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] ] }
      }

  def updates = -1
  while (updates != 0) {
    updates = 0
    updates += reduce(grid)
    updates += uniques(grid)
  }

  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 answer = 0

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

sudoku_text.eachWithIndex { line, idx ->
  if (line.startsWith("Grid")) {
    answer += solve(sudoku_text[idx+1..idx+9])
  }
}

Being one to tinker, I made a few more enhancements and got the runtime down to 1.52 seconds with all but two grids, #7 and #50, being solved entirely by logic. It soon got to a point of dimishing returns though. The additional logic was taking just about as long to run as just calling the recursive solver with the increased number of completed cells.

Conclusion

Not the neatest of solutions, but reasonable interesting. I made use of a lot of Groovy listops here which probably impacted performance unduly, but was otherwise easy to work with. It could have easily been done just using a 100% Java version of the recursive solution without any “clever” logic being required. (Indeed such an implementation, using an int array rather than lists, runs in 0.18 seconds…though not really a direct comparison that’s 100+ times faster.)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: