求解数独的程序

soduku.rb

# 一行代表数独实际的一行，而不是一个九宫格
$soduku = [
  [6, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 4, 1, 2, 9, 6, 0, 0, 0],
  [0, 2, 5, 0, 0, 3, 6, 0, 4],
  [0, 3, 0, 6, 7, 5, 8, 0, 0],
  [8, 0, 6, 9, 0, 4, 5, 0, 2],
  [4, 0, 9, 0, 0, 0, 0, 6, 0],
  [7, 9, 0, 0, 6, 8, 0, 2, 0],
  [0, 0, 8, 4, 5, 0, 3, 0, 1],
  [5, 0, 0, 0, 0, 0, 0, 8, 0]
]

def possible_value(i, j)
  complete = (0..9).to_a
  line_possible = complete - $soduku[i]
  column_possible = complete - get_column(j)
  grid_possible = complete - get_grid(which_grid(i, j))
  grid_possible & column_possible & line_possible
end

def solve(i, j)
  if possible_value(i, j).empty?
    false
  else
    $soduku[i][j] = -1
    next_place = find_zero
    $soduku[i][j] = 0
    chances = possible_value(i, j)
    if next_place.nil?
      $soduku[i][j] = chances.first
      win
      true
    else
      result = false
      chances.each do |c|
        $soduku[i][j] = c
        if solve(next_place.first, next_place.last)
          result = true
          break
        else
          $soduku[i][j] = 0
        end
      end
      result
    end
  end
end

def get_column(j)
  $soduku.collect{|f| f[j]}
end

def get_grid(n)
  i = n / 3
  j = n % 3
  $soduku.slice(i * 3, 3).collect{|f| f.slice(j * 3, 3)}.flatten
end

def which_grid(i, j)
  i / 3 * 3 + j / 3
end

def find_zero
  i = $soduku.find_index do |f|
    f.find_index(0)
  end
  if i.nil?
    nil
  else
    j = $soduku[i].find_index(0)
    [i, j]
  end
end

def win
  cn = 0
  $soduku.each do |line|
    cn += 1
    puts "#{line[0]} #{line[1]} #{line[2]} | " + "#{line[3]} #{line[4]} #{line[5]} | " + "#{line[6]} #{line[7]} #{line[8]}"
    if cn == 3 or cn == 6
      puts "-" * 21
    end
  end
end

start = find_zero
unless solve(start.first, start.last)
  puts "No solution."
end