Archive

Archive for September, 2010

A sudoku solver in powershell

September 16, 2010 3 comments

Seriously – why would someone implement a sudoku solver in powershell? Is it a masochistic exercise in scripting? Or maybe some kind of crazy experiment?  I am not sure. I did it anyway. And not only that – I publish it here.

First of all, the game plan, must be stored somehow. Previously, I have used a 2d-array of integer sets. Powershell supports multidimensional arrays but the support seemed rather limited at a quick glance. Arrays, however, are a fundamental building block and, among other things, powershell offers a convenient slicing syntax (i.e. $array[2..4]). Based on these observations I decided to try jagged arrays or arrays of arrays. (It turned out that I had no use of the slicing syntax so I guess I lost my arguments along the road).

Here is my code for creating and initializing the chosen data structure from a given string of digits:

function parse($data)
{
    $solution = @()
    for ($r=0;$r -lt 9;$r++)
    {
        $row = @()
        for($c=0; $c -lt 9; $c++)
        {
            $ch = $data[$r*9+$c]
            if ($ch -eq ‘0’)
            {
                $row += ,(1,2,3,4,5,6,7,8,9)
            }
            else
            {
                $val = [int]$ch  [int][char]‘0’
                $row += ,($val)
            }
        }
        $solution += ,$row
    }
    $solution
}

I struggled a bit with this, seemingly simple piece of code and I tried a couple of different approaches before ending up with this one. The number one problem I hade was that powershell wanted to flatten my arrays. To prevent this I had to prefix my elements with the comma operator. Powershell has a complex way of handling arrays (and arrays of arrays) and it might be good in some scenarios but during this exercise it caused me a lot of headace. Anyway, this function will return a jagged 9×9 array where each cell contains an enumeration of the possible values for that cell.

Having created and initialized the game plan, we can pass it on to the solve function:

function solve($solutionIn)
{
    # clone input since we will modify it
    $solution = deep-clone-array $solutionIn

    # apply reduce
    reduce $solution

    # invalid solution?
    $invalid = @(enumerate-indices | ? { $solution[$_.R][$_.C].Count -eq 0 })
    if($invalid.Count -gt 0)
    {
        return $null
    }

    # ambiguous or finished?
    $ambiguous = @(enumerate-indices | % { $_ | add-member noteproperty "Count" $solution[$_.R][$_.C].Count; $_ } |
                   ? { $_.Count -gt 1 } | Sort Count)
    if ($ambiguous.Count -gt 0)
    {
        $lac = $ambiguous[0]
        $values = $solution[$lac.R][$lac.C]
        foreach($value in $values)
        {
            $solution[$lac.R][$lac.C] = $value
            $newsol = solve $solution
            if ($newsol) { return $newsol }
        }
    }
    else
    {
        return $solution
    }
}

