## January 14, 2006

### Simple Sudoku Solver

I previously mentioned sudoku on this blog, and my wife bought me a 2006 "Sudoku a Day" desk calendar. So I've been noodling around solving them and it occured to me that I should write a Monad script to work on it.

The scripts takes as input a file containing 9 lines of 9 characters each, with the dots representing unfilled spaces. For example this is the contents of one input file:

``` 7..9..36. .596.3.8. 4...8.91. 9..4..... .7.....9. .....1..2 .83.5...9 .9.3.485. .47..9..3 ```

The full Sudoku solver in Monad script is posted here; I'll comment on some of the specifics of the code below. The only problem with the script is that it isn't very good. It solves them the way I solve them: I look at a given group of nine squares (row, column, or 3x3 box), then consider a number such as 2, and ask myself "Is there no 2 in this group yet, and if so, when I knock out all the spaces where the 2 can't be (because they are occupied, or because there is a 2 somewhere in a row/column/box that conflicts with this square), do I only have one space left?" If so, put a 2 there.

So it chews through simple sudokus but gets stuck on some more complicated ones. After consulting this sudoku site, I see that my current approach is way too simple. For example I miss the case where a number has to go in a given cell because all 8 of the other numbers have a conflict with it (imagine a sudoku which had only the numbers 1 through 7 in the first 7 spaces of the first row, and then an 8 somewhere else in column 8; my solution would miss the fact that row 1, column 9 had to have a 9 in it). This is called "SiSo" on Vegard Hanssen's page. And then there are other reducing methods, which like SiSO all involve keeping track of a "solution table", which is every possible number that can go in a particular cell, and then knocking possibilities off until you only have one left. This would also be easy to do in Monad, but I haven't done it yet. I'll present my current code to demonstrate my narcissism some Monad stuff.

To wit:

``` write-host -nonewline \$board[\$y][\$x] ```

The -nonewline option on write-host does what you might expect. write-host defaults to adding the new line.

``` \$board | foreach-object { \$count += (\$_ -like "[1-9]").Length } ```

This line (which follows one initializing \$count to 0) counts how many digits are on the board. \$board is a two-dimensional array, which is really an array where each element is an array. So sending \$board down a pipeline will cause each record in the pipeline to itself be an array, representing one row in the board. Using the -like operator on \$_ when \$_ is an array will return an array containing all the matching elements; in this case -like "[1-9]" means everything that is a digit between 1 and 9. Then you take the Length property of the resulting array and the result is the total number of cells in \$board that are a number 1 through 9.

``` get-content -TotalCount 9 \$args ```

This reads the first 9 lines from the file represented by \$args. So the usage of this script is
``` sudoku foo.txt ```
where foo.txt contains one of the sudokus in the format shown above.

``` \$arr = [char[]]\$_ ```

This converts a string (which is one of the input lines of the file in this case) to an array of chars.

``` \$board += ,\$arr ```

This appens the array \$arr to \$board as a single new element which is itself an array. If you just += without the , operator, then it concatenates the two arrays.

``` \$conflicts = new-object int[] 9 \$conflicts = (0..8) | foreach { \$false } ```

This initializes \$conflicts to be an array of nine integers, and then initializes it to an array of 9 \$false values. Looking at it now the second line makes the first useless (the array created by new-object just gets tossed by the second line) but I'll keep it here since it shows how to create an array using new-object.

``` continue nloop ```

This allows continue (and break, if you use it with that) to target a specific loop. Pay attention: it DOES NOT jump to the label; what it does is find the loop that is labeled with that name, and continues IT. The label precedes the loop. So the :nloop loop is the foreach (\$n in (0..8)) one. The continue nloop statement moves to the next value of \$n and runs the loop again.

``` if ((\$conflicts -eq \$false).Length -eq 1) ```

This line checks if \$conflicts has exactly one element that is equal to \$false. First it uses -eq to filter out the elements equal to \$false, then it counts them and compares that to 1. NOTE that on older drops of Monad, you would have use -contains instead of -eq to get this effect. -contains and -eq swapped semantics and now -contains just returns true or false in this situation.

At some point I'll hack up a sudoku solver that does it "right" and then we can discuss that one.

Posted by AdamBa at January 14, 2006 09:43 PM