Code Retreat - Sudoku

Dammit, Dann, this is getting to be a habit.

I haven't gotten to the bottom of the squares problem yet, and yesterday was the monthly Toronto Code Retreat. Which means my time is effectively up thanks to this new problem we're being handed. I'm sure there's a canonical, three-line solution out there somewhere, but I didn't want to read up on it until after the event, so I'm thinking at this from first principles. As a result, it won't be pretty or optimized.

The Problem

Near as I can tell, Sudoku is a Set problem. This isn't how I first heard the rules described, but it fits. A solved Sudoku board is one where

• each number is filled in
• each row is a set
• each column is a set
• each disjoint nxn square is a set (where n is the square root of the board size)

we'll call this "The Sudoku Property"

Now there's actually two problems; one is generating boards and one is solving boards. Solving seems to be pretty straightforward:

1. take a board
2. optionally, fill in all obvious squares until there are no more (an obvious square is one where only one legal move exists)
3. for each blank square, try each possibility

If it can't be done, you've got an unsolvable board. If it can, return the first solution you find[1]. That seems to be that.

Generating is a bit of a different story. The naive solution is to generate a bunch of numbers and place them onto a board such that they respect TSP. Essentially, we're solving an empty board by starting with some random seeds. It really seems like this should work, but I can't convince myself that placing a number in an empty square while respecting the TSP will certainly avoid generating impossible boards. That is, an otherwise valid board which contains one or more empty squares whose set of possibilities is the empty set. It might be a better idea to start with nine sets and perform some sort transformation on it until we get something that respects TSP, rather than building it up piecemeal.

The Event

