[QUIZ] Sodoku Solver (#43)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Sodokus are simple number puzzles that often appear in various sources of print.
The puzzle you are given is a 9 x 9 grid of numbers and blanks, that might look
something like this:

+-------+-------+-------+
| _ 6 _ | 1 _ 4 | _ 5 _ |
| _ _ 8 | 3 _ 5 | 6 _ _ |
| 2 _ _ | _ _ _ | _ _ 1 |
+-------+-------+-------+
| 8 _ _ | 4 _ 7 | _ _ 6 |
| _ _ 6 | _ _ _ | 3 _ _ |
| 7 _ _ | 9 _ 1 | _ _ 4 |
+-------+-------+-------+
| 5 _ _ | _ _ _ | _ _ 2 |
| _ _ 7 | 2 _ 6 | 9 _ _ |
| _ 4 _ | 5 _ 8 | _ 7 _ |
+-------+-------+-------+

The task is to fill in the remaining digits (1 through 9 only) such that each
row, column, and 3 x 3 box contains exactly one of each digit. Here's the
solution for the above puzzle:

+-------+-------+-------+
| 9 6 3 | 1 7 4 | 2 5 8 |
| 1 7 8 | 3 2 5 | 6 4 9 |
| 2 5 4 | 6 8 9 | 7 3 1 |
+-------+-------+-------+
| 8 2 1 | 4 3 7 | 5 9 6 |
| 4 9 6 | 8 5 2 | 3 1 7 |
| 7 3 5 | 9 6 1 | 8 2 4 |
+-------+-------+-------+
| 5 8 9 | 7 1 3 | 4 6 2 |
| 3 1 7 | 2 4 6 | 9 8 5 |
| 6 4 2 | 5 9 8 | 1 7 3 |
+-------+-------+-------+

This week's Ruby Quiz is to write a solver that takes the puzzle on STDIN and
prints the solution to STDOUT.

 

[Karl von Laudermann]

Sodokus are simple number puzzles that often appear in various sources of
print.

This week's Ruby Quiz is to write a solver that takes the puzzle on STDIN and
prints the solution to STDOUT.

Heh. I already wrote a Sudoku solver back in May; all I have to do is
change the input/output format a bit to match the quiz example. In the
meantime, here's a harder puzzle to test your programs with:

+-------+-------+-------+
| _ _ 2 | _ _ 5 | _ 7 9 |
| 1 _ 5 | _ _ 3 | _ _ _ |
| _ _ _ | _ _ _ | 6 _ _ |
+-------+-------+-------+
| _ 1 _ | 4 _ _ | 9 _ _ |
| _ 9 _ | _ _ _ | _ 8 _ |
| _ _ 4 | _ _ 9 | _ 1 _ |
+-------+-------+-------+
| _ _ 9 | _ _ _ | _ _ _ |
| _ _ _ | 1 _ _ | 3 _ 6 |
| 6 8 _ | 3 _ _ | 4 _ _ |
+-------+-------+-------+

--
Karl von Laudermann - karlvonl(a)rcn.com - http://www.geocities.com/~karlvonl
#!/usr/bin/env ruby
require "complex";w=39;m=2.0;w.times{|y|w.times{|x|c=Complex.new((m*x/w)-1.5,
(2.0*y/w)-1.0);z=c;e=false;49.times{z=z*z+c;if z.abs>m then e=true;break;end}
print(e ?" ":"@@");puts if x==w-1;}}

 

[Chris Game]

Heh. I already wrote a Sudoku solver back in May; all I have to do
is change the input/output format a bit to match the quiz
example. In the meantime, here's a harder puzzle to test your
programs with:

Why is it harder? If an algorithm works, all solvable puzzles are
the same?


There's a soln on RubyForge somewhere I saw the other day...

 

[Simon Kröger]

Karl von Laudermann wrote:




Why is it harder? If an algorithm works, all solvable puzzles are
the same?

This is true for brute force solving only. If you apply some logic
to cut down the calculation time things gets more interesting.

There's a soln on RubyForge somewhere I saw the other day...

Maybe, but its fun.

To those who try, here is a very neat one:

+-------+-------+-------+
| _ _ _ | _ 7 _ | 9 4 _ |
| _ 7 _ | _ 9 _ | _ _ 5 |
| 3 _ _ | _ _ 5 | _ 7 _ |
+-------+-------+-------+
| _ 8 7 | 4 _ _ | 1 _ _ |
| 4 6 3 | _ 8 _ | _ _ _ |
| _ _ _ | _ _ 7 | _ 8 _ |
+-------+-------+-------+
| 8 _ _ | 7 _ _ | _ _ _ |
| 7 _ _ | _ _ _ | _ 2 8 |
| _ 5 _ | 2 6 8 | _ _ _ |
+-------+-------+-------+

I can't confirm thats its solveable (yet)

cheers

Simon

 

[Karl von Laudermann]

Why is it harder? If an algorithm works, all solvable puzzles are
the same?

Well, it's harder for a human to solve; I forget where I snagged it
from, but it was labelled as "really hard". And it took my solver
program a whole 7 seconds to solve it (on my old computer), while other
examples I tested it with took less than a second to solve. So it's
probably useful for profiling your program's performance.

Ok, here's one that's *not* solvable, useful for making sure that your
program can handle such a case gracefully:

+-------+-------+-------+
| _ _ 1 | _ 2 _ | 8 _ _ |
| _ 7 _ | 3 1 _ | _ 9 _ |
| 3 _ _ | _ 4 5 | _ _ 7 |
+-------+-------+-------+
| _ 9 _ | 7 _ _ | 5 _ _ |
| _ 4 2 | _ 5 _ | 1 3 _ |
| _ _ 3 | _ _ 9 | _ 4 _ |
+-------+-------+-------+
| 2 _ _ | 5 7 _ | _ _ 4 |
| _ 3 _ | _ 9 1 | _ 6 _ |
| _ _ 4 | _ _ _ | 3 _ _ |
+-------+-------+-------+

--
Karl von Laudermann - karlvonl(a)rcn.com - http://www.geocities.com/~karlvonl
#!/usr/bin/env ruby
require "complex";w=39;m=2.0;w.times{|y|w.times{|x|c=Complex.new((m*x/w)-1.5,
(2.0*y/w)-1.0);z=c;e=false;49.times{z=z*z+c;if z.abs>m then e=true;break;end}
print(e ?" ":"@@");puts if x==w-1;}}

 

[Mohit Muthanna]

I too did one back in April - and have modfied it to
read (and write) the current intput format.
=20
Here's the puzzle that takes a *long* time - I don't
remember if it's even solvable, but my solver has
been running for over an hour so far ...
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| 7 _ _ | _ 8 _ | 3 _ _ |
| _ _ _ | 7 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ 9 | _ 1 _ | _ _ _ |
| _ _ _ | _ _ 7 | _ _ _ |
+-------+-------+-------+
| _ _ 1 | _ _ 8 | _ 2 _ |
| _ _ _ | _ 2 6 | _ _ 1 |
| _ _ _ | 3 _ 5 | _ _ _ |
+-------+-------+-------+

Here's what my solver spewed out for this:

Problem:
1 2 3 4 5 6 7 8 9
+--------------------------
1 | _, _, _, _, _, _, _, _, _
2 | 7, _, _, _, 8, _, 3, _, _
3 | _, _, _, _, _, _, _, _, _
4 | _, _, 9, _, 1, _, _, _, _
5 | _, _, _, _, _, 7, _, _, _
6 | _, _, 1, _, _, 8, _, 2, _
7 | _, _, _, _, 2, 6, _, _, 1
8 | _, _, _, 3, _, 5, _, _, _
9 | _, _, _, _, _, _, _, _, _
Filled: 14 / 81

Solution:
1 2 3 4 5 6 7 8 9
+--------------------------
1 | 1, 2, 3, 4, 5, 9, 6, 7, 8
2 | 7, 4, 5, 6, 8, 1, 3, 9, 2
3 | 6, 9, 8, 7, 3, 2, 1, 4, 5
4 | 2, 6, 9, 5, 1, 3, 7, 8, 4
5 | 5, 8, 4, 2, 6, 7, 9, 1, 3
6 | 3, 7, 1, 9, 4, 8, 5, 2, 6
7 | 9, 3, 7, 8, 2, 6, 4, 5, 1
8 | 4, 1, 2, 3, 7, 5, 8, 6, 9
9 | 8, 5, 6, 1, 9, 4, 2, 3, 7
Filled: 81 / 81

real 0m6.210s
user 0m6.203s
sys 0m0.006s

------


At 6 seconds... it really needed to crunch.

Mohit.

--=20
Mohit Muthanna [mohit (at) muthanna (uhuh) com]
"There are 10 types of people. Those who understand binary, and those
who don't."

 

[Dennis Ranke]

[...]
Here's the puzzle that takes a *long* time - I don't
remember if it's even solvable, but my solver has
been running for over an hour so far ...
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| 7 _ _ | _ 8 _ | 3 _ _ |
| _ _ _ | 7 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ 9 | _ 1 _ | _ _ _ |
| _ _ _ | _ _ 7 | _ _ _ |
+-------+-------+-------+
| _ _ 1 | _ _ 8 | _ 2 _ |
| _ _ _ | _ 2 6 | _ _ 1 |
| _ _ _ | 3 _ 5 | _ _ _ |
+-------+-------+-------+

Here's what my solver spewed out for this:

Problem:
1 2 3 4 5 6 7 8 9
+--------------------------
1 | _, _, _, _, _, _, _, _, _
2 | 7, _, _, _, 8, _, 3, _, _
3 | _, _, _, _, _, _, _, _, _
4 | _, _, 9, _, 1, _, _, _, _
5 | _, _, _, _, _, 7, _, _, _
6 | _, _, 1, _, _, 8, _, 2, _
7 | _, _, _, _, 2, 6, _, _, 1
8 | _, _, _, 3, _, 5, _, _, _
9 | _, _, _, _, _, _, _, _, _
Filled: 14 / 81

This is missing the third row of the original Problem, which probably
isn't solvable. (At least my solver claims that it isn't after 0.08
seconds of calculation...

Dennis

 

[horndude77]

I figured that participating in the ruby quiz would be a good way to
learn ruby. Here are my results followin what was done by vance.

for i in *.txt; do time ./sudoku.rb < $i; done

+-------+-------+-------+
| 9 6 3 | 1 7 4 | 2 5 8 |
| 1 7 8 | 3 2 5 | 6 4 9 |
| 2 5 4 | 6 8 9 | 7 3 1 |
+-------+-------+-------+
| 8 2 1 | 4 3 7 | 5 9 6 |
| 4 9 6 | 8 5 2 | 3 1 7 |
| 7 3 5 | 9 6 1 | 8 2 4 |
+-------+-------+-------+
| 5 8 9 | 7 1 3 | 4 6 2 |
| 3 1 7 | 2 4 6 | 9 8 5 |
| 6 4 2 | 5 9 8 | 1 7 3 |
+-------+-------+-------+

real 0m0.041s
user 0m0.013s
sys 0m0.007s
+-------+-------+-------+
| 3 6 2 | 8 4 5 | 1 7 9 |
| 1 7 5 | 9 6 3 | 2 4 8 |
| 9 4 8 | 2 1 7 | 6 3 5 |
+-------+-------+-------+
| 7 1 3 | 4 5 8 | 9 6 2 |
| 2 9 6 | 7 3 1 | 5 8 4 |
| 8 5 4 | 6 2 9 | 7 1 3 |
+-------+-------+-------+
| 4 3 9 | 5 7 6 | 8 2 1 |
| 5 2 7 | 1 8 4 | 3 9 6 |
| 6 8 1 | 3 9 2 | 4 5 7 |
+-------+-------+-------+

real 0m0.062s
user 0m0.048s
sys 0m0.003s
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| 7 _ _ | _ 8 _ | 3 _ _ |
| _ _ _ | 7 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ 9 | _ 1 _ | _ _ _ |
| _ _ _ | _ _ 7 | _ _ _ |
+-------+-------+-------+
| _ _ 1 | _ _ 8 | _ 2 _ |
| _ _ _ | _ 2 6 | _ _ 1 |
| _ _ _ | 3 _ 5 | _ _ _ |
+-------+-------+-------+
I can't solve this one

real 0m0.031s
user 0m0.012s
sys 0m0.006s
+-------+-------+-------+
| 4 6 1 | 9 2 7 | 8 5 3 |
| 5 7 _ | 3 1 6 | 4 9 2 |
| 3 2 9 | 8 4 5 | 6 1 7 |
+-------+-------+-------+
| 1 9 8 | 7 3 4 | 5 2 6 |
| 7 4 2 | 6 5 _ | 1 3 9 |
| 6 _ 3 | 1 8 9 | 7 4 _ |
+-------+-------+-------+
| 2 1 6 | 5 7 3 | 9 8 4 |
| 8 3 7 | 4 9 1 | 2 6 5 |
| 9 5 4 | 2 6 8 | 3 7 1 |
+-------+-------+-------+
I can't solve this one

real 0m0.029s
user 0m0.014s
sys 0m0.005s

Should I post my code now or later? It still has a lot of kinks to work
out, but it seems to work pretty well. I'll be back later today to post
it. Thanks!!

-----Horndude77

 

[James Edward Gray II]

Should I post my code now or later?

I always ask that people wait 48 hours from the time on the quiz
message. Thanks.

Looking forward to seeing the solutions though...

James Edward Gray II

 

[Karl von Laudermann]

Ok, I'm pretty sure that it's been over 48 hours, so here's my solution,
sudoku_solve.rb:

#!/usr/bin/env ruby
#
# =Description
#
# Solves a Su Doku puzzle. Prints the solution to stdout.
#
# =Usage
#
# sudoku_solve.rb <puzzle.txt>
#
# puzzle.txt is a text file containing a sudoku puzzle in the following format:
#
# +-------+-------+-------+
# | _ _ 2 | _ _ 5 | _ 7 9 |
# | 1 _ 5 | _ _ 3 | _ _ _ |
# | _ _ _ | _ _ _ | 6 _ _ |
# +-------+-------+-------+
# | _ 1 _ | 4 _ _ | 9 _ _ |
# | _ 9 _ | _ _ _ | _ 8 _ |
# | _ _ 4 | _ _ 9 | _ 1 _ |
# +-------+-------+-------+
# | _ _ 9 | _ _ _ | _ _ _ |
# | _ _ _ | 1 _ _ | 3 _ 6 |
# | 6 8 _ | 3 _ _ | 4 _ _ |
# +-------+-------+-------+
#
# Characters '-', '+', '|', and whitespace are ignored, and thus optional. The
# file just has to have 81 characters that are either numbers or other
# printables besides the above mentioned. Any non-numeric character is
# considered a blank (unsolved) grid entry.
#
# The puzzle can also be passed in via stdin, e.g.:
# cat puzzle.txt | sudoku_solve.rb

require 'rdoc/usage'

#==============================================================================
# ----- Classes -----
#==============================================================================

class UnsolvableException < Exception
end

# Represents one grid space. Holds known value or list of candidate values.
class Space
def initialize(num = nil)
@value = num
@cands = num ? [] : [1, 2, 3, 4, 5, 6, 7, 8, 9]
end

def value() @value end
def value=(val) @value = val; @cands.clear end
def remove_cand(val) @cands.delete(val) end
def cand_size() @cands.size end
def first_cand() @cands[0] end
end

# Represents puzzle grid. Grid has 81 spaces, composing 9 rows, 9 columns, and
# 9 "squares":
#
# Colums
# Spaces 012 345 678
#
# 0 1 2| 3 4 5| 6 7 8 0 | |
# 9 10 11|12 13 14|15 16 17 1 0 | 1 | 2 <- Squares
# 18 19 20|21 22 23|24 25 26 2 | | |
# --------+--------+-------- R ---+---+--- |
# 27 28 29|30 31 32|33 34 35 o 3 | | |
# 36 37 38|39 40 41|42 43 44 w 4 3 | 4 | 5 <----+
# 45 46 47|48 49 50|51 52 53 s 5 | | |
# --------+--------+-------- ---+---+--- |
# 54 55 56|57 58 59|60 61 62 6 | | |
# 63 64 65|66 67 68|69 70 71 7 6 | 7 | 8 <----+
# 72 73 74|75 76 77|78 79 80 8 | |
class Board
# Stores which spaces compose each square
@@squares = []
@@squares[0] = [ 0, 1, 2, 9, 10, 11, 18, 19, 20].freeze
@@squares[1] = [ 3, 4, 5, 12, 13, 14, 21, 22, 23].freeze
@@squares[2] = [ 6, 7, 8, 15, 16, 17, 24, 25, 26].freeze
@@squares[3] = [27, 28, 29, 36, 37, 38, 45, 46, 47].freeze
@@squares[4] = [30, 31, 32, 39, 40, 41, 48, 49, 50].freeze
@@squares[5] = [33, 34, 35, 42, 43, 44, 51, 52, 53].freeze
@@squares[6] = [54, 55, 56, 63, 64, 65, 72, 73, 74].freeze
@@squares[7] = [57, 58, 59, 66, 67, 68, 75, 76, 77].freeze
@@squares[8] = [60, 61, 62, 69, 70, 71, 78, 79, 80].freeze
@@squares.freeze

# Takes a string containing the text of a valid puzzle file as described in
# the Usage comment at the top of this file
def initialize(grid = nil)
@spaces = Array.new(81) { |n| Space.new }

if grid
count = 0
chars = grid.split(//).delete_if { |c| c =~ /[\+\-\|\s]/ }

chars.each do |c|
set(count, c.to_i) if c =~ /\d/
count += 1
break if count == 81
end
end
end

def set(idx, val)
@spaces[idx].value = val
adjust_cands_from(idx)
end

# Remove indicated space's value from candidates of all spaces in its
# row/col/square
def adjust_cands_from(sidx)
val = @spaces[sidx].value

row_each(which_row(sidx)) do |didx|
@spaces[didx].remove_cand(val)
end

col_each(which_col(sidx)) do |didx|
@spaces[didx].remove_cand(val)
end

square_each(which_square(sidx)) do |didx|
@spaces[didx].remove_cand(val)
end
end

# Return number of row/col/square containing the given space index
def which_row(idx) idx / 9 end
def which_col(idx) idx % 9 end

def which_square(idx)
@@squares.each_with_index { |s, n| return n if s.include?(idx) }
end

# Yield each space index in the row/col/square indicated by number
def row_each(row) ((row * 9)...((row + 1) * 9)).each { |n| yield(n) } end
def col_each(col) 9.times { yield(col); col += 9 } end
def square_each(squ) @@squares[squ].each { |n| yield(n) } end

def solved?() @spaces.all? { |sp| sp.value } end

# For each empty space that has only one candidate, set the space's value to
# that candidate and update all related spaces. Repeat process until no
# empty spaces with only one candidate remain
def deduce_all
did = true

while did
did = false

@spaces.each_index do |idx|
sp = @spaces[idx]

raise UnsolvableException if ((!sp.value) && sp.cand_size == 0)
if (sp.cand_size == 1)
sp.value = sp.first_cand
adjust_cands_from(idx)
did = true
end
end
end
end

def to_s
div = "+-------+-------+-------+\n"
ret = "" << div

@spaces.each_index do |idx|
ret << "|" if (idx % 9 == 0)
ret << " " + (@spaces[idx].value || '_').to_s
ret << " |" if (idx % 3 == 2)
ret << "\n" if (idx % 9 == 8)
ret << div if ([26, 53, 80].include?(idx))
end

ret
end

def solve()
# Solve
deduce_all
return if solved?

# Find an unsolved space with the fewest candidate values and store its
# index and first candidate
min_count = nil
test_idx = nil

@spaces.each_with_index do |sp, n|
if !sp.value
if (!min_count) || (sp.cand_size < min_count)
test_idx, min_count = n, sp.cand_size
end
end
end

test_cand = @spaces[test_idx].first_cand

# Solve clone of board in which the value of the space found above is
# set to it's first candidate value
str = ""

@spaces.each_index do |idx|
str << (idx == test_idx ? test_cand.to_s :
(@spaces[idx].value || '_').to_s)
end

b_clone = Board.new(str)

begin
b_clone.solve
initialize(b_clone.to_s) # Take state from clone
rescue UnsolvableException
@spaces[test_idx].remove_cand(test_cand)
solve
end
end
end

#==============================================================================
# ----- Script start -----
#==============================================================================

b_str = ARGF.readlines().join()
board = Board.new(b_str)

begin
board.solve()
puts board.to_s
rescue UnsolvableException
puts "This puzzle has no solution!"
end

--
Karl von Laudermann - karlvonl(a)rcn.com - http://www.geocities.com/~karlvonl
#!/usr/bin/env ruby
require "complex";w=39;m=2.0;w.times{|y|w.times{|x|c=Complex.new((m*x/w)-1.5,
(2.0*y/w)-1.0);z=c;e=false;49.times{z=z*z+c;if z.abs>m then e=true;break;end}
print(e ?" ":"@@");puts if x==w-1;}}

 

[Gavin Kistner]

Here's my (poor) solution. I started out thinking "Hey, that's
easy!", and only when I was done did I realize that my solution
cannot make the guesses necessary to "try out" numbers to fill in
empty spaces to try and progress.

What it does do is solve the puzzle if there's always a simple
logical next step (i.e. at least one row, column, or tile with
exactly one number missing).

I failed the quiz, but feel the need to share my results anyhow
(The board that I load happens to be the Quiz board, with the first
row and third tile filled in just enough for my solver to be able to
handle it.)

module Soduku
class Board
attr_reader :spaces, :tiles, :rows, :cols
def initialize( board_to_load=nil )
@spaces = (0..80).to_a.map{ |i| Space.new }

@rows = []
0.step( 80, 9 ){ |i|
@rows << @spaces[ i..(i+8) ]
}

@cols = []
0.upto( 8 ){ |i|
@cols << col = []
0.step( 80, 9 ){ |j|
col << @spaces[ i+j ]
}
}

@tiles = []
0.step(54,27){ |a|
0.step(6,3){ |b|
@tiles << tile = []
corner = a+b
0.step(18,9){ |row_offset|
0.upto(2){ |col_offset|
tile << @spaces[ corner + row_offset +
col_offset ]
}
}
}
}

if board_to_load
values = board_to_load.scan( /[\d_]/ )
raise "Supplied board does not have 81 distinct
values" unless values.length == 81
values.each_with_index{ |v,i|
@spaces.value = v.to_i if v != '_'
}
end
end

def solve
unsolved_count = 81
iteration = 1
row_solved = {}
col_solved = {}
tile_solved = {}

while unsolved_count > 0 && iteration < 100
puts "Iteration #{iteration}" if $DEBUG
unsolved_count = 81 - @spaces.select{ |s|
s.value }.length
puts "\t#{unsolved_count} spaces unsolved" if $DEBUG

@rows.each_with_index{ |row,i|
unless row_solved
if solve_set( row )
row_solved = true
end
end
}

@cols.each_with_index{ |col,i|
unless col_solved
if solve_set( col )
col_solved = true
end
end
}

@tiles.each_with_index{ |tile,i|
unless tile_solved
if solve_set( tile )
tile_solved = true
end
end
}

iteration += 1
end
end

def synchronize
@spaces.each{ |s| s.synchronize }
end

def to_s
row_sep = "+-------+-------+-------+\n"
out = ''
@spaces.each_with_index{ |s,i|
out << row_sep if i % 27 == 0
out << '| ' if i % 3 == 0
out << s.to_s + ' '
out << "|\n" if i % 9 == 8
}
out << row_sep
out
end

private
def solve_set( spaces )
unknown_spaces = spaces.select{ |s| !s.value }
return true if unknown_spaces.length == 0
known_spaces = spaces - unknown_spaces
known_values = known_spaces.collect{ |s| s.value }
unknown_spaces.each{ |s|
possibles = s.possibles
known_values.each{ |v| possibles.delete( v ) }
s.synchronize
}
# Recheck now that they've all been synchronized
unknown_spaces = spaces.select{ |s| !s.value }
return true if unknown_spaces.length == 0
return false
end

end

class Space
attr_accessor :value, ossibles
def initialize( value=nil )
@possibles = {}
unless @value = value
1.upto(9){ |i| @possibles=true }
end
end
def synchronize
possible_numbers = @possibles.keys
if possible_numbers.length == 1
@value = possible_numbers.first
end
end
def to_s
@value ? @value.to_s : '_'
end
end
end

b = Soduku::Board.new( <<ENDBOARD )
+-------+-------+-------+
| 9 6 3 | 1 7 4 | 2 5 _ |
| _ _ 8 | 3 _ 5 | 6 4 9 |
| 2 _ _ | _ _ _ | 7 _ 1 |
+-------+-------+-------+
| 8 _ _ | 4 _ 7 | _ _ 6 |
| _ _ 6 | _ _ _ | 3 _ _ |
| 7 _ _ | 9 _ 1 | _ _ 4 |
+-------+-------+-------+
| 5 _ _ | _ _ _ | _ _ 2 |
| _ _ 7 | 2 _ 6 | 9 _ _ |
| _ 4 _ | 5 _ 8 | _ 7 _ |
+-------+-------+-------+
ENDBOARD

$DEBUG = true
puts b
b.solve
puts b

 

[horndude77]

Ok, I've seen a couple other solutions posted. Here is my code. I threw
this together pretty quick.

I start out by populating the board matrix with either the given value
or an array of possibilities. We then go through each row, column and
box eliminating possibilities from the unknown squares. If there is
ever only one possibility for a square we set that square to the now
known value. Next we go through each row, column and box to find
instances where a square has multiple possibilities, but for that set
one of these possibilities is the only one. So if a square has
possibilities of 2 and 7, but no other square in the same row can be 2
then this square must be 2 and not 7. We alternate between this process
and eliminating until we either find a solution or we have gone through
a loop without finding anything to change.

I'm not convinced that this fully solves ever puzzle. I'd be interested
in a proof though. (ie if a given sudoku board has only one possible
solution then this algorithm will find it) The next logical step would
be to brute force the rest of the puzzle looking for solutions. A Depth
First Search would work.

In any case. This was a good help for me learning ruby. I was
especially happy to find the set operators for arrays. That made my
day.

-----Horndude77


#!/usr/bin/env ruby

class Sudoku
def initialize(boardstring)
@board = Array.new(9)
9.times { |i| @board = Array.new(9) }
flattened = boardstring.delete("-+|\n").split
index = 0
@unknown = []

# set up actual array
9.times do |i|
9.times do |j|
if(flattened[index] == '_') then
@board[j] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
@unknown << [i,j]
else
@board[j] = flattened[index].to_i
end
index += 1
end
end

#set up what each row, col, and box contains
@rows = Array.new(9)
@cols = Array.new(9)
@boxes = Array.new(9)
9.times { |i| @rows = numsInRow(i) }
9.times { |j| @cols[j] = numsInCol(j) }
3.times { |i| 3.times { |j| @boxes[i+3*j] = numsInBox(3*i,3*j) } }
end

def numsInRow(row)
toreturn = []
9.times do |j|
if(@board[row][j].kind_of? Fixnum) then
toreturn << @board[row][j]
end
end
return toreturn
end

def numsInCol(col)
toreturn = []
9.times do |i|
if(@board[col].kind_of? Fixnum) then
toreturn << @board[col]
end
end
return toreturn
end

def numsInBox(boxrow, boxcol)
toreturn = []
x = boxrow - boxrow%3
y = boxcol - boxcol%3
3.times do |i|
3.times do |j|
if(@board[x+i][y+j].kind_of? Fixnum) then
toreturn << @board[x+i][y+j]
end
end
end
return toreturn
end

def to_s
s = ""
9.times do |i|
if(i%3 == 0) then
s += "+-------+-------+-------+\n"
end
9.times do |j|
if(j%3 == 0) then
s += "| "
end
if(@board[j].kind_of? Array) then
s += "_ "
else
s += "#{@board[j]} "
end
end
s += "|\n"
end
s += "+-------+-------+-------+\n"
return s
end

# Looks in row, column and box to eliminate impossible values
def eliminate(i,j)
changed = false
if(@board[j].kind_of? Array) then
combined = @rows | @cols[j] | @boxes[(i/3)+(j-j%3)]
if( (@board[j] & combined).length > 0) then
changed = true
@board[j] -= combined
end

if(@board[j].length == 1) then
foundsolution(i,j,@board[j][0])
end
end
return changed
end

def foundsolution(x,y,val)
@board[x][y] = val
@rows[x] << @board[x][y]
@cols[y] << @board[x][y]
@boxes[(x/3)+(y-y%3)] << @board[x][y]
@unknown.delete([x,y])
end

def eliminateall
changed = true
while(changed)
changed = false
@unknown.each do |u|
if(eliminate(u[0],u[1])) then changed = true end
end
end
return changed
end

#these check functions look for squares that have multiple
# possibilities except the set itself only has one.
def checkrow(i)
changed = false
set = Hash.new
9.times do |j|
if (@board[j].kind_of? Array) then
@board[j].each do |e|
if(set[e]) then
set[e] << j
else
set[e] = [j]
end
end
end
end
set.each do |k,v|
if(v.length == 1) then
foundsolution(i,v[0],k)
changed = true
end
end
return changed
end

def checkcol(j)
changed = false
set = Hash.new
9.times do |i|
if (@board[j].kind_of? Array) then
@board[j].each do |e|
if(set[e]) then
set[e] << i
else
set[e] =
end
end
end
end
set.each do |k,v|
if(v.length == 1) then
foundsolution(v[0],j,k)
changed = true
end
end
return changed
end

def checkbox(n)
x = 3*(n%3)
y = 3*(n/3)
changed = false
set = Hash.new
3.times do |i|
3.times do |j|
if (@board[x+i][y+j].kind_of? Array) then
@board[x+i][y+j].each do |e|
if(set[e]) then
set[e] << [x+i,y+j]
else
set[e] = [ [x+i,y+j] ]
end
end
end
end
end
set.each do |k,v|
if(v.length == 1) then
foundsolution(v[0][0], v[0][1], k)
changed = true
end
end
return changed
end

def checkallrows
changed = false
9.times do |i|
if(checkrow(i)) then changed = true end
end
return changed
end

def checkallcols
changed = false
9.times do |j|
if(checkcol(j)) then changed = true end
end
return changed
end

def checkallboxes
changed = false
9.times do |n|
if(checkbox(n)) then changed = true end
end
return changed
end

def solve
#is there a better way to do this? it seems messy
# and redundant.
changed = true
while(changed && @unknown.length>0)
changed = false
changed = eliminateall ? true : changed
changed = checkallrows ? true : changed
changed = eliminateall ? true : changed
changed = checkallcols ? true : changed
changed = eliminateall ? true : changed
changed = checkallboxes ? true : changed
end
puts self
if(@unknown.length>0)
puts "I can't solve this one"
end
end
end

board = Sudoku.new($stdin.readlines.join)
board.solve

 

[James Edward Gray II]

In any case. This was a good help for me learning ruby. I was
especially happy to find the set operators for arrays. That made my
day.

Then you'll want to look at the standard "set" library. That will
make your whole weekend.

James Edward Gray II

 

[Simon Kröger]

Hi,

here is my solution. The algorithm is well described by Horndude77,
but this implementation also features the brute force part to solve
them all. (which may need some more seconds)

This one is hardest for my algorithm (from the list i posted):

+-------+-------+-------+
| 7 _ _ | _ _ _ | _ 1 9 |
| 4 6 _ | 1 9 _ | _ _ _ |
| _ _ _ | 6 8 2 | 7 _ 4 |
+-------+-------+-------+
| _ 9 _ | _ _ _ | _ _ 7 |
| _ _ _ | 3 _ _ | 4 _ 5 |
| _ _ 6 | 7 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ 1 | _ _ _ | _ _ _ |
| 2 _ _ | _ 7 4 | _ _ _ |
| _ _ _ | 2 _ _ | 3 _ _ |
+-------+-------+-------+

it took 18.6s to solve:
+-------+-------+-------+
| 7 8 2 | 4 5 3 | 6 1 9 |
| 4 6 5 | 1 9 7 | 8 2 3 |
| 3 1 9 | 6 8 2 | 7 5 4 |
+-------+-------+-------+
| 5 9 3 | 8 4 1 | 2 6 7 |
| 1 2 7 | 3 6 9 | 4 8 5 |
| 8 4 6 | 7 2 5 | 9 3 1 |
+-------+-------+-------+
| 6 7 1 | 9 3 8 | 5 4 2 |
| 2 3 8 | 5 7 4 | 1 9 6 |
| 9 5 4 | 2 1 6 | 3 7 8 |
+-------+-------+-------+

here is the code:
----------------------------------------------------------------------
require 'Set'
require 'Benchmark'

class Board
@@col = Array.new(9) {|o| Array.new(9){|i| o + i*9}}
@@row = Array.new(9) {|o| Array.new(9){|i| o*9 + i}}
@@box = Array.new(9) {|o| Array.new(9){|i|
(o / 3) * 27 + (o % 3) * 3 + ((i % 3) + (i / 3) * 9)}}

@@neighbourhoods = Array.new(81) {|i|
[[], @@row[i /9], @@col[i % 9], @@box[(i / 27) * 3 + (i % 9) / 3]]}

attr_reader :cells, ossibilities

def initialize cells
@possibilities = Array.new(81) {(1..9).to_set}
@cells = Array.new(81){0}
81.times{|i|set_cell(i, cells) if cells != 0}
end

def set_cell c, v
@@neighbourhoods[c].flatten.each{|i|
possibilities-=[v] unless c==i}
@cells[c], @possibilities[c] = v, [v]
end

def to_s
"+-------+-------+-------+\n| " +
Array.new(3) do |br|
Array.new(3) do |r|
Array.new(3) do |bc|
Array.new(3) do |c|
@cells[br*27 + r * 9 + bc * 3 + c].nonzero? || "_"
end.join(" ")
end.join(" | ")
end.join(" |\n| ")
end.join(" |\n+-------+-------+-------+\n| ") +
" |\n+-------+-------+-------+\n"
end

def solve_with_logic!
count, changed = 0, 0
begin
next if @cells[i = count % 81] != 0
p = possibilities
@@neighbourhoods.each do |neighbours|
pn = neighbours.inject(p){|r, j|(j != i)?r-possibilities[j]:r}
if pn.size == 1
pn.each{|c| set_cell(i, c)}
changed = count
break
end
end
end until ((count += 1) - changed) > 81
self
end

def solve_with_logic
Board.new(@cells).solve_with_logic!
end

def solve
board = solve_with_logic
return nil if (0..80).find{|i| board.possibilities.size == 0}
return board unless board.cells.find{|c| c==0}

#we have to guess
(2..9).each do |c|
81.times do |i|
if (p = board.possibilities).size == c
p.each do |j|
board.set_cell(i,j)
b = board.solve
return b if b
end
return nil
end
end
end
end

end

# main
count, $stdout.sync = 0, true
Benchmark.bm 20 do |bm|
loop do
cells = []
while cells.size < 81 do
exit 0 if ARGF.eof
ARGF.gets.scan(/[0-9_.]/).each{|c| cells << c.to_i}
end
board = Board.new(cells)
bm.report "solving nr #{count+=1}" do
board = board.solve
end
puts board.to_s + "\n\n"
end
end

 

[Adam Shelly]

------=_Part_125_11136010.1124762925385
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Hi. This is my first attempt at a ruby quiz, and my first post to ruby-talk=
=20
I've been messing with ruby for about a year. I actually wrote a version of=
=20
this solver with a fxwindows gui a while ago. The quiz was a good excuse to=
=20
clean it up and refactor it to handle text input.=20

It takes grids of almost arbitrary sizes upto 16 (and could be extended=20
more). It doesn't do any guessing, so it never solves some of the posted=20
programs. On the other hand, the official sudoku program from
www.soduku.com<http://www.soduku.com>tells me that those are not valid
puzzles, so I don't feel so bad. Anyway,
here it is:

#!/usr/bin/env ruby


# SodukuSolver.rb
# Solves soduku puzzles.
# supports arbitrary grid sizes (tested upto 16x16)

#Utility function to define the inner sets of a grid
def GetGroupBounds(gridsize)
case gridsize
when 1 then [1,1]
when 2 then [1,2]
when 4 then [2,2]
when 6 then [2,3]
when 8 then [2,4]
when 9 then [3,3]
when 10 then [5,2]
when 12 then [3,4]
when 14 then [2,7]
when 15 then [3,5]
when 16 then [4,4]
else=20
print "GridSize of #{gridsize} unsupported. Exiting\n"
[0,0]
end
end

# a Cell represents a square on the grid.
# it keeps track of all possible values it could have.
# it knows its grid location for convenience
class Cell=20
attr_reader :row, :col, :group, ossible
def initialize(row, col, val=3D-1, max =3D 9)
@row =3D row
@col =3D col
bounds =3D GetGroupBounds(max)
@group =3D col/(bounds[0])+((row/bounds[1])*bounds[1])
@solved =3D false
case val
when 1..max
@possible =3D [val]
else
@possible =3D (1..max).to_a
end
end

def includes?(n)
@possible.include?(n)
end

def markSolved
@solved =3D true
end

def set(toValue)
if (found =3D @possible.include?(toValue))
@possible =3D [toValue];
end
return found
end

def hasFinalValue
if (@possible.length =3D=3D 1)
return @possible[0]
end
end

def eliminate(n)
@possible.delete(n)
return hasFinalValue && !@solved
end

def show
(v =3D hasFinalValue)?" "+v.to_s(32):" _"
end

def to_s #for debugging
s =3D @possible.to_s;
s.length.upto(9) do s << " " end
"(#{row},#{col})["+s+"]"
end
end=20


class Solver
def initialize(boardlist, size)
@groups =3D[]
@rows =3D[]
@cols =3D []=20
@Queue =3D [] #a list of cells to check for solutions.
@size =3D size
0.upto(@size-1) { |n| @groups[n] =3D [] ; @rows[n]=3D[]; @cols[n]=3D[] }
r=3Dc=3D0
boardlist.each do |v|
cell =3D Cell.new(r,c,v, size)
@groups[cell.group] <<@rows[r][c] =3D @cols[c][r] =3D cell
@Queue << cell
c+=3D1
if (c=3D=3Dsize) then c=3D0; r=3Dr+=3D1 end
end
end

def solve
while @queue.size > 0
while (cell =3D @queue.pop)
eliminateChoices(cell)=20
end
checkForKnownValues()
end
end

#for any resolved cell, eliminate its value from the possible values of the=
=20
other cells in the set
def eliminateChoices(cell)
value =3D cell.hasFinalValue
if (value)
cell.markSolved
eliminateChoiceFromGroup(@groups[cell.group], cell, value)
eliminateChoiceFromGroup(@rows[cell.row], cell, value)
eliminateChoiceFromGroup(@cols[cell.col], cell, value)
end
end

def eliminateChoiceFromGroup(g, exceptThisCell, n)
g.each do |cell|=20
eliminateValueFromCell(n,cell) if (cell !=3D exceptThisCell)
end
end

def eliminateValueFromCell(value, cell)
if (cell.eliminate(value) && [email protected]?(cell))
@Queue << cell #if this cell is now resolved, put it on the queue.
end
end

def checkForKnownValues()
0.upto(@size-1) do |n|
findPairs(@rows[n])
findPairs(@cols[n])
findPairs(@groups[n])
findUniqueChoices(@rows[n])
findUniqueChoices(@cols[n])
findUniqueChoices(@groups[n])
end
end

def findUniqueChoices(set)
1.upto(@size) do |n| #check for every possible value
lastCell =3D nil
set.each do |c| #in every cell in the set
if (c.includes?(n))
if (c.hasFinalValue || lastCell) #found a 2nd instance=20
lastCell =3D nil
break
end
lastCell =3D c;
end=20
end=20
#if true, there is only one cell in the set with that value, so be the=20
answer
if (lastCell && !lastCell.hasFinalValue)=20
lastCell.set(n)
@Queue << lastCell
end
end
end=20

#find any pair of cells in a set with the same 2 possibilities=20
# - these two can be removed from any other cell in the same set
def findPairs(set)
0.upto(@size-1) do |n|
n.upto(@size-1) do |m|
if (n !=3D m && set[n].possible.size =3D=3D 2 && set[n].possible =3D=3D=20
set[m].possible)
eliminateExcept(set, [m,n], set[n].possible)
end
end
end
end

#for every cell in a set except those in the skiplist, eliminate the values
def eliminateExcept(set, skipList, values)
0.upto(@size-1) do |i|=20
if (!skipList.include?(i))=20
values.each {|v| eliminateValueFromCell(v, set)}=20
end
end
end

#formating (vertical line every cbreak)
def showBorder(cbreak)
s =3D "+"
1.upto(@size) do |n|
s << "--"
if ((n)%cbreak =3D=3D 0) then s<< "-+" end
end
s <<"\n"
end


def show
r=3Dc=3D0
cbreak,rbreak =3D GetGroupBounds(@size)
s =3D showBorder(cbreak)
@rows.each do |row|=20
r+=3D1
s << "|"
row.each do |cell|=20
c+=3D1
s << cell.show
if (c=3D=3Dcbreak) then s << " |";c=3D0; end
end
s<<"\n"
if (r=3D=3Drbreak) then s << showBorder(cbreak); r=3D0; end
end
s<<"\n"
print s
end
end

#parses text file containing board. The only significant characters are _,=
=20
0-9, A-Z.
#there must be an equal number of significant chars in each line, and the=
=20
same number of many rows.
def ParseBoard(file)
row =3D 0
col =3D 0
boardlist =3D [ ]
file.each do |line|
line.chomp.each_byte do |c|
case c
when ?A..?Z
boardlist << c.to_i - ?A + 10
col+=3D1
when ?0..?9
boardlist << c.to_i - ?0
col+=3D1
when ?_
boardlist << -1
col+=3D1
end
end
if (col > 0) then=20
row+=3D1=20
if (row =3D=3D col) then break end
end
col=3D0
end
return boardlist,row
end

if __FILE__ =3D=3D $0
boardlist, size =3D ParseBoard(ARGF)=20
sol =3D Solver.new(boardlist, size)

sol.show
sol.solve()
sol.show

end

 

[Adam Shelly]

------=_Part_133_7508606.1124763103784
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

aargh. What happened to my tabs?

=20
Hi. This is my first attempt at a ruby quiz, and my first post to=20
ruby-talk.

...

------=_Part_133_7508606.1124763103784--

 

[James Edward Gray II]

Hi. This is my first attempt at a ruby quiz, and my first post to
ruby-talk.

Welcome to the Ruby community and thanks for the quiz submission!

I'm not sure what happened to your tabs. Did you just paste the code
right into a message?

James Edward Gray II

 

[James Edward Gray II]

Ok, I've updated my version to resort to guessing when it can't deduce
all the values.

Looking good. Here's a few general Ruby style tips. Feel free to
ignore, if your not interested:

1. An easier way to write `print "line\n"` is `puts line`.
2. Instead of using the dprint() method and commenting out the
print, try puts "whatever" if $DEBUG. Then you can use Ruby's -d
command-line switch to enable debugging output whenever you like (it
sets $DEBUG).
3. You can drop those outer parenthesis for if statements. `if
(condition)` can be just `if condition`.

James Edward Gray II

 

[Adam Shelly]

Looking good. Here's a few general Ruby style tips. Feel free to
ignore, if your not interested:
=20
1. An easier way to write `print "line\n"` is `puts line`.
2. Instead of using the dprint() method and commenting out the
thanks
3. You can drop those outer parenthesis for if statements. `if
(condition)` can be just `if condition`.

I know, but C programmer habits die hard. just looks funny without them...

So here's one thing I couldn't figure out last night, maybe someone can hel=
p me:
I wanted to throw an exception in the middle of a pair of recursive
functions, and catch it at the beginning of recursion. But I can't
figure out where to put the rescue.
I wanted to do something like this pseudocode:

def solve
deduce
startGuessing if !solved
return solved
end

def deduce
...work...
raise BadGuess if conflict
end

def startGuessing
@depth+=3D1
begin
while candidates do
begin
guess #chose a candidate
cloneBoard.solve #with that candidate
rescue BadGuess
#go on to next candidate
end
end #while
raise UnsolvableBoard if !solved
rescue UnsolvableBoard if @depth =3D=3D 1 # this doesn't work.
# if I remove the if, I end up at the level I started with.
# and putting the rescue in the solve function doesn't help either.
# ? So can I get back to the next candidate on the 1st level,
# without checking return codes the whole way down
# (which is what I ended up doing)?
end
end


Thanks for any ideas,
-Adam

 

[Travis Smith]

So here's one thing I couldn't figure out last night, maybe someone can h= elp me:
I wanted to throw an exception in the middle of a pair of recursive
functions, and catch it at the beginning of recursion. But I can't
figure out where to put the rescue.
I wanted to do something like this pseudocode:
=20
def solve
deduce
startGuessing if !solved
return solved
end
=20
def deduce
...work...
raise BadGuess if conflict
end
=20
def startGuessing
@depth+=3D1
begin
while candidates do
begin
guess #chose a candidate
cloneBoard.solve #with that candidate
rescue BadGuess
#go on to next candidate
end
end #while
raise UnsolvableBoard if !solved
rescue UnsolvableBoard if @depth =3D=3D 1 # this doesn't work.
# if I remove the if, I end up at the level I started with.
# and putting the rescue in the solve function doesn't help either.
# ? So can I get back to the next candidate on the 1st level,
# without checking return codes the whole way down
# (which is what I ended up doing)?
end
end

You can always recuse it, then throw it again if you don't want it. At
least I assume so... I've never tried to do it in Ruby.


--=20
~Travis