Simple Sudoku Solver with backtracking

peter-norvig_11-hardest-puzzles.txt

850002400720000009004000000000107002305000900040000000000080070017000000000036040
005300000800000020070010500400005300010070006003200080060500009004000030000009700
120040000005069010009000500000000070700052090030000002090600050400900801003000904
000570030100000020700023400000080004007004000490000605042000300000700900001800000
700152300000000920000300000100004708000000060000000000009000506040907000800006010
100007090030020008009600500005300900010080002600004000300000010040000007007000300
100034080000800500004060021018000000300102006000000810520070900006009000090640002
000920000006803000190070006230040100001000700008030029700080091000507200000064000
060504030100090008000000000900050006040602070700040005000000000400080001050203040
700000400020070080003008079900500300060020090001097006000300900030040060009001035
000070020800000006010205000905400008000000000300008501000302080400000009070060000

sudoku_solver.rb

class Sudoku
  attr_accessor :board

  def initialize(board_string)
    @board_string = board_string.split("")
    @board = Array.new(9) { Array.new(9) }

    build_board
    @boxes = [[[0,0],[1,0],[2,0],[0,1],[1,1],[2,1],[0,2],[1,2],[2,2]],
              [[3,0],[4,0],[5,0],[3,1],[4,1],[5,1],[3,2],[4,2],[5,2]],
              [[6,0],[7,0],[8,0],[6,1],[7,1],[8,1],[6,2],[7,2],[8,2]],
              [[0,3],[1,3],[2,3],[0,4],[1,4],[2,4],[0,5],[1,5],[2,5]],
              [[3,3],[4,3],[5,3],[3,4],[4,4],[5,4],[3,5],[4,5],[5,5]],
              [[6,3],[7,3],[8,3],[6,4],[7,4],[8,4],[6,5],[7,5],[8,5]],
              [[0,6],[1,6],[2,6],[0,7],[1,7],[2,7],[0,8],[1,8],[2,8]],
              [[3,6],[4,6],[5,6],[3,7],[4,7],[5,7],[3,8],[4,8],[5,8]],
              [[6,6],[7,6],[8,6],[6,7],[7,7],[8,7],[6,8],[7,8],[8,8]]]
  end

  def valid_move? num, x, y
    return false if in_row? num, x, y
    return false if in_col? num, x, y
    return false if in_box? num, x, y
    true
  end

  def solve! x, y
    if y == 9
      y = 0
      x += 1
    end
    
    return true if x == 9

    if board[x][y] == 0
      (1..9).each do |try|
        board[x][y] = try
        return true if solve!(x,y+1) if valid_move?(try,x,y)
        board[x][y] = 0
      end
    else
      return true if solve! x, y+1
    end
    false
  end

  def build_board
    9.times do |x|
      row = @board_string.shift(9)
      9.times { |y| board[x][y] = row[y].to_i }
    end
  end

  def in_row? num , x, y
    9.times { |index| return true if board[x][index] == num && index != y }
    false
  end

  def in_col? num, x, y
    9.times { |index| return true if @board[index][y] == num && index != x }
    false
  end

  def in_box? num, x, y
    check_box = @boxes.select { |box| box.include?([x,y]) }[0]
    check_box.each { |ix,iy| return true if @board[ix][iy] == num  &&  ix != x && iy != y }
    false
  end

  def to_s
    @board.map { |row| row.join(" ") + "\n" }.join
  end
end

puts "Starting..."
game_start = Time.now
board_string = File.readlines('peter-norvig_11-hardest-puzzles.txt')
board_string.each do |board|
  game = Sudoku.new(board)
  puts "*"*50
  board_start = Time.now
  puts game
  game.solve!(0,0)
  puts "*"*50
  puts game
  puts "Finished that board in #{Time.now - board_start} seconds"
end
puts "Finished in #{Time.now - game_start} seconds"