We did this pretty casually. The problem as presented was to solve boards generated by this site, and not bother with the generation side of things. In practice, no group ever got to the point of a general brute-force Sudoku solver. Three groups managed to solve obvious boards (ones where it's possible to find a complete solution without guessing), and one managed to hook together a bogosort-style solution that could, in principle, if we left it running for a few years, solve an arbitrary 9x9 Sudoku board.

We went the usual three sessions, and I did my usual and used a different language each time. First up, we had a mostly-ideation session in which we ostensibly worked in Python. The only snippet I've got left over from that is

def makeBoard(regionWidth):
    side = regionWidth * regionWidth
    return [[0 for x in xrange(side)] for y in xrange(side)]

sample = [[0, 7, 1, 4, 0, 0, 0, 0, 5],
          [0, 0, 0, 0, 5, 0, 0, 8, 0],
          [0, 0, 3, 9, 0, 7, 6, 0, 0],
          [0, 0, 0, 0, 0, 1, 0, 0, 0],
          [0, 9, 0, 8, 0, 6, 0, 0, 3],
          [0, 0, 0, 0, 0, 0, 8, 2, 0],
          [0, 6, 0, 0, 4, 0, 7, 0, 8],
          [3, 0, 0, 0, 0, 0, 0, 9, 0],
          [0, 0, 0, 0, 8, 5, 0, 0, 0]]

def placements(board, n):
    """Return list of coords where `n` is a legal placement."""
    emptyRows = [i for i, row in enumerate(board) if not n in row]
    res = []
    for i in emptyRows:
        for j, col in enumerate(board[i]):
            if col == 0: res.append((i, j))
    return res

The idea would be to get a function which takes a board and an n, and finds out what the possible placements of n are. I'm not entirely sure how we would have proceeded if this ended up working; I think we'd have to hope really hard that at least one of the digits has only one possible position, which doesn't sound terribly likely in general. The fully implemented version of that function would also check for column and block presences, rather than just filtering rows poorly.

For round two, I got into a group of three with two people who wanted to see Haskell in action. So, after some type-system snafus, we did this:

module Sudoku where

import Data.Set (Set(..), fromList, union, difference)
import Data.List (genericIndex, genericTake)

type Board = [[Int]]

sample :: Board
sample = [[0, 7, 1, 4, 0, 0, 0, 0, 5],
          [0, 0, 0, 0, 5, 0, 0, 8, 0],
          [0, 0, 3, 9, 0, 7, 6, 0, 0],
          [0, 0, 0, 0, 0, 1, 0, 0, 0],
          [0, 9, 0, 8, 0, 6, 0, 0, 3],
          [0, 0, 0, 0, 0, 0, 8, 2, 0],
          [0, 6, 0, 0, 4, 0, 7, 0, 8],
          [3, 0, 0, 0, 0, 0, 0, 9, 0],
          [0, 0, 0, 0, 8, 5, 0, 0, 0]]

row :: Board -> (Int, Int) -> Set Int
row board (x, y) = fromList $ genericIndex board y

col :: Board -> (Int, Int) -> Set Int
col board (x, y) = fromList $ map (flip genericIndex x) board

origin :: Int -> Int
-- origin n = 3 * fromIntegral $ floor $ n / 3
origin n
  | 3 > n = 0
  | 6 > n = 3
  | otherwise = 6

block :: Board -> (Int, Int) -> Set Int
block board (x, y) = fromList . concat . map (genericTake blockSize . drop ox) $ genericTake blockSize $ drop oy board
  where blockSize = 3
        ox = origin x
        oy = origin y
        
possibilities :: Board -> (Int, Int) -> Set Int
possibilities board (x, y) = difference (fromList [1..9]) b
  where a = union (row board (x, y)) $ col board (x, y)
        b = union a $ block board (x, y)

...which is also ugly as fuck. Let me zoom into two particular pieces for you

origin :: Int -> Int
-- origin n = 3 * fromIntegral $ floor $ n / 3
origin n
  | 3 > n = 0
  | 6 > n = 3
  | otherwise = 6

That commented line is what we wanted to do initially. Actually, what we wanted was just blockSize * (floor $ n/blockSize), except that Ints apparently don't derive RealFrac? I don't know what the actual problem there is, and I'll likely toss the question up to SO later, but at the time, we went with the ugly, 9x9-specific, guard-based approach.

block :: Board -> (Int, Int) -> Set Int
block board (x, y) = fromList . concat . map (genericTake blockSize . drop ox) $ genericTake blockSize $ drop oy board
  where blockSize = 3
        ox = origin x
        oy = origin y

Note that blockSize is specified as 3. Which means that this function is also specific to 9x9 Sudoku boards. We went this route for the same reasons as before; the type system doesn't like it when you try to use fromIntegral . sqrt $ length board for some reason, and we didn't have enough time left to figure out what type annotations we'd need to convince GHCi that yes, this is really what we mean.

We also didn't really have enough time in one 40-minute session to write solve, and chat about Haskell and try to form theories about the errors we were seeing, but it's a reasonable-if-rushed implementation of the approach I was assuming we'd use.

The last session, my partner and I decided to have some fun with JavaScript. Except neither of us had node installed standalone, so we ended up using the Chromium JS console. Once we loaded up underscore, things went much faster than expected. We managed to put together a solution that works on any valid board size, that could solve boards where it doesn't need to guess.

var sample4x4 = [[1, 0, 3, 0],
                 [0, 4, 0, 2],
                 [0, 3, 4 ,0],
                 [4, 0, 2, 3]];

var sample9x9 = [[0, 7, 1, 4, 0, 0, 0, 0, 5],
                 [0, 0, 0, 0, 5, 0, 0, 8, 0],
                 [0, 0, 3, 9, 0, 7, 6, 0, 0],
                 [0, 0, 0, 0, 0, 1, 0, 0, 0],
                 [0, 9, 0, 8, 0, 6, 0, 0, 3],
                 [0, 0, 0, 0, 0, 0, 8, 2, 0],
                 [0, 6, 0, 0, 4, 0, 7, 0, 8],
                 [3, 0, 0, 0, 0, 0, 0, 9, 0],
                 [0, 0, 0, 0, 8, 5, 0, 0, 0]];

function possibilities (board, x, y) { 
    return _.difference(_.range(1, _.size(board[0]) + 1), 
                        row(board, x, y),
                        col(board, x, y),
                        block(board, x, y))
}

function row(board, x, y) {
    return board[y];
}

function col(board, x, y) {
    return _.map(board, function (row) { row[x] })
}

function block(board, x, y) {
    var blockSize = Math.sqrt(_.size(board[0]))
    var origin = function (n) { 
        return blockSize * Math.floor(n / blockSize)
    }
    var relevantRows = _.take(_.drop(board, origin(y)), blockSize);
    return _.reduce(relevantRows, function (memo, row) { 
        return _.union(memo, _.take(_.drop(row, origin(y)), blockSize)) 
    }, []);
}

function isFilled (board) { 
    return _.every(board, function (row) { _.every(row, function (val) { val != 0; })})
}

function solve(board) {
    if (isFilled(board)) {
        return board;
    } else {
        return solve(_.map(board, function (row, y) { 
            return _.map(row, function (val, x) { 
                var poss = possibilities(board, x, y);
                if (val != 0) {
                    return val;
                } else if ((val == 0) && (_.size(poss) == 1)) {
                    return poss[0];
                } else {
                    console.log("UNSOLVED");
                    return 0;
                }
            })
        }));
    }
}

Easily the most annoying thing about writing quickly in JS after having gotten so used to the functional paradigm is having to return things explicitly. That bugs the crap out of me over in Python-land too, but at least Python makes up for it by saving you from lines like this

                }
            })
        }));
    }
}

I could do the Lisp-esque thing and start writing

                }})}));}}

but doubt anyone would appreciate that.

Further Reading

The Sudoku situation isn't quite as solved as I assumed before reading up on it. The appropriate Rosetta Code page doesn't have any solutions that leave me gobsmacked by elegance the way that the Clojure Game of Life did. Though the Prolog approach looks quite interesting. Also, the Haskellers apparently look at Sudoku-solver-writing as a hobby, so it has its own page over at the Haskell wiki. "Elegant" isn't something I'd say about any of these, but that's probably because my Math level isn't high enough.

The last note I'll leave you on is that brute-forcing apparently isn't the best solution here. Sudoku is an instance of something called the Exact cover problem, and a Marlboro College student named Sam Auciello wrote an implementation of that solution in Python (links to code files at the bottom of that page page). I haven't quite gotten my head around this one yet, and that's probably what I'll be doing with my next few chunklets of spare time.

---

Footnotes

1 - [back] - (If you're doing this functionally and recursively, it seems like it would be fairly straight-forward. Side-effects complicate things slightly since you have to copy your board out at each decision step, or devise some other method of backtracking)