« Girl Scout Cookies, Anyone? | Main | It Didn't Rain Yesterday... »

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[0]

This reads the first 9 lines from the file represented by $args[0]. 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

Trackback Pings

TrackBack URL for this entry:
http://proudlyserving.com/cgi-bin/mt-tb.cgi/385

Comments

Posted by: Abomb at January 14, 2006 11:14 PM