.. -*- coding: utf-8 -*- .. Copyright (C) 2014,2019, Wolfgang Scherer, .. .. This file is part of HDP Sudoku. .. .. Permission is granted to copy, distribute and/or modify this document .. under the terms of the GNU Free Documentation License, Version 1.3 .. or any later version published by the Free Software Foundation; .. with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. .. A copy of the license is included in the section entitled "GNU .. Free Documentation License". .. inline comments (with du_comment_role) .. role:: rem(comment) .. role:: html(raw) :format: html .. role:: shx(code) :language: sh .. >>CODD Introduction ================================================== :rem:`|||:sec:|||`\ Resources ================================================== - `SudokuWiki.org`_ - `Systematic Sudoku | Human engineered Sudoku solving`_ - `SadMan Software: Techniques for Solving Sudoku`_ - `The New Sudoku Players' Forum`_ - `SudokuOne - Home of Xsudo`_ -------------------------------------------------- :rem:`||:sec:||`\ Puzzles -------------------------------------------------- - `Sudoku oppgaver (Menneske)`_ - `Printable Puzzles by KrazyDad`_ .. _`Printable Puzzles by KrazyDad`: http://krazydad.com/ .. _`Sudoku oppgaver (Menneske)`: http://www.menneske.no/sudoku/ -------------------------------------------------- :rem:`||:sec:||`\ Monster Loops -------------------------------------------------- - `More Monster Loops, Structure and Symmetry : Advanced solving techniques`_ - `exocet pattern in hardest puzzles : Advanced solving techniques`_ .. _`exocet pattern in hardest puzzles : Advanced solving techniques`: http://forum.enjoysudoku.com/exocet-pattern-in-hardest-puzzles-t6546-15.html .. _`More Monster Loops, Structure and Symmetry : Advanced solving techniques`: http://forum.enjoysudoku.com/more-monster-loops-structure-and-symmetry-t6556.html -------------------------------------------------- :rem:`||:sec:||`\ Bob Hanson -------------------------------------------------- - `Sudoku Assistant/Solver`_ - `Sudoku Analyst`_ - `Sudoku Assistant -- Solving Techniques`_ - `12000 Method Examples -- Sudoku Assistant`_ - `Solution to the Easter Monster Puzzle: Formal Logic and Number Pair Chains:`_ .. _`12000 Method Examples -- Sudoku Assistant`: https://www.stolaf.edu/people/hansonr/sudoku/examples.htm .. _`Sudoku Assistant -- Solving Techniques`: https://www.stolaf.edu/people/hansonr/sudoku/explain.htm .. _`Sudoku Analyst`: https://www.stolaf.edu/people/hansonr/sudoku/analyst.htm .. _`Sudoku Assistant/Solver`: https://www.stolaf.edu/people/hansonr/sudoku/index.htm .. _`Solution to the Easter Monster Puzzle: Formal Logic and Number Pair Chains:`: https://www.stolaf.edu/people/hansonr/sudoku/easter_monster.htm ================================================== :rem:`|||:sec:|||`\ HDP Sudoku Notation ================================================== Cell and range notation is defined similar to spreadsheets. This differs from the rXcY notation used on the web. -------------------------------------------------- :rem:`||:sec:||`\ Rows, Columns, Cells -------------------------------------------------- Columns are labeled with uppercase letters, rows are labeled with numbers:: | A B C | D E F | G H I | ---+-------+-------+-------+ 1 | | | | 2 | Q1 | Q2 | Q3 | 3 | | | | ---+-------+-------+-------+ 4 | | | | 5 | Q4 | Q5 | Q6 | 6 | | | | ---+-------+-------+-------+ 7 | | | | 8 | Q7 | Q8 | Q9 | 9 | | | | ---+-------+-------+-------+ Cells are denoted as `` references. E.g.:: H5 A3 -------------------------------------------------- :rem:`||:sec:||`\ Ranges -------------------------------------------------- Ranges are referenced as comma separated tuples `, , `:: A4,B4,C4,D4,E4 (row segment) C1,C2,C3 (column segment) Contiguous ranges are also referenced in spreadsheet range notation ` .. `:: A4..E4 == A4,B4,C4,D4,E4 (row segment) C1..C3 == C1,C2,C3 (column segment) A4..E5 == A4,B4,C4,D4,E4,A5,B5,C5,D5,E5 (rectangular range) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|:sec:|`\ Quadrants ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Quadrants (blocks) are referenced by `Q`. E.g., quadrant Q1 is equivalent to the cells `A1..C3`:: Q1 = A1, B1, C1, = A1..C3 A2, B2, C2, A3, B3, C3 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|:sec:|`\ Range exclusion ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Set minus notation is used to exclude range(2) from another range. E.g.:: Q1\A1..B2 = A3,B3,C1,C2,C3 Q1\A1..B2\C2 = A3,B3,C1,C3 -------------------------------------------------- :rem:`||:sec:||`\ Possible Values -------------------------------------------------- Possible values of a cell range are given as comma separated number tuples after a colon `: , , `. E.g.:: A5: 1,2,3 A3..B4: 1,2,3 If only a subset or superset of the values is of interest, a trailing short ellipses is used. The given possible values need not actually be present in the cells of a range. E.g.:: Actual Subset/Superset ---------- --------------- A2: 1,2,7 A2: 2.. B5: 3,5,9 B5: 3,5.. C3: 4,7,9 C3: 1,4.. -------------------------------------------------- :rem:`||:sec:||`\ Reasoning -------------------------------------------------- Condition, consequence or reason, constraints. Read:: E1..F1: 2.. => A1..C1 != 2 as: "The possible value 2 (among other possible values) in cells E1,F1 constrains the possible values of cell range A1,B1,C1 to be not 2". Such a condition can also be expressed more clearly as:: Q2: 2.. => A1..C1 != 2 Read it as: "The distribution of possible values 2 (among other possible values) in quadrant Q2 constrains the possible values of A1,B1,C1 to be not 2". ======================================================== :rem:`|||:sec:|||`\ Sudoku Algorithms/Generators/Solvers ======================================================== Good references to other places: http://stackoverflow.com/questions/6963922/java-sudoku-generatoreasiest-solution Algorithms: http://www.sadmansoftware.com/sudoku/solvingtechniques.htm Good generator discussion: http://garethrees.org/2007/06/10/zendoku-generation/ -------------------------------------------------- :rem:`||:sec:||`\ Block/Block Exclusion -------------------------------------------------- :: ---+-------+-------+-------+ 1 | | | | 2 | Q1 | Q2 | Q3 | 3 | | | | ---+-------+-------+-------+ 4 | | | | 5 | Q4 | Q5 | Q6 | 6 | | | | ---+-------+-------+-------+ 7 | | | | 8 | Q7 | Q8 | Q9 | 9 | | | | ---+-------+-------+-------+ Examine block relations in 3 sets of 3-cell-strips: By rows:: Q1 Q2 Q3 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip Q4 Q5 Q6 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip Q7 Q8 Q9 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip By columns:: Q1 Q4 Q7 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip Q2 Q5 Q8 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip Q3 Q6 Q9 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip 3-cell-strip | 3-cell-strip | 3-cell-strip -------------------------------------------------- :rem:`||:sec:||`\ Pair, Triple, .. Detection -------------------------------------------------- The goal is to find a distribution of x values over x cells. A general distribution algorithm has worst case complexity of choose(). Since choose() is polynomial, the algorithm is effective. Worst case number of possible distribution combinations for 9 free cells:: choose(9,2) = 36 choose(9,3) = 84 choose(9,4) = 126 choose(9,5) = 126 choose(9,6) = 84 choose(9,7) = 36 choose(9,8) = 9 | The minimal case of 2 values distributed over 2 free cells = choose(2,2) = 1 is trivial. | The maximal case of 9 values distributed over 9 free cells = choose(9,9) = 1 is also trivial. The sum() is 501 different combinations per 9-segment (row, column, quadrant). The maximum amount of possible combinations is therefore:: (9 rows + 9 columns + 9 quadrants) * 501 = 13527. The general formula for the number of possible combinations depending on the number of free cells is:: if max(free) > 2: for x = 2..max(free)-1: choose(max(free), x) The possible pairings can be held in tables to avoid repeating calculations at run-time. If an x-distribution of values over x cells is found, both hidden and naked pairs can be handled with the result. -------------------------------------------------- :rem:`||:sec:||`\ Coloring -------------------------------------------------- - mark all pairs (including blocks) - alternate colors as necessary - disable all cells that share both a cell and an alternate - repeat See sadman-swordfish3-base.sdk value2 for a good example However, see algo-xy-wing-000-base.sdk value 3 for a counter-example of weakly-linked blocks ================================================== :rem:`|||:sec:|||`\ Design ================================================== sudoku::cell sudoku::cell::var:: parent -> sudoku::cell ================================================== :rem:`|||:sec:|||`\ Hard Puzzles ================================================== From `More Monster Loops, Structure and Symmetry : Advanced solving techniques`_:: .......39.8......5..9.6.8....5.9...67....2......4.......3.8..5..2.7..6..4.....1.. colx062,coloin 2.8 3BB r12c7 r4c8 r7c9 .....4.....2.3.....5.7....9..4..2.8..985....63.........8....79....8...6...5.1...8 tarx0035,tarek 28.1 1.5 *3BB r9c78 r7c4 r8c2 ........2..1...7...3..5..9......6.4...3.4.8...4.5.9....9..6..3...2...1..7....3... tarx0006;Trompe_l'oeil 33.4 1.5 *3BB r5c46 r4c2 r6c8 ..9.......6...3...1...7...54...52..7.....6.4..3.9.....2......1.....2.57...48....2 tarx0064,tarek 5.1 *3BB r9c78 r7c5 r8c1 .......89.....1.35..3.5......5.6...8.7...2...1..4.......6.9..5..2.7..6..4........ colx180,coloin 22.7 23.5 *BB r12c7 r4c8 r7c9 .....5..3..9....4..81.4.......7.......4..2..68...14.3.......2...4...6..79...5..1. tarx0108,tarek 49.5 1.9 *3BB r1c23 r2c5 r3c8 ........3..1..9.6..5..8.4.....9...8...867.....1....2....6..7.2..3.8..5..4.......8 tarx0119,tarek 63.5 1.7 *3BB r6c45 r4c3 r5c8 ........6..2....4..1...798....79.....8..5......3..8.1...6....2..9...51..4.......8 tarx0010,tarek *53.9 2.0 3BB r6c45 r4c2 r5c7 .....5.....3.7...8.9.8...4...5.....2.8.6..4..7...3......2...69...4...1...1.9....4 tarx0062,tarek 8.3 *3BB r78c9 r3c7 r5c8 ........7..9.5.2..1....6.8....5..6...9.....3...64.2....8.6.......4.2.9..7......61 tarx0004,tarek, 5.3 *3BB r5c46 r4c3 r6c7 ........7..1..9.8..3.6..5.9.9..25.......6....3..9...4...7....91.2.5..3..8........ tarx0003,tarek 6.1 *3BB r6c56 r4c7 r5c2 .....1.....7.2.....9.6.8..5..1..7....6.9....42.9.........8...59.8....4....6.3...8 tarx0079,tarek 4.7 *3BB r9c78 r7c2 r8c4 ........6..9...4...1..7..8....7.1.3.1.8.3.5...3...2....8..2..1...6...9..4..3..... tarx0114,tarek 4.3 *3BB r5c46 r4c2 r6c8 ..1.......5...6..16.7...........1..3...4.5.8..9..2..5...5..3..7....8..4..3.5..2.. tarx0014,tarek 5.8 *3BB r13c2 r4c3 r7c1 ........7.2.4...6.1.....5...9...2.4....8..6..6..9.......5..3....3..8..2.7....4..1 TungstonRod,coloin 9.7 3BB r56c6 r2c5 r8c4 ........2..8..91..5......4....9.7.....7.3.8.....8.1.3..4..6...5..97..3..2........ tarx0052,tarek 2.5 *3BB r46c5 r2c4 r8c6 ........91......35..9.3.8....3.5...67....2......4.......6.8..9..2.7..6..4.....1.. weekender1,coloin 56.8 3.6 3BB r12c7 r4c8 r7c9 ........3..1..56...9..4..7......9.5.7.......8.5.4.2....8..2..9...35..1..6........ tarx0001;Fata_Morgana 7.1 1.2 *3BB r5c46 r4c2 r6c8 ........5..8..79...6..1..4....1.2.7.4...7...3.7.6......3..2..6...5...8..9.......7 tarx0002,tarek 32.4 2.3 *3BB r5c46 r4c2 r6c8 ........9..6.1.7.24......3......12...6..2..5...28.7....3......4..8.7.6..9..1..... tarx0130,tarek 8.0 3BB r5c46 r4c3 r6c7 ........2..8.1.9..5....3.4....1.93...6..3..8...37......4......53.1.7.8..2........ tarx0140,tarek 8.3 3BB r5c46 r4c3 r6c7 ..6.......3...7..11.7.............9.3....6..5.5.8..2....3..5..6...2...4..4..9.8.. tarx0137,tarek 42.3 1.3 3BB r13c2 r5c3 r7c1 .......1......4.32.2..3.5.......7....4..2...5..89..4....78..6...3..1..5.9........ coly004,coloin 4.4 *3BB r12c7 r5c8 r8c9 .....7..8.3..2..9...84..3....6.......8.5..6..5.4..........9.8.2.1.....7.8..3..4.. tarx0121,tarek 42.3 1.3 *3BB r46c2 r3c1 r9c3 ........9..1...6...5..7..4....4.7.8...3.8...5.8...2....78.2..5..39...1..6........ tarx0011,tarek 7.2 *3BB r5c46 r4c2 r6c8 .......93.8......5..3.6.8....5.9...67....2......4.......9.8..5..2.7..6..4.....1.. colx1665,coloin 4.3 3BB r12c7 r4c8 r7c9 ........2..7...1...3..9..4......9.6.6...3.4.5.4...8....6..4..5...2...7..1..8..... tarx0145,tarek 5.5 *3BB r5c46 r4c2 r6c8 ........6..5.3.7..2....8.1....9..8...5..8..4...87.3....1.3.......7.9.5..6.......2 tarx0013,tarek 23.8 1.9 *3BB r5c46 r4c3 r6c7 ........8..3.9.4..6....7.1....5.97...3.....2...74........7....6..4.5.3..81....... tarx0007,tarek 6.4 *3BB r5c46 r4c3 r6c7 .2.4..7.........32.......94.9.2...7...6..5...8...1....5.1..8....3.9....7......6.. colx467,coloin 2.1 3BB r23c7 r4c9 r8c8 .....6.....1.2...3.3.8...7...6.....5.5.3..7..2....1.......9..4...5...98..9.4....7 tarx0008,tarek 53.2 3.2 3BB r78c9 r3c7 r5c8 ........6..4.7.9.28......3......72...4..2..1...25.9....3......8..9.5.7..6......9. tarx0103,tarek 4.7 3BB r5c46 r4c3 r6c7 ........7..4.2.6..8.....31......29...4..9..3...95.6....1......8..6.5.2..7......6. tarx0139,tarek 3.0 3BB r5c46 r4c3 r6c7 1.......2....1..3...5..34....2..1..4....8.7..6..9.......1..5.4.8.....5..9...6.... coly001,coloin 3.3 3BB r12c7 r4c8 r7c9 ..8.......5...8..11.9.4........3......5..9..4.4.6...7.......6..5....4.29.2..7..3. tarx0061,tarek 28.6 2.9 3BB r13c2 r5c1 r8c3 ........7..2...6...8..1..9....9.1.3.3...8...4.9...5....3..9..4...7...2..6..5..... tarx0146,tarek 5.0 *3BB r5c46 r4c2 r6c8 ....9..5..1.....3...23..7....45...7.8.....2.......64...9..1.....8..6......54....7 coly013,coloin 1.4 BB r12c7 r4c9 r8c3 BB r56c8 r3c9 r9c7 ...1....87.......9..6.9.5....8.6...5.....23...7.4..6....3.8..5..2...1....4....... coly012,coloin 3.7 BB r12c7 r4c8 r7c9 BB r56c9 r3c8 r7c7 ........7..2..96..8...6...3....92.....46..5...1..54.....5.4.9...3.....7.1.......8 tarx0009,tarek 15.1 13.8 *BB r46c4 r2c5 r7c6 .....6..5.1.....2...9.3.4......7......48.9...8..4.39....7.8.3...5.....1.2.......6 tarx0012,tarek 3.2 BB r4c46 r5c7 r6c3 .......1...6....23.2..3.4..8....5....3..1...4..96........9..7...1..2..4.5....8... coly002,coloin 7.1 BB r12c7 r5c8 r8c9 ........5..6..87..3......9....1.7.4...7...8...4...6....9..8...3..16..4..5...2.... tarx0067,tarek 2.5 BB r46c5 r2c4 r8c6 ...2....87.......9..3.9.5....8.3...51.....3.....4..6....6.8..5..7...1...2....4... coly007,coloin 4.3 BB r12c7 r4c8 r7c9 BB r56c9 r3c8 r7c7 .1......8.7...4..9..3.9.5....8.3...5.2....3.....4..6....6.8..5.2....1......7..... coly010,coloin, 2.6 BB r2c17 r4c8 r7c9 BB r56c9 r3c8 r7r7 ...1....8.7......9..3.9.5....8.3...57....23.....4..6....6.8..5.4....1...2........ coly006,coloin, 3.7 BB r2c17 r4c8 r7c9 BB r56c9 r3c8 r7r7 ...1....87.......9..3.9.5....9.3...5.....23.....4..6....6.8..5.47...1...2........ coly008,coloin, 3.4 BB r2c17 r4c8 r7c9 BB r56c9 r3c8 r7r7 .....5..4.9.....2...6.7.3.....7..8....86.....13..8......3.1.6...2......54......9. tarx0068,tarek 16.0 18.*BB r6c46 r4c3 r5c7 ........6..5..8.9..3.4..7....491........8..4.5....42....1..9.5..6....4.37........ tarx0005,tarek, 6.4 *BB r6c45 r4c8 r5c3 .....1.39........5..3.5.6....8.9...67....28..1..4.......9.8..5..2.......4..7..... colx001,coloin 28.6 BB r12c7 r4c8 r7c9 1.......5.2.4...6...3...7...9...4........9.8.8.26.........5.1...6.9...2...7.....3 colx134,coloin 32.0 BB r6c56 r4c8 r5c2 .......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7..... Golden_Nugget,tarek 56.7 30 *BB r12c7 r4c8 r7c9 ........6..5..18...9...8.7....8.2.....3.1.2..4..5.3....6.....9...83..1..7.......4 tarx0075,tarek 22.5 18.3 *BB r46c5 r2c4 r8c6 3.......2.8..7..1...69......5.7.4...........8...51..7...9...3...1..4..8.2.......6 Pearly6000-1801,tarek, 33.0 21.6 *BB r5c46 r4c8 r6c2 7....4..8.1......9..6.9.5....8.6...5.....23.....4..6....3.8..5.2....1......7..... coly009,coloin 1.5 BB r12c7 r4c8 r7c9 BB r56c9 r3c8 r7c7 1.......7.2.4...6...3...5...9..4........62.4....9..8....5.....3.6.2...8.7....1... SilverPlate,coloin 67.2 77.9 BB r6c56 r4c8 r5c2 9....4....3..6..7...5...8...2.1.6.......7...3...2...1...8...9...7..1..6.4.......5 tarek071,tarek 29.6 29.6 *BB r5c46 r4c8 r6c2 1.......7.2.4...6...3...5...9..82.......9..8....6..4....5...1...6.8...2.7....3... BronzeMedalian,coloin 16.5 16 *BB r6c56 r4c8 r5c2 .....1..7....6..2.8..9..3...954....3..3...4..4......8......7..6.1..2....5..3..9.. tarx0018,tarek 2.5 *bb(2) r6c23 r4c7 r5c4 ..4.....9.1...3.7.6.....2.......8....5..3..8....1.5.....2.....4.7.3...1.9...7.6.. tarx0037,tarek 7.0 SK *BB r46c5 r2c4 r8c6 1.........2.4...6...3...5.1.4..86.......49.8....2.....5.7...3...6.9...4.........7 CloudyBay,coloin 5.1 SK *BB r6c56 r4c8 r5c2 1.......2.2.....6...34..5.....8.5.....8.3.9.....9.4.....5..34...7.....1.6.......7 dukdiamond1,coloin 3.2 SK *bb(2)r5c1289 r3c6 r7c4 Platinum Blonde:: .......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6... PlatinumBlonde .. >>CODD Chapter .. >>CODD Conclusion .. >>CODD Appendix A ================================================== :rem:`|||:sec:|||`\ Perl version of solver ================================================== .. note:: There is a memory leak in Perl/Tk, which causes X11/ibus daemon to become increasingly slower, if the program is restarted. (See http://stackoverflow.com/questions/14408521/perl-tk-memory-leak-when-using-destroy-command). ================================================== :rem:`|||:sec:|||`\ Classification ================================================== -------------------------------------------------- :rem:`||:sec:||`\ Single Sudoku Analysis -------------------------------------------------- - classify.py Generates basic analysis for sudoku. Output to :file:`sudoku-base`. .. code-block:: sh classify.py --replace --document sudoku-base.sdk ... - csp-setup.sh generate CSP specification and satoku matrix for sudoku .. code-block:: sh csp-setup.sh sudoku.sdk ... - cdcl_check.sh output to :file:`sudoku-base` .. code-block:: sh cdcl_check.sh sudoku-base.sdk ... - class-stats.sh Generate hdp.csv and dump it .. code-block:: sh class-stats.sh sudoku.sdk .. - clue-count.sh count the number of clues of the original sudoku generates sdfs.csv .. code-block:: sh clue-count.sh sudoku.sdk ... -------------------------------------------------- :rem:`||:sec:||`\ Sort -------------------------------------------------- - classify-level.sh divert :file:`*-base.sdk` into level directories .. code-block:: sh classify-level.sh -------------------------------------------------- :rem:`||:sec:||`\ Statistics -------------------------------------------------- - csp_check.sh check Satoku CSP results and prepare report .. code-block:: sh csp_check.sh | tee README-csp-check.txt sda readme --format singlehtml README-csp-check.txt sda make html - make-automated-index.sh refresh index files for top directory and all level directories .. code-block:: sh make-automated-index.sh --force # uses make-analysis-indexes.sh, make-analysis-index.sh, clue-count.sh These operations are collected in :program:`publish.sh`. .. \|:here:| .. >>CODD Notes .. ================================================== .. :rem:`|||:sec:|||`\ Footnotes .. ================================================== :html:`
` .. \[#] .. >>CODD Reference List/Bibliography .. ================================================== .. :rem:`|||:sec:|||`\ References .. ================================================== .. include:: doc_defs.inc .. include:: doc_defs_combined.inc .. .. \||<-snap->|| doc_standalone .. include:: doc/doc_defs_secret.inc .. \||<-snap->|| doc_standalone .. \||<-snap->|| not_doc_standalone .. include:: doc_defs_secret.inc .. \||<-snap->|| not_doc_standalone .. _`Wolfgang Scherer`: wolfgang.scherer@gmx.de