parrotcode: A sudoku solver  
Contents  IMCC 
Sudoku  A sudoku solver
This program implements scanning and blocked rows or columns invalidation. It does not consider all effects of multiple number blocking, where a combination of invalid numbers blocks a row or column. In such cases a simple backtracking algorithm continues to solve the sudoku.
parrot Ot sudoku.pir [options] [file]
If no file is given a builtin game is run.
Valid options are:
The game state is held in multiple views which share one Integer PMC per common position. Thus updating a row sets also the column or square information. These three views are list of lists.
Game files may contain comments (hash sign in the first column) digits, and dots for empty fields. E.g:
# std020.sud
# der standard 020  leicht
2.1..678.
...2...36
8.9.3...5
.7...4..2
..6.9.5..
9..5...6.
5...4.9.7
71...3...
.987..2.3
Column, rows, and sqares have zerobased indices. Squares are numbered from top left to bottom right.
Leopold Toetsch
Same as parrot.
Consider this one:
# daily sudoku 16nov2005 very hard
.5..3.9..
.394.....
.....964.
.6...84..
5.......8
..19...2.
.826.....
.....576.
..5.9..8.
It got solved until here, then backtracking began (and succeeded).
++++
 4 5 6  8 3 .  9 . .  777 77. 7..
 . 3 9  4 . .  8 . .  .77 7.. 7..
 . . 8  . . 9  6 4 3  ..7 ..7 777
++++
 . 6 .  . . 8  4 . .  .7. ..7 7..
 5 . .  . . .  . . 8  7.. ... 7.7
 8 . 1  9 . .  . 2 6  7.7 7.. 777 <<<<<<<<<<
++++
 . 8 2  6 . .  . . .  .77 7.. 777
 . . .  2 8 5  7 6 .  777 777 777
 6 . 5  . 9 .  2 8 .  7.7 .7. 777
++++
Have a look at the marked row 5. '3' and '5' can't be in col 1. So '3' and '5' have to be at the right side of the row.
Now take a look at the '7'  invalid positions are shown above already (dumped with the inv=7 option).
In both squares 0 and 6 the '7' can only be in columns 0 or 1. This implies that a '7' has to be in col 2, row 3 or 4. Looking at square 5, the '7' is also in row 3 or 4. Therefore the '7' in the middle square (4) has to be too in row 5.
Voila we have 3 numbers (3,5,7) which are somewhere on the right side of row 5 and we get a unique number in row 5, col 1  the '4'.
And then it's easy.
One part (the '7') is implemented in scan_dbl
, which boils down this case to the other one below.
Given this sudoku:
# daily sudoku 16nov2005 very hard
.5..3.9..
.394.....
.....964.
.6...84..
5.......8
..19...2.
.826.....
.....576.
..5.9..8.
Earlier sudoku.pir started backtracking at:
++++
 . . 1  3 8 5  . . . 
 6 8 7  . 1 .  . 9 . 
 2 3 5  6 9 7  . . 1 
++++
 1 . .  9 7 3  . 5 . 
 . 7 6  5 . 8  1 3 . 
 . 5 .  . 6 1  . . . 
++++
 7 1 .  8 . .  . . 4 
 . . .  7 . .  . 1 8 
 . . .  1 . 9  7 . . 
++++
In columns 7 the digits (9,5,3) are blocking this column in square 8 so that the digits (2,6) have to be in column 7 too. Which implies that in square 2 we have a unique '7' at row 0, col 7:
++++
 . . 1  3 8 5  x 7 y  (x,y) = (26)
 6 8 7  . 1 .  . 9 . 
 2 3 5  6 9 7  . . 1 
++++
 1 . .  9 7 3  . 5 . 
 . 7 6  5 . 8  1 3 . 
 . 5 .  . 6 1  . . . 
++++
 7 1 .  8 . .  a . 4  (a,b,c) = (359)
 . . .  7 . .  b 1 8 
 . . .  1 . 9  7 . c 
