TITLE 
Sudoku - A sudoku solver
OVERVIEW
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.
SYNOPSIS
parrot -Ot sudoku.pir [--options] [file]
If no file is given a builtin game is run.
Valid options are:
- --version
- Print version information and exit.
- --help
- Print help hint and exit.
- --debug
- Print debug output and game progress to stdout.
- --inv=n..
- Print additionally invalid state of given number(s).
- --builtin=name
- Run builtin game. If no name is given a list of builtins is printed.
- --nc
- Use ncurses for display and single step through progress. Press any key for next display.
DESCRIPTION
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
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
PARROT
Parrot features used
- Parrot OO
- The solver is an object as well as the display.
- Freeze/thaw
- For deep copying the game state for backtracking.
- Multi Method Dispatch
- The display classes define multiple methods with the name print, which take different types and amounts of arguments.
- Libraries
- The program uses Getopt/Obj and the ncurses library.
- Exception handling
- To turn off ncurses just in case.
Variable indices
Column, rows, and sqares have zero-based indices. Squares are numbered from top left to bottom right.
Sudoku Class attributes
- rows, cols, sqrs
- LoL of 0 = free, 1..9 = number
- i_rows, i_cols, i_sqrs
- LoL of a bitmask of invalid numbers per field. Bits are starting at bit one not zero.
- all
- Hash referencing these 6 items - used for backtracking.
- opt
- The option hash.
- disp
- Holds an instance of the display class (Dummy, NCurses) to use.
AUTHOR
Leopold Toetsch
COPYRIGHT
Same as parrot.
Advanced checks
Double blocked rows/columns
Consider this one:
# daily sudoku 16-nov-2005 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.
Blocking due to multiple others
Given this sudoku:
# daily sudoku 16-nov-2005 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) = (2|6)
| 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) = (3|5|9)
| . . . | 7 . . | b 1 8 |
| . . . | 1 . 9 | 7 . c |
+---------+---------+---------+
Now the tests in "create_inv_n" invalidate illegal positions due to multiple-blocking and other tests are likely to proceed.
TODO
# daily sudoku wed 28-dec-2005, 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 'X-Wing' 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
