The Artima Developer Community
Sponsored Link

Ruby Buzz Forum
YASS (yet another Sudoku solver)

2 replies on 1 page. Most recent reply: Feb 20, 2007 7:05 PM by Jonathan Demes

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 2 replies on 1 page
Laurent Julliard

Posts: 8
Nickname: eljay
Registered: Feb, 2006

Laurent Julliard, a Ruby hacker
YASS (yet another Sudoku solver) Posted: Feb 15, 2006 4:43 AM
Reply to this message Reply

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

Advertisement

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"

Read: YASS (yet another Sudoku solver)


Jonathan Demes

Posts: 3
Nickname: jon12
Registered: Aug, 2006

Re: YASS (yet another Sudoku solver) Posted: Aug 22, 2006 6:15 PM
Reply to this message Reply
Not bad! My Sudoku Solver solved it in 6 milliseconds and took 19 ms to verify that the solution is unique. It is written in Java and it uses backtracking with optimized guessing. It is online and it is free. You need the java plugin in your browser to use it: http://dj3.electronicbox.net/sudoku/

Here is the hardest Sudoku I found so far, my solver takes 29 millis to solve (and ~100 ms to verify that the solution is unique):
{ 0, 0, 2, 0, 9, 0, 1, 0, 7 },
{ 0, 3, 8, 6, 0, 0, 0, 0, 0 },
{ 4, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 5, 0, 0, 0 },
{ 0, 0, 9, 0, 1, 0, 3, 0, 0 },
{ 0, 0, 0, 4, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 4 },
{ 0, 0, 0, 0, 0, 7, 9, 2, 0 },
{ 8, 0, 6, 0, 3, 0, 7, 0, 0 },

Jonathan Demes

Posts: 3
Nickname: jon12
Registered: Aug, 2006

Good Camel's Sudoku Solver! Posted: Feb 20, 2007 7:05 PM
Reply to this message Reply
Updated :)

Here is a link to a free sudoku solver. No need to download and install anything. All you need is your browser. You'll see, it is very easy to use and very fast. It will also tell you if there are more than one solution for your sudoku.

Here is the link: Good Camel's Sudoku Solver!

Happy Sudoku :)

Flat View: This topic has 2 replies on 1 page
Topic: Writing Google Maps Applications with Rails and Ajax Previous Topic   Next Topic Topic: Bounded space memoization, another new twist

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use