HDP Sudoku Notation

Cell and range notation is defined similar to spreadsheets.

This differs from the rXcY notation used on the web.

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 <column><row> references. E.g.:

H5
A3

Ranges

Ranges are referenced as comma separated tuples <cell_1>, <cell_2>, <cell_3>:

A4,B4,C4,D4,E4 (row segment)
C1,C2,C3       (column segment)

Contiguous ranges are also referenced in spreadsheet range notation <upper left cell> .. <lower right cell>:

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)

Quadrants

Quadrants (blocks) are referenced by Q<number>. E.g., quadrant Q1 is equivalent to the cells A1..C3:

Q1 = A1, B1, C1, = A1..C3
     A2, B2, C2,
     A3, B3, C3

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

Possible Values

Possible values of a cell range are given as comma separated number tuples after a colon <range>: <value_1>, <value_2>, <value_3>. 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..

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”.

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/

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

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.

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

Design

sudoku::cell

sudoku::cell::var:

parent -> sudoku::cell

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

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).

Classification

Single Sudoku Analysis

  • classify.py

    Generates basic analysis for sudoku. Output to sudoku-base.

    classify.py --replace --document sudoku-base.sdk ...

  • csp-setup.sh

    generate CSP specification and satoku matrix for sudoku

    csp-setup.sh sudoku.sdk ...

  • cdcl_check.sh

    output to sudoku-base

    cdcl_check.sh sudoku-base.sdk ...

  • class-stats.sh

    Generate hdp.csv and dump it

    class-stats.sh sudoku.sdk ..

  • clue-count.sh

    count the number of clues of the original sudoku

    generates sdfs.csv

    clue-count.sh sudoku.sdk ...

Sort

  • classify-level.sh

    divert *-base.sdk into level directories

    classify-level.sh

Statistics

  • csp_check.sh

    check Satoku CSP results and prepare report

    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

    make-automated-index.sh  --force # uses make-analysis-indexes.sh, make-analysis-index.sh, clue-count.sh

These operations are collected in publish.sh.