First of all, reduce is called which is the iterative step that removes impossible values based on the definite along with the rules of sudoku. We will get back to this function later on. As before, calling reduce might lead to three different cases:

  • an invalid solution (when one or more cells do not have any possible values left),
  • an ambiguous solution (when one or more cells have multiple possible values,
  • and finally, a valid solution (when all cells have one single possible value).

The solve function uses two utility functions; deep-clone-array and enumerate-indices. deep-clone-array, opposed to array.clone(), makes sure that the returned array shares no data with the original. The implementation is short, but maybe not obvious:

function deep-clone-array($a)
{
    $a | % { if ($_.gettype().isarray) { ,(deep-clone-array $_) } else { $_ } }
}

Again, notice the prefix comma operator that prevents powershell from flattening the result. The pipeline operator | and the foreach-object alias % helps keep the code compact. Here is enumerate-indices (companioned with its helper create-index):

function create-index($r, $c)
{
    $t = New-Object psobject
    $t | Add-Member NoteProperty "R" $r
    $t | Add-Member NoteProperty "C" $c
    $t
}

function enumerate-indices($rMin = 0, $rCount = 9, $cMin = 0, $cCount = 9)
{
    $rMax = $rMin + $rCount  1
    $cMax = $cMin + $cCount  1
    $rMin..$rMax | % { foreach($c in $cMin..$cMax) { create-index $_ $c } }
}

This one is interesting, I think, since it benefits from the dynamic nature of powershell. create-index creates a new psobject and adds two properties, R and C, to it using the Add-Member commandlet.

One more thing before we move on to the reduce function; you might have noticed that some expressions are wrapped in @(). Why? Well, again, this comes down to the way powershell handles arrays. Depeding on the number of objects returned from a pipeline, powershell behaves differently:

  • If zero objects are returned the result will be null
  • If one object is returned the result will be that object
  • If more than one object is returned the result will be an array of objects

Strange? At least unconventional in my opinion. I guess this design was chosen because it is convenient in many scripting scenarios. We can “undo” this behaviour by wrapping the statement in a @(). This will make sure that the result is always an array.

Enough about the solve function. Let’s move on to the reduce function:

function reduce($solution)
{
    $changed = $false
    do
    {
        $changed = $false
        for ($r=0;$r -lt 9;$r++)
        {
            for($c=0; $c -lt 9; $c++)
            {
                if (is-ambiguous $solution[$r][$c])
                {
                    $row = select-row $solution $r $c
                    $col = select-column $solution $r $c
                    $block = select-block $solution $r $c
                    $newsol = @( $solution[$r][$c] | ? { $row -notcontains $_ } | ? { $col -notcontains $_ } | ? { $block -notcontains $_ } )
                    if (-not (compare-arrays $newsol $solution[$r][$c]))
                    {
                        $solution[$r][$c] = $newsol
                        $changed = $true
                    }
                }
            }
        }
    } while($changed)
}

 

This function is ofcourse not complete without the definitions of the slicing operations; select-row, select-column and select-block:

function select-row($solution, $r, $c)
{
    @( 0..8 | ? { $_ -ne $c} | % { $cell=$solution[$r][$_]; if (is-definite $cell) {$cell} } | sort -Unique )
}

function select-column($solution, $r, $c)
{
    @( 0..8 | ? { $_ -ne $r} | % { $cell=$solution[$_][$c]; if (is-definite $cell) {$cell} } | sort -Unique )
}

function select-block($solution, $r, $c,$size=3)
{
    [int]$br = [Math]::Floor($r/$size) * $size;
    [int]$bc = [Math]::Floor($c/$size) * $size;
    @(
        enumerate-indices $br $size $bc $size |
        ? { -not (($_.R -eq $r) -and ($_.C -eq $c)) } |
        % { $cell=$solution[$_.R][$_.C]; if (is-definite $cell) {$cell} } |
        sort -Unique
    )
}

It took a lot of work before I ended up here but the final result is quite good I think. Pipelining and filtering are powerful concepts.

The utility method compare-arrays is needed since $a –eq $b does not do the right thing (I guess it implements referential equality). I add the implementation here since it might be useful in other contexts:

function compare-arrays($a, $b)
{
    $(Compare-Object $a $b) -eq $null
}

That’s about it. I would not say that it was an all pleasant journey but I did it and the final result was okay I think. Not surprisingly, powershell seems to handle simpler scripting tasks very well but when it comes to more complex programming exercises like this, other languages like C# and #F, are preferable. Also, I should add that the performance of the solver is a magnitude less than its F# and C# counterparts. This brings me back to the initial question; why would someone implement a sudoku solver in powershell?

Advertisements
Categories: Uncategorized

Powershell resources

September 16, 2010 Leave a comment

Three useful powershell resources:

  • PowerGUI ships with a free script editor that provides, among other things, good intellisense. It is a bit slow to start but it is worth waiting for.
  • Powershell Community Extensions “is aimed at providing a widely useful set of additional cmdlets, providers, aliases, filters, functions and scripts for Windows PowerShell that members of the community have expressed interest in.” Very handy – I like the less and the tail commandlets.
  • Powershell.com – “The community for powershell people”. Provides the free Master-Powershell book by Tobias Weltner.

Edit: A PowerGUI visual studio add-in also exists (requires lastest version of PowerGUI).

Categories: Uncategorized

More on sudoku solvers

September 9, 2010 Leave a comment

Fabulous Adventures In Coding by Eric Lippert is a good blog which I check out sometimes. I went there today, searching for some new or undiscovered entries. Did I find something? Oh, yeah. Under the title Graph Colouring, Part Five Eric had hidden a sudoko solver that was based on graph theory. A very different approach from mine indeed. Cool!

Categories: Uncategorized