# 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 (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


“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

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¶

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