## Project Euler Problem #96

### June 14, 2010

Read the details of the problem here

Summary

Devise an algorithm for solving Su Doku puzzles.

Solution

I kicked this one off with a straightforward list-based recursive solution but couldn’t get the time down below around 36 seconds using solely this approach. I managed to get it down to 27 seconds using an array for representing the grid and lists just for validity checking but I really needed an algorithmic fix to get the time down significantly. (recurse() calls = 2,842,877 (100%).)

At this point I did consider whether I should jump to a full-blown OO solution and model the grid, cells and row/column/subgrid structures appropriately. Although this would have probably led to much neater solution, it seemed overkill for this problem. I just ploughed ahead with the idea of putting in the minimum function to get the problem answered. After all, this was a programming, rather than a maths, problem.

I initially inserted a simple reduction routine that kept iterating through the grid, reducing the eligible entries for each cell (which I had to add when setting the grid up) based on the contents of the row, column and subgrid that the cell belongs to. That cost only 300 ms or so, was sufficient to solve 12/50 puzzles directly (which meant that the recusive routine was never used) and dropped the overall runtime down to 22.8 seconds. So nearly there. (recurse() calls = 1,680,969 (59%). Cells completed by logic: 718.)

I then added a routine, uniques(), that checked just the rows for cells that had a missing number in only one location. If such a number was found the number would be entered in the appropriate cell. As it was only working on a row-by-row basis it didn’t need to handle updates of the eligible lists for affected cells, leaving that operation to the interleaved  reduce() function (as above).

I did consider making these functions recursive themselves but it seemed overcomplicated. Instead, I just combined these two routines such they kept on being called until they found no potential updates.

Adding the uniques() function cost another 300 ms or so, but managed to solve 23/50 of the puzzles completely (which I thought was quite amazing given the simplicity of the algorithm) and reduced the overall runtime to 3.3 seconds as many more of the missing cells had been filled in before the recursive search was called so it then had a lot less work to do. Doubling the number of cells resolved by logic dropped the recursive effort by an order of magnitude. (recurse() calls = 194,793 (7%). Cells completed by logic: 1,388.)

Unfortunately, all this makes the code a little too long…even in Groovy.

```def recurse(grid, r, c) {
if (grid[r][c][0] != 0) {
if (( r == 8 ) && ( c == 8 )) return true
def (r1, c1) = ( c == 8 ) ? [ r + 1, 0 ] : [ r, c + 1 ]
return recurse(grid, r1, c1)
}

def unavail = used_numbers(grid, r, c)

for (i in 1..9) {
if (unavail.contains(i)) continue
grid[r][c][0] = i
if (recurse(grid, r, c)) return true
}

grid[r][c][0] = 0
return false
}

def used_numbers(grid, r, c) {
def used = [] as Set
for (i in 0..8) {
used << grid[r][i][0]
used << grid[i][c][0]
}
def (gr, gc) = [ 3 * r.intdiv(3), 3 * c.intdiv(3) ]
for (y in gr..gr+2) {
for (x in gc..gc+2) {
used << grid[y][x][0]
}
}
used
}

def reduce(grid) {
def updated = true
def count = 0
while (updated) {
updated = false
grid.eachWithIndex { row, y ->
row.eachWithIndex { cell, x ->
if (cell[0] == 0) {
cell[1] -= used_numbers(grid, y, x)
if (cell[1].size() == 1) {
cell[0] = cell[1][0]
( updated, count ) = [ true, count + 1 ]
}
}
}
}
}
count
}

def uniques(grid) {
def count = 0
grid.each { row ->
def uniq =
row.findAll { it[0] == 0 }
.collect { it[1] }
.flatten()
.groupBy { it }
.findAll { it.value.size() == 1 }
.keySet()

uniq.each { v ->
def cell = row.find { it[1].contains(v) }
cell[0] = v
cell[1] = [v]
count++
}
}
count
}

def solve(lines) {
def grid =
lines.collect { line ->
line.collect {
def v = it.toInteger()
[ v, v == 0 ? (1..9).toList() : [v] ] }
}

}

if ((0..2).any { grid[0][it][0] == 0 }) recurse(grid, 0, 0)

grid[0][0..2].inject(0) { p, v -> p * 10 + v[0] }
}

def sudoku_text =
new File("euler_p96_sudoku.txt").text.split("\r\n")

sudoku_text.eachWithIndex { line, idx ->
if (line.startsWith("Grid")) {