++++
Now the tests in "create_inv_n" invalidate illegal positions due to multipleblocking and other tests are likely to proceed.
(This is partially still TODO)
Given this suduku:
# "unsolvable" 3  YWing . . . 8 . . . . 6 . . 1 6 2 . 4 3 . 4 . . . 7 1 . . 2 . . 7 2 . . . 8 . . . . . 1 . . . . . 1 . . . 6 2 . . 1 . . 7 3 . . . 4 . 2 6 . 4 8 1 . . 3 . . . . 5 . . .
It started backtracking at:
++++
 . 3 .  8 5 4  . 1 6  .. .. 29 .. .. .. 79 .. ..
 . . 1  6 2 9  4 3 .  .. .. .. .. .. .. .. .. ..
 4 6 .  3 7 1  . . 2  .. .. .. .. .. .. .. 59 ..
++++
 . 4 7  2 9 3  . 8 1  56 .. .. .. .. .. 56 .. ..
 . . .  . 1 7  3 . .  .. .. .. 45 .. .. .. .. 59
 . 1 3  . 8 6  2 . .  59 .. .. 45 .. .. .. .. ..
++++
 1 . .  7 3 2  . . 4  .. .. .. .. .. .. .. .. ..
 . 2 6  9 4 8  1 . 3  57 .. .. .. .. .. .. 57 ..
 3 . 4  1 6 5  . 2 .  .. .. .. .. .. .. .. .. ..
++++
The numbers on the right side are showing squares with unique pairs. Having a look at the columns 7 and 8, we see these pairs (79, 59, and 57)
Let's label these numbers as A, B, and C:
++++
 . 3 .  8 5 4  AC 1 6 
 . . 1  6 2 9  4 3 . 
 4 6 .  3 7 1  . AB 2 
++++
 . 4 7  2 9 3  . 8 1 
 . . .  . 1 7  3 . . 
 . 1 3  . 8 6  2 . . 
++++
 1 . .  7 3 2  X . 4 
 . 2 6  9 4 8  1 BC 3 
 3 . 4  1 6 5  X 2 . 
++++
When we now try to fill row 2, column 7 with A or B, we see that at positions X, a C can't be valid. Either it's blocked via the column or directly via the last square. Thus we can eliminate digit 7 from positions X.
# daily sudoku wed 28dec2005, very hard
# backtracking
...52.63.
.5.....7.
9....8..2
.17..4...
.9.....6.
...8..31.
1..6....5
.4.....9.
.86.95...
This one starts backtracking early. The '6' is an 'XWing' like configuration (col 1 and row 2 with a common corner have just 2 possible positions, just one is valid, when you try both). The same happens a bit later with '9'.
++++
 . 7 .  5 2 .  6 3 .  666 666 666
 . 5 .  . . .  . 7 .  .66 6.. 666
 9 . .  . . 8  . . 2  6.6 6.6 666
++++
 . 1 7  . . 4  . . .  .66 6.6 666
 . 9 .  . . .  . 6 .  666 666 666
 . . .  8 . .  3 1 .  ..6 6.. 666
++++
 1 . 9  6 . .  . . 5  666 666 666
 . 4 .  . . .  . 9 6  666 666 666
 . 8 6  . 9 5  . . 3  666 666 666
++++
Here is starts backtracking. A possible improvement would be:
 detect such digit configuration
 only backtrack try this digit ('6') above
See also std331.sud
A Sudoku has 2 dimensions and 3 connected views (row, column, and square). There are 1dim tests, which work for all views. 2dim tests are a bit more tricky to generalize and not yet done properly.
Basically: as only 2 views are independant, all these tests can work on 2 of 3 views:
square, row
square, column
row, columm
Now the problem is, how to generalize the possible other direction. Let's call it the 'neighbour'. A neighbour is always 'towards' the second view. A row has 9 column neighbours and 3 square neighbours. A square has 3 row and 3 column neighbours. (Maybe neighbour is a bad term as it does contain itself).
scan_dbl
can now easily be reviewed and generalized:
For all neighbours (n): If in the view (v0) a digit is valid in only one of (n)'s views: giving (v1), this digit is invalid in the complement of the intersection (v0 & v1).
NB: it seems to be simpler to just hack the code as to utter the idea in $human_lang.
This is trivial if these views are (row, column) as the intersection is just one point, but it is the generalization of the 'inv_1' code.
Another example of a 2dim test is of course YWing.
