This post originated from an RSS feed registered with Ruby Buzz by Laurent Julliard. Original Post: YASS (yet another Sudoku solver) Feed Title: Laurent Julliard Feed URL: http://www.moldus.org/blog/xml/rss/feed.xml Feed Description: Eljay's blog Latest Ruby Buzz Posts Latest Ruby Buzz Posts by Laurent Julliard Latest Posts From Laurent Julliard

The other day I explained my son what recursive programming is and as he is a sudoku addict I put together a few lines of Ruby code to show him how it applies to the sudoku game. See below (I am aware there are tons of other - and more clever - sudoku solver around!). Comments are welcome.

The soduko grid given as an example is reported on sudoku.com as the most difficult sudoku to solve with a unique solution. Still it doesn't take much time to crack ( ~ 4 sec on my 1.8 GhZ Pentium)

require 'benchmark'

class SudokuGrid

  def initialize(grid)
    raise "Invalid Suduku grid" if grid.class != Array || grid.size != 81
    @grid = grid.dup
  end

  def display
    for r in 0..8
      puts((@grid[r*9..r*9+8].collect { |n| n.nil? ? '-' : n }).join(' '))
    end
  end

  def solve
    empty_idx = @grid.index(nil)
    if empty_idx.nil?
      puts "Solution found!!!"
      self.display
    else
      choices = _find_possible_choices(empty_idx)
      choices.each do |c|
        @grid[empty_idx] = c
        SudokuGrid.new(@grid).solve
      end
    end
  end

  private

  def _nb_in_column(idx)
    col = _idx_to_col(idx)
    nb_in_column = []
    for i in 0..8
      nb_in_column << @grid[i*9+col] unless @grid[i*9+col].nil?
    end
    return nb_in_column
  end

  def _nb_in_row(idx)
    row = _idx_to_row(idx)
    nb_in_row = []
    for i in 0..8
      nb_in_row << @grid[i+row*9] unless @grid[i+row*9].nil?
    end
    return nb_in_row
  end

  def _nb_in_square(idx)
    row = (_idx_to_row(idx) / 3)*3 # first column of square
    col = (_idx_to_col(idx) / 3)*3 # first row of square
    nb_in_square = []
    for r in 0..2
      for c in 0..2
        square_idx = _row_col_to_idx(row+r,col+c)
        nb_in_square << @grid[square_idx] unless @grid[square_idx].nil?
      end
    end
    return nb_in_square
  end

  def _idx_to_row(idx)
    idx / 9
  end

  def _idx_to_col(idx)
    idx % 9
  end

  def _row_col_to_idx(row,col)
    row*9+col
  end

  def _find_possible_choices(idx)
    [1,2,3,4,5,6,7,8,9] - (_nb_in_row(idx) | _nb_in_column(idx) | _nb_in_square(idx))
  end

end


if $0 == __FILE__

  grid_to_solve = [nil,nil,nil,nil,  7,nil,  9,  4,nil,
                   nil,  7,nil,nil,  9,nil,nil,nil,  5,
                     3,nil,nil,nil,nil,  5,nil,  7,nil,
                   nil,  8,  7,  4,nil,nil,  1,nil,nil,
                     4,  6,  3,nil,nil,nil,nil,nil,nil,
                   nil,nil,nil,nil,nil,  7,nil,  8,nil,
                     8,nil,nil,  7,nil,nil,nil,nil,nil,
                     7,nil,nil,nil,nil,nil,nil,  2,  8,
                   nil,  5,nil,  2,  6,  8,nil,nil,nil]

  grid = SudokuGrid.new(grid_to_solve)
  puts "Solving..."
  grid.display
  puts "-"*40
  tms = Benchmark::measure { grid.solve }
  puts "Time to solve the grid: #{tms.format('%t')} sec"