really stupid backtracking sudoku solver

readme.md

See original discussion: http://www.ruby-forum.com/topic/55723

excerpt from original (2006-02-23)

c++ code: 0.33 seconds ruby code: 27.6 seconds

mri 1.9.3 (2012-10-16)

ruby code: 2.3 seconds

mri 2.0.0 (2012-02-27)

ruby code: 1.9 seconds

rubinius 2.0.0dev

ruby code: 7.7 seconds

jruby jruby 1.7.3

ruby code: 3.5 seconds

backtracking-sudoku-solver.rb

=begin
  ruby solver
=end

$count = 0

def valid?(state, x, y)
  # check in col and row
  0.upto(8) do |i|
    return false if i != y and state[x][i] == state[x][y]
    return false if i != x and state[i][y] == state[x][y]
  end

  # check in box
  x_from = (x / 3) * 3
  y_from = (y / 3) * 3
  x_from.upto(x_from + 2) do |xx|
    y_from.upto(y_from + 2) do |yy|
      return false if (xx != x or yy != y) and state[xx][yy] == state[x][y]
    end
  end

  true
end



def next_state(state, x, y)
  $count = $count + 1
  y = 0 and x = x + 1 if y == 9
  return true if x == 9

  unless state[x][y].zero?
    return false unless valid?(state, x, y)
    return next_state(state, x, y + 1)
  else
    1.upto(9) do |i|  
    state[x][y] = i
      return true if valid?(state, x, y) and next_state(state, x, y + 1)
    end
  end
  
  state[x][y] = 0
  false
end


## MAIN ##

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

start_time = Time.new

if next_state(start, 0, 0)
  puts "time elapsed: #{Time.new - start_time} sec."
  puts "count: #{$count}"
  start.each do |val|
    puts val.join(" ")
  end
else
  puts "Not solveable!"
end