Sudoku solver for Dropquest https://www.dropbox.com/dropquest2011/

sudoku_dropquest.rb

#!/usr/bin/env ruby
# -*- mode: ruby; coding: utf-8-unix -*-

# Sudoku solver for Dropquest
# https://www.dropbox.com/dropquest2011/

require 'pp'

CANDIDATES = 'AFERDOWSI'.split(//)

def is_possible?(row, col, char, field)
  0.upto(8) { |i|
    return false if field[row][i] == char
    return false if field[i][col] == char
  }

  # Check 3x3 region
  r0 = row - row % 3
  c0 = col - col % 3
  r0.upto(r0 + 2) { |r|
    c0.upto(c0 + 2) { |c|
      return false if field[r][c] == char
    }
  }
  true
end

def is_complete?(field)
  field.join !~ /\s/
end

def next_point(r0, c0, field)
  c0.upto(8) { |c|
    return [r0, c] if field[r0][c] == ' '
  }
  (r0 + 1).upto(8) { |r|
    0.upto(8) { |c|
      return [r, c] if field[r][c] == ' '
    }
  }
  throw Error
end

def solve(r, c, field)
  next_r, next_c = next_point(r, c, field)
  CANDIDATES.each { |x|
    next unless is_possible?(next_r, next_c, x, field)
    next_field = Marshal.load(Marshal.dump(field)) # deep copy
    next_field[next_r][next_c] = x
    return next_field if is_complete?(next_field)
    result = solve(next_r, next_c, next_field)
    return result unless result.nil?
  }
  nil
end

field = [' WI  D  A',
         'D F W  O ',
         'RS       ',
         '  DF A  O',
         ' AO   DR ',
         'S  E OA  ',
         '       AW',
         ' F  A O I',
         'A  W  RF '].map { |s| s.split(//) }

pp solve(0, 0, field)