Skip to content

Instantly share code, notes, and snippets.

@jimweirich
Created January 2, 2009 15:19
Show Gist options
  • Save jimweirich/42562 to your computer and use it in GitHub Desktop.
Save jimweirich/42562 to your computer and use it in GitHub Desktop.
# http://www.websudoku.com/?level=4&set_id=470872047
..53.694.
.3.1....6
.......3.
7..9.....
.1..3..2.
.....2..7
.6.......
8....7.5.
.436.81..
# http://www.websudoku.com/?level=2&set_id=3350218628
.4...7.3.
..85..1..
.15.3..9.
5...7.21.
..6...8..
.81.6...9
.2..4.57.
..7..29..
.5.7...8.
#!/usr/bin/env ruby
require 'set'
class Cell
attr_reader :number
OneThruNine = Set[*1..9]
def initialize(name="unamed")
@name = name
@groups = []
end
def number=(value)
@number = value.nonzero?
end
def available_numbers
if number
Set[]
else
@groups.inject(OneThruNine) { |res, group|
res - group.numbers
}
end
end
def join(group)
@groups << group
end
def to_s
@name
end
def inspect
to_s
end
end
class Group
def initialize
@cells = []
end
def <<(cell)
cell.join(self)
@cells << cell
self
end
def numbers
Set[*@cells.map { |c| c.number }.compact]
end
end
class Board
include Enumerable
def initialize(verbose=nil)
@verbose = verbose
@cells = (0...81).map { |i|
Cell.new("C#{(i/9)+1}#{(i%9)+1}")
}
define_groups
end
def parse(string)
numbers = string.gsub(/^#.*$/, '').gsub(/[\r\n\t]/, '').
split(//).map { |n| n.to_i }
each do |cell|
cell.number = numbers.shift
end
self
end
def each
@cells.each do |cell|
yield cell
end
end
def solved?
all? { |cell| cell.number }
end
def stuck?
any? { |cell| cell.number.nil? && cell.available_numbers.size == 0 }
end
def to_s
encoding.
gsub(/.../, "\\0 ").
gsub(/.{12}/, "\\0\n").
gsub(/.{39}/m, "\\0\n").
gsub(/[\d.]/, "\\0 ")
end
def inspect
"<Board #{encoding}>"
end
def encoding
map { |cell| cell.number || "." }.join
end
def solve
alternatives = []
while true
solve_easy_squares
break if solved?
if stuck?
fail "No Solution Found" if alternatives.empty?
puts "Backtracking (#{alternatives.size})" if @verbose
guess(alternatives)
else
cell = find_candidate_for_guessing
remember_alternatives(cell, alternatives)
guess(alternatives)
end
end
end
private
def solve_easy_squares
while solve_one_easy_square
end
end
def solve_one_easy_square
each do |cell|
an = cell.available_numbers
if an.size == 1
puts "Put #{an.to_a.first} at (#{cell})" if @verbose
cell.number = an.to_a.first
return true
end
end
return false
end
def find_candidate_for_guessing
cells_without_numbers.sort_by { |cell|
[cell.available_numbers.size, to_s]
}.first
end
def cells_without_numbers
to_a.reject { |cell| cell.number }
end
def remember_alternatives(cell, alternatives)
cell.available_numbers.each do |n|
alternatives.push([encoding, cell, n])
end
end
def guess(alternatives)
state, cell, number = alternatives.pop
parse(state)
puts "Guessing #{number} at #{cell}" if @verbose
cell.number = number
end
def define_groups
define_columns
define_rows
define_blocks
end
def define_rows
(0..8).each do |r|
define_group(r..r, 0..8)
end
end
def define_columns
(0..8).each do |c|
define_group(0..8, c..c)
end
end
def define_blocks
[(0..2), (3..5), (6..8)].each do |rrange|
[(0..2), (3..5), (6..8)].each do |crange|
define_group(rrange, crange)
end
end
end
def define_group(row_range, col_range)
g = Group.new
row_range.each do |r|
col_range.each do |c|
g << @cells[r*9 + c]
end
end
end
end
if __FILE__ == $0 then
def solve(string)
board = Board.new(true).parse(string)
puts board
board.solve
puts
puts board
puts
end
if ARGV.empty?
puts "Usage: ruby sudoku.rb sud-files..."
exit
end
ARGV.each do |fn|
puts "Solving #{fn} ----------------------------------------------"
open(fn) do |f|
solve(f.read)
end
end
end
require 'rubygems'
require 'test/unit'
require 'shoulda'
require 'sudoku'
class CellTest < Test::Unit::TestCase
def create_group_with(cell, *numbers)
g = Group.new
g << cell
numbers.each do |n|
c = Cell.new
c.number = n
g << c
end
g
end
context 'a cell' do
setup do
@cell = Cell.new("C25")
end
should 'know its name' do
assert_equal "C25", @cell.to_s
end
should 'initially have no number' do
assert_nil @cell.number
end
should 'be able to set number' do
@cell.number = 4
assert_equal 4, @cell.number
end
should 'accept a zero as no number' do
@cell.number = 0
assert_nil @cell.number
end
should 'report all numbers are available' do
assert_equal( Set[*(1..9)], @cell.available_numbers )
end
context 'within a group' do
setup do
@group = create_group_with(@cell, 3, 4, 5)
end
should 'report available numbers not in the group' do
assert_equal Set[1, 2, 6, 7, 8, 9], @cell.available_numbers
end
should 'report no available numbers if a number has been assigned' do
@cell.number = 6
assert_equal Set[], @cell.available_numbers
end
end
end
end
class GroupTest < Test::Unit::TestCase
context 'a group of cells' do
setup do
@group = Group.new
end
should 'exist' do
assert_not_nil @group
end
context 'with cells' do
setup do
@cells = (1..10).map { |i| Cell.new("C#{i}") }
@cells.each do |c| @group << c end
end
should 'give a list of numbers' do
assert_equal Set[], @group.numbers
end
context 'with some numbers' do
setup do
@cells[0].number = 3
@cells[3].number = 6
end
should 'give a list of the remaining missing numbers' do
assert_equal [3, 6], @group.numbers.sort
end
end
end
end
end
class BoardTest < Test::Unit::TestCase
Wiki =
"53 7 " +
"6 195 " +
" 98 6 " +
"8 6 3" +
"4 8 3 1" +
"7 2 6" +
" 6 28 " +
" 419 5" +
" 8 79"
Medium =
" 4 7 3 " +
" 85 1 " +
" 15 3 9 " +
"5 7 21 " +
" 6 8 " +
" 81 6 9" +
" 2 4 57 " +
" 7 29 " +
" 5 7 8 "
Evil =
" 53 694 " +
" 3 1 6" +
" 3 " +
"7 9 " +
" 1 3 2 " +
" 2 7" +
" 6 " +
"8 7 5 " +
" 436 81 "
context 'a board' do
setup do
@board = Board.new
end
should 'initially give all 9 numbers for all cells' do
@board.each do |cell|
assert_equal((1..9).to_a, cell.available_numbers.sort)
end
end
should 'parse a string representation of the puzzle' do
@board.parse(Wiki)
assert_equal "5 3 . . 7 . . . . \n" +
"6 . . 1 9 5 . . . \n" +
". 9 8 . . . . 6 . \n\n" +
"8 . . . 6 . . . 3 \n" +
"4 . . 8 . 3 . . 1 \n" +
"7 . . . 2 . . . 6 \n\n" +
". 6 . . . . 2 8 . \n" +
". . . 4 1 9 . . 5 \n" +
". . . . 8 . . 7 9 \n\n",
@board.to_s
end
should 'solve the Wikipedia Puzzle' do
board = Board.new.parse(Wiki)
board.solve
assert board.solved?
assert_equal "534678912672195348198342567" +
"859761423426853791713924856" +
"961537284287419635345286179",
board.encoding
end
should 'solve the Wikipedia Puzzle with DOS line endings' do
board = Board.new.parse(open("wiki_dos.sud") { |f| f.read })
board.solve
assert board.solved?
assert_equal "534678912672195348198342567" +
"859761423426853791713924856" +
"961537284287419635345286179",
board.encoding
end
should 'solve the Medium Puzzle' do
board = Board.new.parse(Medium)
board.solve
assert board.solved?
assert_equal "942187635368594127715236498" +
"593478216476921853281365749" +
"829643571137852964654719382",
board.encoding
end
should 'solve the Evil Puzzle' do
board = Board.new.parse(Evil)
board.solve
assert board.solved?
assert_equal "285376941439125786176849235" +
"752981364618734529394562817" +
"567213498821497653943658172",
board.encoding
end
end
end
# http://en.wikipedia.org/wiki/Sudoku
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment