[QUIZ] Sodoku Solver (#43)
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:
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
<20050819130127.ELYX126...@localhost.localdomain>,
Ruby Quiz <ja...@grayproductions.net> wrote:
>
> Sodokus are simple number puzzles that often appear in various sources of
> print.
<snip>
> 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...
--
Chris Game
This time it will surely run.
Simon Kröger
> Karl von Laudermann wrote:
>
>
>>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?
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
Chris Game <chri...@example.net> wrote:
> Karl von Laudermann wrote:
>
> > 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?
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 _ _ |
Vance A Heron
read (and write) the current intput format.
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 | _ _ _ |
+-------+-------+-------+
The 4 problems we've been given (the orignal with the
quiz and the 3 new ones seemed to yield fairly
quickly. I'm looking forward to see other
solutions and try them on this one.
Here's the results of running the 1st 4.
Vance
heron-linux:for i in rqi* ; do time sd2.rb $i ; done
Input
+-------+-------+-------+
| _ 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 _ |
+-------+-------+-------+
Solution
+-------+-------+-------+
| 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.060s
user 0m0.050s
sys 0m0.000s
Input
+-------+-------+-------+
| _ _ 2 | _ _ 5 | _ 7 9 |
| 1 _ 5 | _ _ 3 | _ _ _ |
| _ _ _ | _ _ _ | 6 _ _ |
+-------+-------+-------+
| _ 1 _ | 4 _ _ | 9 _ _ |
| _ 9 _ | _ _ _ | _ 8 _ |
| _ _ 4 | _ _ 9 | _ 1 _ |
+-------+-------+-------+
| _ _ 9 | _ _ _ | _ _ _ |
| _ _ _ | 1 _ _ | 3 _ 6 |
| 6 8 _ | 3 _ _ | 4 _ _ |
+-------+-------+-------+
Solution
+-------+-------+-------+
| 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 0m1.626s
user 0m0.830s
sys 0m0.010s
Input
+-------+-------+-------+
| _ _ _ | _ 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 | _ _ _ |
+-------+-------+-------+
Solution
+-------+-------+-------+
| 2 1 5 | 8 7 6 | 9 4 3 |
| 6 7 8 | 3 9 4 | 2 1 5 |
| 3 4 9 | 1 2 5 | 8 7 6 |
+-------+-------+-------+
| 5 8 7 | 4 3 2 | 1 6 9 |
| 4 6 3 | 9 8 1 | 7 5 2 |
| 1 9 2 | 6 5 7 | 3 8 4 |
+-------+-------+-------+
| 8 2 6 | 7 4 3 | 5 9 1 |
| 7 3 4 | 5 1 9 | 6 2 8 |
| 9 5 1 | 2 6 8 | 4 3 7 |
+-------+-------+-------+
real 0m0.960s
user 0m0.450s
sys 0m0.000s
Input
+-------+-------+-------+
| _ _ 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 _ _ |
+-------+-------+-------+
Unsolvable
+-------+-------+-------+
| 4 6 1 | 9 2 7 | 8 5 3 |
| 8 7 5 | 3 1 6 | _ 9 2 |
| 3 2 9 | 8 4 5 | 6 1 7 |
+-------+-------+-------+
| _ 9 _ | 7 _ _ | 5 _ _ |
| _ 4 2 | 6 5 8 | 1 3 9 |
| _ _ 3 | _ _ 9 | _ 4 _ |
+-------+-------+-------+
| 2 _ _ | 5 7 _ | 9 _ 4 |
| _ 3 _ | _ 9 1 | _ 6 _ |
| _ _ 4 | _ _ _ | 3 _ _ |
+-------+-------+-------+
real 0m0.046s
user 0m0.030s
sys 0m0.010s
Mohit Muthanna
> I too did one back in April - and have modfied it to
> read (and write) the current intput format.
>
> 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.
--
Mohit Muthanna [mohit (at) muthanna (uhuh) com]
"There are 10 types of people. Those who understand binary, and those
who don't."
Dennis Ranke
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
hornd...@gmail.com
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
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
Gavin Kistner
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[i].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[i]
if solve_set( row )
row_solved[i] = true
end
end
}
@cols.each_with_index{ |col,i|
unless col_solved[i]
if solve_set( col )
col_solved[i] = true
end
end
}
@tiles.each_with_index{ |tile,i|
unless tile_solved[i]
if solve_set( tile )
tile_solved[i] = 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, :possibles
def initialize( value=nil )
@possibles = {}
unless @value = value
1.upto(9){ |i| @possibles[i]=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
hornd...@gmail.com
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[i] = 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[i][j] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
@unknown << [i,j]
else
@board[i][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[i] = 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[i][col].kind_of? Fixnum) then
toreturn << @board[i][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[i][j].kind_of? Array) then
s += "_ "
else
s += "#{@board[i][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[i][j].kind_of? Array) then
combined = @rows[i] | @cols[j] | @boxes[(i/3)+(j-j%3)]
if( (@board[i][j] & combined).length > 0) then
changed = true
@board[i][j] -= combined
end
if(@board[i][j].length == 1) then
foundsolution(i,j,@board[i][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[i][j].kind_of? Array) then
@board[i][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[i][j].kind_of? Array) then
@board[i][j].each do |e|
if(set[e]) then
set[e] << i
else
set[e] = [i]
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
David Tran
complex strategics.
class Sodoku
def initialize( input )
@ary = Array.new(9) { Array.new(9) } # 9 rows x 9 columns
index = 0
input.to_s.scan(/./) do |c|
case c
when '1'..'9' : @ary[index / 9][index % 9] = c.to_i
when '_' : # skip
else next
end
break if (index += 1) == 9 * 9
end
# raise "Input data incomplete" if index != 9 * 9
end
def solve
9.times do |row|
9.times do |col|
next if @ary[row][col]
# find next possible value for @ary[row][col]
1.upto(9) do |v|
# check on same row/col, no any col/row already used it
next unless 9.times { |i| break if @ary[i][col] == v ||
@ary[row][i] ==v }
# check on 3x3 box, no other cell already used it
next unless 3.times do |i|
break unless 3.times do |j|
break if @ary[i + row / 3 * 3][j + col / 3 * 3] == v
end
end
@ary[row][col] = v
if solve
return true
else
@ary[row][col] = nil # backtracking
end
end
return false
end
end
true
end
def to_s
s = "+-------+-------+-------+\n"
@ary.each_with_index do |row, index|
row = row.map { |e| e ||= '_' } * ' '
row[6,0] = row[12,0] = '| '
s << '| ' << row << " |\n"
s << "+-------+-------+-------+\n" if [2, 5, 8].include?(index)
end
s
end
end
if __FILE__ == $0
input = ''
while line = gets
input << line
end
sodoku = Sodoku.new(input)
puts sodoku.solve ? sodoku : "No solution"
end
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
here is a list of some Sodokus to solve and test
your algorithms (i would like to see which one is
hardest for your script and how long does this take):
+-------+-------+-------+
| _ 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 _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 2 | _ _ 5 | _ 7 9 |
| 1 _ 5 | _ _ 3 | _ _ _ |
| _ _ _ | _ _ _ | 6 _ _ |
+-------+-------+-------+
| _ 1 _ | 4 _ _ | 9 _ _ |
| _ 9 _ | _ _ _ | _ 8 _ |
| _ _ 4 | _ _ 9 | _ 1 _ |
+-------+-------+-------+
| _ _ 9 | _ _ _ | _ _ _ |
| _ _ _ | 1 _ _ | 3 _ 6 |
| 6 8 _ | 3 _ _ | 4 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ 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 | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| 1 2 _ | _ _ _ | _ 3 _ |
| _ _ _ | _ 2 4 | _ 5 _ |
+-------+-------+-------+
| _ 9 _ | _ _ _ | 6 _ 8 |
| _ 3 _ | 5 _ 8 | _ _ _ |
| 6 7 _ | _ _ _ | 3 _ _ |
+-------+-------+-------+
| 8 _ _ | _ 1 5 | _ _ _ |
| _ 6 _ | 9 _ _ | _ 2 1 |
| 3 _ _ | _ 4 _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ 1 |
| _ _ 4 | _ 1 _ | 6 _ _ |
| 7 1 _ | _ _ _ | 2 8 _ |
+-------+-------+-------+
| _ _ 9 | 3 _ _ | 8 5 _ |
| 5 _ 8 | 4 _ _ | 7 _ _ |
| _ 2 _ | _ 8 5 | _ _ 6 |
+-------+-------+-------+
| _ _ _ | _ _ _ | 4 _ _ |
| _ 4 6 | _ _ 9 | _ _ _ |
| _ _ _ | 7 3 _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ _ _ | _ 6 _ |
| 9 _ _ | _ _ 3 | _ _ _ |
| _ _ _ | _ _ _ | 7 _ 4 |
+-------+-------+-------+
| _ _ 6 | _ _ _ | 1 _ 9 |
| _ 7 _ | _ 2 _ | 4 3 _ |
| _ _ _ | _ _ _ | _ _ 5 |
+-------+-------+-------+
| _ _ 3 | _ _ 5 | _ _ 1 |
| _ 4 _ | 1 _ _ | 6 _ _ |
| _ 6 9 | 4 7 _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ _ _ | 9 _ 7 |
| _ _ _ | _ _ 1 | 8 5 _ |
| _ _ _ | _ _ _ | 2 3 _ |
+-------+-------+-------+
| 2 3 _ | _ 6 _ | _ _ _ |
| _ 6 9 | 3 8 _ | _ 4 _ |
| _ 8 1 | _ _ 5 | 6 _ _ |
+-------+-------+-------+
| _ 9 _ | 6 _ _ | _ _ _ |
| 1 _ 2 | _ _ 7 | _ _ _ |
| _ 5 _ | _ _ _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ _ 2 | 7 _ _ |
| 4 _ _ | 5 8 _ | _ 1 _ |
| 3 _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| 6 _ 7 | _ 5 _ | _ _ _ |
| 2 1 _ | _ _ _ | 9 _ 3 |
| _ _ _ | _ 7 _ | _ _ _ |
+-------+-------+-------+
| _ 2 _ | 4 _ _ | _ _ 9 |
| _ _ 1 | _ _ 6 | _ _ _ |
| _ _ _ | 8 _ _ | 4 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ 1 _ | 7 8 _ |
| 5 _ _ | _ _ 9 | _ _ _ |
| _ _ _ | _ _ _ | _ 4 _ |
+-------+-------+-------+
| _ 2 6 | _ _ _ | _ _ _ |
| _ _ _ | 6 _ _ | _ _ 3 |
| _ 7 4 | _ 8 _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ 3 | _ _ 2 |
| _ 8 _ | _ 4 _ | _ 1 _ |
| 6 _ _ | 5 _ _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ 3 _ | _ _ _ |
| 9 3 _ | _ 6 _ | 8 _ _ |
| 5 6 _ | _ _ _ | _ _ 4 |
+-------+-------+-------+
| _ _ 2 | _ 1 6 | _ _ _ |
| 8 5 _ | 4 7 _ | _ _ _ |
| 6 _ _ | _ 2 9 | _ _ 3 |
+-------+-------+-------+
| 7 _ _ | _ _ _ | 2 1 _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ 5 9 |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ 3 _ | _ _ _ |
| 9 3 _ | _ 6 _ | 8 _ _ |
| 5 6 _ | _ _ _ | _ _ 4 |
+-------+-------+-------+
| 3 _ 2 | _ 1 6 | _ _ _ |
| 8 5 _ | 4 7 3 | _ _ _ |
| 6 _ _ | _ 2 9 | _ _ 3 |
+-------+-------+-------+
| 7 _ _ | _ _ _ | 2 1 _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ 5 9 |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ 7 _ | _ _ _ |
| 3 4 9 | _ _ _ | _ 7 _ |
| _ _ 6 | 5 _ _ | 8 4 _ |
+-------+-------+-------+
| _ _ 3 | _ 8 6 | _ _ 9 |
| 2 _ _ | _ _ _ | _ _ _ |
| _ _ 5 | 9 _ _ | _ _ _ |
+-------+-------+-------+
| 5 _ _ | _ 2 _ | _ _ 1 |
| 9 _ _ | _ _ _ | _ _ 7 |
| _ _ 8 | _ _ 1 | 6 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ 7 _ | _ 9 _ |
| _ _ _ | _ _ 8 | _ _ 4 |
| _ 4 2 | _ _ 1 | _ 7 _ |
+-------+-------+-------+
| _ _ 4 | _ _ _ | _ _ 8 |
| 8 _ _ | 2 _ 5 | _ _ 9 |
| 5 _ _ | _ _ _ | 7 _ _ |
+-------+-------+-------+
| _ 7 _ | 6 _ _ | 1 3 _ |
| 2 _ _ | 8 _ _ | _ _ _ |
| _ 6 _ | _ 3 _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | _ 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 | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | 1 _ _ | 7 _ _ |
| _ 2 _ | 6 9 _ | _ _ _ |
| 9 _ _ | _ _ 3 | _ 8 2 |
+-------+-------+-------+
| _ _ _ | _ _ _ | 4 6 _ |
| 6 4 _ | _ _ _ | _ 5 7 |
| _ 5 8 | _ _ _ | _ _ _ |
+-------+-------+-------+
| 2 1 _ | 8 _ _ | _ _ 9 |
| _ _ _ | _ 1 6 | _ 7 _ |
| _ _ 4 | _ _ 2 | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | 7 _ _ | _ _ 1 |
| _ 8 _ | _ _ _ | 3 2 _ |
| _ 1 9 | _ 2 _ | _ _ _ |
+-------+-------+-------+
| _ _ 1 | _ 7 3 | _ _ _ |
| _ _ _ | 6 _ _ | 1 _ 7 |
| 9 _ _ | _ 8 _ | _ _ _ |
+-------+-------+-------+
| _ 2 4 | 9 _ _ | _ 5 6 |
| _ 5 _ | _ 1 _ | 9 _ 2 |
| _ _ 6 | _ 5 _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ _ | 9 _ _ | 8 _ 7 |
| _ _ _ | _ _ 7 | _ _ _ |
| _ _ 3 | _ _ _ | _ _ 2 |
+-------+-------+-------+
| _ _ 9 | _ _ 4 | _ _ _ |
| _ _ 1 | _ 6 _ | _ _ _ |
| _ 6 _ | _ _ 3 | _ _ 1 |
+-------+-------+-------+
| _ _ 8 | _ 4 _ | 1 _ _ |
| _ 3 _ | 6 _ _ | 7 8 _ |
| 7 _ _ | _ _ 9 | _ 2 5 |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 1 | _ 8 _ | 6 _ 4 |
| _ 3 7 | 6 _ _ | _ _ _ |
| 5 _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ 5 | _ _ _ |
| _ _ 6 | _ 1 _ | 8 _ _ |
| _ _ _ | 4 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ 3 |
| _ _ _ | _ _ 7 | 5 2 _ |
| 8 _ 2 | _ 9 _ | 7 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 1 | 2 _ _ | _ 6 _ |
| _ _ 9 | _ _ 8 | _ 4 _ |
| _ 5 _ | _ 4 _ | 9 _ _ |
+-------+-------+-------+
| 7 3 _ | _ 8 _ | _ _ _ |
| _ _ 5 | _ 3 _ | 1 _ _ |
| _ _ _ | _ 6 _ | _ 3 4 |
+-------+-------+-------+
| _ _ 3 | _ 2 _ | _ 9 _ |
| _ 2 _ | 8 _ _ | 5 _ _ |
| _ 9 _ | _ _ 1 | 4 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 1 | 4 3 _ | _ _ 5 |
| 8 _ 5 | _ _ _ | _ _ _ |
| _ 7 _ | 6 _ _ | _ 1 _ |
+-------+-------+-------+
| _ _ _ | _ 7 _ | _ _ 9 |
| _ _ _ | 2 _ 3 | 4 _ _ |
| 1 _ _ | _ 8 _ | _ _ _ |
+-------+-------+-------+
| _ 2 _ | _ _ 9 | _ _ _ |
| 9 _ _ | 8 _ _ | 5 2 3 |
| 3 _ 4 | _ _ _ | 9 7 _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 2 | _ 9 _ | 1 _ 7 |
| _ 3 8 | 6 _ _ | _ _ _ |
| 4 _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ 5 | _ _ _ |
| _ _ 9 | _ 1 _ | 3 _ _ |
| _ _ _ | 4 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ 4 |
| _ _ _ | _ _ 7 | 9 2 _ |
| 8 _ 6 | _ 3 _ | 7 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 2 | 6 _ _ | _ _ _ |
| _ 9 _ | _ _ _ | 4 _ _ |
| _ 1 _ | _ _ 9 | _ _ 7 |
+-------+-------+-------+
| _ _ _ | _ 4 6 | _ _ 5 |
| _ _ 4 | _ 9 _ | _ 8 _ |
| _ _ _ | 7 1 _ | 3 _ 4 |
+-------+-------+-------+
| 8 _ _ | _ 3 1 | _ _ _ |
| 3 _ _ | 9 8 _ | _ _ _ |
| _ _ _ | 4 _ _ | _ 3 2 |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 3 | _ 5 _ | 4 _ _ |
| 7 _ _ | _ 6 _ | _ _ _ |
| _ 5 _ | 8 _ _ | _ 6 _ |
+-------+-------+-------+
| 5 _ _ | _ _ 3 | _ _ 4 |
| _ 1 _ | _ 7 _ | _ 8 _ |
| 2 _ _ | 4 _ _ | _ _ 7 |
+-------+-------+-------+
| _ 4 _ | _ _ 8 | _ 5 _ |
| _ _ _ | _ 4 _ | _ _ 9 |
| _ _ 6 | _ 1 _ | 2 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 3 | _ 5 _ | 4 _ 7 |
| _ _ _ | _ _ _ | _ 9 _ |
| 4 2 _ | _ _ _ | 5 _ _ |
+-------+-------+-------+
| _ _ _ | _ 4 1 | 2 8 _ |
| _ _ _ | _ 8 9 | _ 4 _ |
| _ _ 1 | _ _ _ | 7 3 _ |
+-------+-------+-------+
| _ _ _ | 9 _ _ | _ _ _ |
| _ _ 6 | _ _ _ | _ 5 _ |
| _ 3 7 | 2 _ _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 3 | 6 2 _ | 4 _ _ |
| _ _ _ | _ _ 1 | 5 7 _ |
| _ _ _ | _ 7 _ | 9 _ _ |
+-------+-------+-------+
| 4 _ _ | _ _ _ | 6 9 _ |
| _ _ _ | 1 6 _ | 8 _ _ |
| 2 _ _ | _ _ _ | 1 _ _ |
+-------+-------+-------+
| 9 _ _ | _ 8 _ | 3 _ _ |
| _ 6 8 | 2 _ 4 | _ _ _ |
| _ _ _ | _ _ 6 | _ _ 8 |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 5 | 4 _ _ | 7 _ _ |
| _ _ _ | 5 2 _ | 4 9 6 |
| _ _ 4 | _ _ _ | _ 5 _ |
+-------+-------+-------+
| _ 1 _ | _ 6 _ | _ _ _ |
| _ _ _ | 8 _ _ | _ 4 _ |
| 2 7 _ | _ _ _ | 8 _ _ |
+-------+-------+-------+
| _ _ _ | 2 1 9 | _ _ _ |
| 1 _ _ | 6 _ _ | _ _ 9 |
| _ 8 2 | _ 7 _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 7 | _ _ 4 | _ _ _ |
| _ _ 2 | _ _ _ | 9 1 _ |
| _ 6 _ | _ 5 _ | _ _ 4 |
+-------+-------+-------+
| _ 3 _ | 6 2 _ | 1 _ _ |
| 6 _ _ | _ 7 _ | _ _ 2 |
| _ _ 1 | _ 8 5 | _ 6 _ |
+-------+-------+-------+
| 2 _ _ | _ 1 _ | _ 4 _ |
| _ 1 8 | _ _ _ | 6 _ _ |
| _ _ _ | 7 _ _ | 3 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ _ 9 | _ _ 1 | _ 8 7 |
| _ _ _ | _ _ _ | 4 _ _ |
| _ _ 1 | _ 8 _ | _ 6 _ |
+-------+-------+-------+
| _ _ _ | 8 3 6 | _ 2 _ |
| _ _ 6 | _ _ _ | _ _ _ |
| 4 5 _ | _ _ 7 | _ _ 6 |
+-------+-------+-------+
| 5 _ _ | _ _ 8 | _ _ 9 |
| _ 1 _ | _ 6 _ | _ _ 2 |
| _ _ _ | 4 2 _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ 2 _ | _ _ _ | _ _ _ |
| _ _ _ | 6 _ _ | _ _ 3 |
| _ 7 4 | _ 8 _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ 3 | _ _ 2 |
| _ 8 _ | _ 4 _ | _ 1 _ |
| 6 _ _ | 5 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ 1 _ | 7 8 _ |
| 5 _ _ | _ _ 9 | _ _ _ |
| _ _ _ | _ _ _ | _ 4 _ |
+-------+-------+-------+
+-------+-------+-------+
| _ 2 _ | _ _ 1 | _ 9 _ |
| _ _ 1 | _ 6 5 | 2 _ _ |
| _ _ 6 | _ _ _ | _ _ _ |
+-------+-------+-------+
| 2 8 _ | 4 _ _ | 3 _ _ |
| 9 _ 7 | _ _ 2 | _ _ 6 |
| _ _ 3 | _ _ _ | _ 2 _ |
+-------+-------+-------+
| _ 3 _ | _ _ _ | _ _ 5 |
| _ 7 _ | _ _ _ | 1 _ 2 |
| _ _ 2 | _ 3 _ | 8 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ 4 _ | _ _ _ | 9 _ _ |
| _ _ 3 | 2 _ _ | 8 _ _ |
| _ 6 _ | 4 _ _ | _ _ 2 |
+-------+-------+-------+
| 6 _ _ | 1 5 2 | _ _ _ |
| 7 5 _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ 5 1 |
+-------+-------+-------+
| _ _ 6 | 9 2 _ | _ _ 8 |
| _ _ 8 | _ _ 4 | 3 _ _ |
| _ 9 7 | 6 _ 8 | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ 4 _ | 8 9 _ | 3 5 _ |
| _ _ _ | _ 4 _ | _ _ _ |
| _ _ _ | _ _ 5 | 6 _ _ |
+-------+-------+-------+
| 2 _ _ | _ _ _ | _ 8 _ |
| 5 _ 3 | 1 8 _ | 9 _ _ |
| _ _ 9 | 7 _ _ | 1 _ _ |
+-------+-------+-------+
| _ _ _ | _ 5 _ | _ 2 _ |
| _ 3 _ | _ _ _ | _ _ 1 |
| _ _ 2 | _ _ _ | _ 6 _ |
+-------+-------+-------+
+-------+-------+-------+
| _ 5 _ | _ _ _ | 2 _ _ |
| _ _ _ | _ _ _ | _ 7 _ |
| _ _ _ | _ 6 8 | 3 _ 9 |
+-------+-------+-------+
| _ 8 _ | _ 5 4 | 9 _ _ |
| 6 _ _ | _ _ 2 | 1 _ _ |
| _ _ _ | 6 _ 7 | _ _ _ |
+-------+-------+-------+
| 1 4 _ | 3 _ _ | _ 2 _ |
| 5 _ _ | _ 7 6 | 8 1 _ |
| 7 _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| _ 7 _ | _ _ _ | _ _ _ |
| 6 _ _ | 5 4 _ | _ _ 3 |
| _ _ 1 | _ _ 2 | 4 _ _ |
+-------+-------+-------+
| _ _ 7 | _ _ 8 | _ _ _ |
| _ _ _ | 2 9 _ | _ _ _ |
| _ 4 9 | _ _ 3 | _ _ 8 |
+-------+-------+-------+
| _ _ 3 | _ _ _ | 7 _ _ |
| 2 _ _ | 7 3 4 | _ _ 9 |
| _ _ _ | _ _ _ | _ 6 _ |
+-------+-------+-------+
+-------+-------+-------+
| _ 7 _ | _ _ _ | 3 2 _ |
| _ _ _ | _ _ _ | _ 6 _ |
| _ _ 8 | 6 _ _ | _ _ 1 |
+-------+-------+-------+
| _ _ _ | _ _ _ | 6 3 _ |
| 7 _ 4 | _ _ _ | _ _ _ |
| _ 3 _ | 9 _ 1 | 7 _ 2 |
+-------+-------+-------+
| 9 2 _ | 8 3 _ | _ _ _ |
| 5 _ 7 | _ 2 _ | _ _ _ |
| _ 6 _ | _ 5 _ | 2 1 _ |
+-------+-------+-------+
+-------+-------+-------+
| _ 8 7 | _ 5 _ | 6 _ _ |
| 4 _ _ | _ _ _ | _ _ 3 |
| _ _ _ | 1 _ _ | _ 8 _ |
+-------+-------+-------+
| _ _ _ | _ _ 3 | _ _ 4 |
| _ 7 _ | 8 _ _ | _ _ _ |
| 6 _ _ | _ _ _ | _ 5 8 |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ 9 2 |
| _ _ 2 | _ _ 5 | 3 _ _ |
| _ 9 _ | 6 _ _ | 5 1 _ |
+-------+-------+-------+
+-------+-------+-------+
| _ 9 _ | _ _ 4 | _ _ _ |
| _ _ 4 | _ _ 1 | _ _ 3 |
| _ _ _ | 6 9 _ | _ _ 5 |
+-------+-------+-------+
| 8 _ _ | _ 5 _ | 3 _ 9 |
| _ 3 _ | _ _ 7 | 6 _ 2 |
| _ _ _ | _ 3 8 | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ 7 _ | _ _ _ |
| 5 _ 1 | _ _ _ | _ _ _ |
| _ 6 3 | _ _ _ | 8 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| 2 _ _ | _ 8 _ | _ _ 6 |
| _ 1 _ | _ _ _ | _ 7 _ |
| _ _ 9 | _ _ _ | 5 _ _ |
+-------+-------+-------+
| _ _ _ | 9 _ 5 | _ _ _ |
| 3 _ _ | _ 1 _ | _ _ 7 |
| _ _ _ | 2 _ 3 | _ _ _ |
+-------+-------+-------+
| _ _ 5 | _ _ _ | 4 _ _ |
| _ 7 _ | _ _ _ | _ 9 _ |
| 8 _ _ | _ 4 _ | _ _ 3 |
+-------+-------+-------+
+-------+-------+-------+
| 3 _ _ | _ 6 _ | _ _ 5 |
| _ 2 _ | _ _ _ | _ 4 _ |
| _ _ 7 | _ _ _ | 2 _ _ |
+-------+-------+-------+
| _ _ _ | 6 _ 7 | _ _ _ |
| 9 _ _ | _ 8 _ | _ _ 6 |
| _ _ _ | 9 _ 1 | _ _ _ |
+-------+-------+-------+
| _ _ 2 | _ _ _ | 7 _ _ |
| _ 4 _ | _ _ _ | _ 1 _ |
| 6 _ _ | _ 5 _ | _ _ 9 |
+-------+-------+-------+
+-------+-------+-------+
| 3 1 _ | 6 _ _ | _ _ _ |
| _ _ 2 | _ _ _ | _ _ _ |
| _ 5 _ | _ 9 _ | 7 8 _ |
+-------+-------+-------+
| _ _ _ | _ _ 5 | _ _ _ |
| _ 9 _ | _ 1 _ | _ 6 _ |
| _ _ _ | 4 _ _ | _ _ _ |
+-------+-------+-------+
| _ 7 5 | _ 6 _ | _ 3 _ |
| _ _ _ | _ _ _ | 4 _ _ |
| _ _ _ | _ _ 7 | _ 9 2 |
+-------+-------+-------+
+-------+-------+-------+
| 4 _ _ | _ 1 _ | _ _ 8 |
| _ 5 _ | _ _ _ | _ 2 _ |
| _ _ 6 | _ _ _ | 9 _ _ |
+-------+-------+-------+
| _ _ _ | 9 _ 2 | _ _ _ |
| 8 _ _ | _ 5 _ | _ _ 3 |
| _ _ _ | 1 _ 8 | _ _ _ |
+-------+-------+-------+
| _ _ 9 | _ _ _ | 6 _ _ |
| _ 2 _ | _ _ _ | _ 5 _ |
| 1 _ _ | _ 7 _ | _ _ 4 |
+-------+-------+-------+
+-------+-------+-------+
| 5 _ _ | _ _ 3 | _ _ _ |
| _ _ _ | 1 4 _ | _ 9 _ |
| 9 1 _ | _ 2 6 | 4 _ _ |
+-------+-------+-------+
| _ 6 _ | 9 _ _ | _ 5 _ |
| _ _ _ | _ _ 5 | 7 _ _ |
| _ _ _ | _ 8 _ | _ _ 4 |
+-------+-------+-------+
| 1 2 _ | _ _ _ | _ 7 3 |
| 8 _ _ | _ 1 _ | _ 6 _ |
| _ _ 6 | _ _ _ | _ _ 1 |
+-------+-------+-------+
+-------+-------+-------+
| 5 _ _ | _ 8 _ | _ _ _ |
| _ _ _ | 3 _ _ | 9 _ _ |
| 3 _ _ | _ 2 4 | _ _ 5 |
+-------+-------+-------+
| _ _ _ | _ 6 8 | _ 1 _ |
| _ _ 3 | _ _ 2 | _ _ _ |
| 8 _ _ | _ _ _ | _ 7 _ |
+-------+-------+-------+
| _ _ _ | _ 4 _ | _ 5 9 |
| _ _ 6 | 9 3 _ | _ _ 8 |
| _ 5 2 | _ _ _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| 5 _ 2 | 3 _ _ | 4 7 _ |
| _ _ 1 | _ 7 _ | _ _ 9 |
| _ _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ 5 _ |
| _ 3 _ | _ _ 4 | _ _ 6 |
| 7 _ _ | 5 _ _ | _ 9 _ |
+-------+-------+-------+
| _ _ _ | _ 5 _ | _ 1 _ |
| _ _ _ | _ _ 3 | 8 _ 7 |
| _ 8 _ | 4 _ 9 | _ 3 _ |
+-------+-------+-------+
+-------+-------+-------+
| 5 3 _ | _ _ _ | _ 7 _ |
| _ 9 _ | 3 1 _ | _ 8 _ |
| 6 _ _ | 9 _ _ | _ _ 1 |
+-------+-------+-------+
| _ _ 4 | _ _ _ | _ _ _ |
| _ _ 5 | _ 2 4 | _ _ _ |
| _ 8 _ | _ _ 6 | _ 1 _ |
+-------+-------+-------+
| _ _ _ | 8 _ _ | _ _ 7 |
| _ _ _ | _ _ _ | 8 9 _ |
| _ _ 6 | _ _ 9 | _ 5 2 |
+-------+-------+-------+
+-------+-------+-------+
| 6 _ _ | _ 4 _ | _ _ 3 |
| _ 1 _ | _ _ _ | _ 7 _ |
| _ _ 5 | _ _ _ | 8 _ _ |
+-------+-------+-------+
| _ _ _ | 5 _ 2 | _ _ _ |
| 3 _ _ | _ 9 _ | _ _ 2 |
| _ _ _ | 1 _ 3 | _ _ _ |
+-------+-------+-------+
| _ _ 8 | _ _ _ | 9 _ _ |
| _ 7 _ | _ _ _ | _ 5 _ |
| 2 _ _ | _ 3 _ | _ _ 4 |
+-------+-------+-------+
+-------+-------+-------+
| 6 _ _ | _ 7 _ | _ _ 9 |
| _ 1 _ | _ _ _ | _ 2 _ |
| _ _ 5 | _ _ _ | 4 _ _ |
+-------+-------+-------+
| _ _ _ | 1 _ 2 | _ _ _ |
| 9 _ _ | _ 8 _ | _ _ 6 |
| _ _ _ | 6 _ 9 | _ _ _ |
+-------+-------+-------+
| _ _ 1 | _ _ _ | 2 _ _ |
| _ 3 _ | _ _ _ | _ 4 _ |
| 7 _ _ | _ 5 _ | _ _ 8 |
+-------+-------+-------+
+-------+-------+-------+
| 6 _ 5 | _ _ _ | _ _ _ |
| 2 _ _ | 4 _ _ | _ 7 _ |
| _ 1 _ | _ 7 _ | 6 _ 9 |
+-------+-------+-------+
| 4 _ _ | _ _ _ | 7 _ _ |
| 1 9 _ | _ 3 _ | 8 _ _ |
| _ _ 3 | _ _ 9 | _ _ 2 |
+-------+-------+-------+
| _ 6 _ | 3 _ 8 | 9 _ _ |
| _ 4 _ | _ _ 7 | _ _ _ |
| _ _ _ | 1 _ _ | 2 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| 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 _ _ |
+-------+-------+-------+
+-------+-------+-------+
| 7 _ _ | _ 2 _ | _ _ 4 |
| _ 5 _ | _ _ _ | _ 8 _ |
| _ _ 1 | _ _ _ | 6 _ _ |
+-------+-------+-------+
| _ _ _ | 3 _ 7 | _ _ _ |
| 1 _ _ | _ 6 _ | _ _ 9 |
| _ _ _ | 5 _ 8 | _ _ _ |
+-------+-------+-------+
| _ _ 6 | _ _ _ | 5 _ _ |
| _ 8 _ | _ _ _ | _ 4 _ |
| 9 _ _ | _ 4 _ | _ _ 1 |
+-------+-------+-------+
+-------+-------+-------+
| 7 _ _ | 2 _ _ | 5 _ 9 |
| 2 _ _ | _ _ 3 | _ 7 8 |
| _ 6 _ | _ _ _ | _ 2 _ |
+-------+-------+-------+
| _ 2 _ | _ _ _ | _ _ 7 |
| 6 _ 9 | _ _ 5 | _ _ _ |
| _ 1 _ | _ 4 6 | _ _ _ |
+-------+-------+-------+
| _ _ 6 | 3 _ _ | _ 8 4 |
| _ _ _ | _ _ _ | 7 _ _ |
| _ _ _ | 8 9 _ | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| 8 _ 2 | _ _ _ | _ _ 4 |
| _ 9 _ | _ _ _ | _ _ 7 |
| _ _ 5 | _ _ 1 | 3 9 _ |
+-------+-------+-------+
| _ 8 _ | _ 1 7 | _ _ _ |
| _ _ _ | 5 _ 2 | _ _ 1 |
| _ _ _ | _ _ 8 | _ 3 6 |
+-------+-------+-------+
| _ _ 7 | 1 _ _ | _ _ _ |
| 4 _ _ | _ 7 _ | _ _ _ |
| 3 2 _ | _ _ 5 | _ _ _ |
+-------+-------+-------+
+-------+-------+-------+
| 9 _ _ | _ _ _ | 1 _ _ |
| _ 8 _ | _ 7 _ | _ _ _ |
| 3 _ _ | 9 _ _ | 8 _ _ |
+-------+-------+-------+
| _ 2 1 | 6 8 _ | _ _ _ |
| _ _ 9 | _ _ _ | _ _ _ |
| 8 _ _ | _ 9 _ | _ 2 _ |
+-------+-------+-------+
| 7 _ 6 | 4 _ _ | _ _ 2 |
| _ _ 5 | _ _ _ | _ 3 _ |
| _ _ 8 | 7 2 _ | _ _ 5 |
+-------+-------+-------+
+-------+-------+-------+
| 9 _ _ | _ 7 _ | _ _ 4 |
| _ 1 _ | _ _ _ | _ 5 _ |
| _ _ 8 | _ _ _ | 2 _ _ |
+-------+-------+-------+
| _ _ _ | 8 _ 9 | _ _ _ |
| 7 _ _ | _ 4 _ | _ _ 6 |
| _ _ _ | 2 _ 7 | _ _ _ |
+-------+-------+-------+
| _ _ 3 | _ _ _ | 1 _ _ |
| _ 2 _ | _ _ _ | _ 8 _ |
| 6 _ _ | _ 9 _ | _ _ 7 |
+-------+-------+-------+
cheers
Simon
Simon Kröger
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, :possibilities
def initialize cells
@possibilities = Array.new(81) {(1..9).to_set}
@cells = Array.new(81){0}
81.times{|i|set_cell(i, cells[i]) if cells[i] != 0}
end
def set_cell c, v
@@neighbourhoods[c].flatten.each{|i|
possibilities[i]-=[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[i]
@@neighbourhoods[i].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[i].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[i]).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
----------------------------------------------------------------------
cheers
Simon
Vance A Heron
make after looking at Simons answer...
I find it interesting comparing the times of Simons pgm
vs mine - his is faster about half the time, but in a
one case, his program runs in .9 Seconds, while mine
takes 85.7 ... a huge difference.
The one that's hardest for mine to solve is:
+-------+-------+-------+
| 3 1 _ | 6 _ _ | _ _ _ |
| _ _ 2 | _ _ _ | _ _ _ |
| _ 5 _ | _ 9 _ | 7 8 _ |
+-------+-------+-------+
| _ _ _ | _ _ 5 | _ _ _ |
| _ 9 _ | _ 1 _ | _ 6 _ |
| _ _ _ | 4 _ _ | _ _ _ |
+-------+-------+-------+
| _ 7 5 | _ 6 _ | _ 3 _ |
| _ _ _ | _ _ _ | 4 _ _ |
| _ _ _ | _ _ 7 | _ 9 2 |
+-------+-------+-------+
although his finds that there's no solution
for
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| 7 _ _ | _ 8 _ | 3 _ _ |
| _ _ _ | 7 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ 9 | _ 1 _ | _ _ _ |
| _ _ _ | _ _ 7 | _ _ _ |
+-------+-------+-------+
| _ _ 1 | _ _ 8 | _ 2 _ |
| _ _ _ | _ 2 6 | _ _ 1 |
| _ _ _ | 3 _ 5 | _ _ _ |
+-------+-------+-------+
in about 0.2 S.
Here's my (first) solution ...
-----
class Sudoku
def initialize(dbg = false)
@dbg = dbg
@board = []
end
def read(fname = STDIN)
while line = gets
next unless line =~ /^[\d\|]/
line.gsub!(/,/, ' ')if line =~ /^\d/ # to keep working w/old
boards
@board << line.gsub(/\|/,'').split(' ').map{|p| p.to_i}
end
end
def to_s
tb = "+-------+-------+-------+\n"
out = ''
@board.each_with_index{|row,rndx|
out += tb if rndx % 3 == 0
row.each_with_index{|cell, cndx|
out += '| ' if cndx % 3 == 0
out += cell == 0 ? "_ " : "#{cell} "
}
out += "|\n"
}
out += tb
end
def solve
begin
fill_spec # fill fully specified spaces
rescue
return # if try made illegal partial ...
end
if count_zeros > 0 # some empty spaces
sav = []
copy_board(sav,@board) # save last known legal bd
x,y = first_zero
choices = find_choices(x,y)
choices.each{|v| # try each possible choice for a 0
copy_board(@board,sav)
@board[x][y] = v
puts "Try #{x},#{y} <- #{v}" if @dbg
self.solve # recurse...
break if count_zeros == 0
}
end
end
# fill fully specified entries
def fill_spec
zeros = count_zeros # how many to fill
begin
last_zeros = zeros
(0..8).each{|i|
(0..8).each{|j|
next if @board[i][j] != 0 # skip filled spaces
choices = find_choices(i, j)
raise "Illegal Board #{i+1} #{j+1}" if choices.length == 0
@board[i][j] = choices[0] if choices.length == 1
}
}
zeros = count_zeros
# if filled some, possibly others are now fully specified
end while ((zeros > 0) && (last_zeros > zeros))
end
def find_choices (x, y) # get all choices for a given location
choices = Array.new(9) {|i| i+1}
# remove numbers from same line & row
(0..8).each{|i|
choices[@board[x][i] -1] = 0 if (@board[x][i] != 0 ) # rm digits
in row
choices[@board[i][y] -1] = 0 if (@board[i][y] != 0 ) # rm digits
in col
}
# remove numbers from same square ...
xs = (x/3) * 3
xe = xs + 2
ys = (y/3) * 3
ye = ys + 2
(xs..xe).each{|i|
(ys..ye).each{|j|
choices[(@board[i][j]) - 1] = 0 if (@board[i][j] != 0)
}
}
choices.delete_if {|v| v == 0}
end
def count_zeros # to determine if I'm done ...
@board.inject(0){|sum, row| sum += row.select{|e| e == 0}.length }
end
def copy_board(dst, src)
(0..8).each{|i| dst[i] = src[i].dup}
end
def first_zero
(0..8).each{|j| (0..8).each{|i| return i,j if @board[i][j] == 0 }}
end
end
dbg = ARGV[0] =~ /-d/ ? true : false
ARGV.shift if dbg
bd = Sudoku.new(dbg)
bd.read(ARGV[0])
puts "Input\n#{bd}"
bd.solve
puts bd.count_zeros == 0 ? "Solution\n#{bd}" : "Unsolvable\n#{bd}"
----
Vance
David Tran
have only one unique solution per puzzle.
I simply slightly modified my previous quiz solution to show all
possible solutions.
Added show_all_solutions ( almost the same as solve method )
class Sodoku
attr_reader :solutions
def initialize( input )
@ary = Array.new(9) { Array.new(9) } # 9 rows x 9 columns
@solutions = 0
def show_all_solutions
9.times do |row|
9.times do |col|
next if @ary[row][col]
shift_row = row / 3 * 3
shift_col = col / 3 * 3
# find next possible value for @ary[row][col]
1.upto(9) do |v|
# check on same row/col, no any col/row already used it
next unless 9.times { |i| break if @ary[i][col] == v ||
@ary[row][i] ==v }
# check on 3x3 box, no other cell already used it
next unless 3.times do |i|
break unless 3.times do |j|
break if @ary[i + shift_row][j + shift_col] == v
end
end
@ary[row][col] = v
show_all_solutions
@ary[row][col] = nil # backtracking
end
return
end
end
@solutions += 1
puts to_s
end
def to_s
s = "+-------+-------+-------+\n"
@ary.each_with_index do |row, index|
row = row.map { |e| e ||= '_' } * ' '
row[6,0] = row[12,0] = '| '
s << '| ' << row << " |\n"
s << "+-------+-------+-------+\n" if [2, 5, 8].include?(index)
end
s
end
end
if __FILE__ == $0
input = ''
while line = gets
input << line
end
sodoku = Sodoku.new(input)
sodoku.show_all_solutions
puts "Total #{sodoku.solutions} solutions."
end
__END__
if your input is like:
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
It will show you all 6,670,903,752,021,072,936,960 solutions.
( This number is equivalent to 9! × 722 × 27 × 27,704,267,971 )
How long it takes? I don't know, and I do not like try it ;-)
Back to the quiz, the puzzle is
+-------+-------+-------+
| _ 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 _ |
+-------+-------+-------+
my show_all_solutions takes only ~ 0.515 seconds (on my machine)
to find it has only one unique solution.
And later I try the only 17 cells numbers
( Currently it is the minimum cell numbers puzzle and still has unique
solution )
+-------+-------+-------+
| _ _ 6 | 9 _ _ | _ 7 _ |
| _ _ _ | _ 1 _ | _ _ 2 |
| 8 _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ 2 _ | _ _ _ | _ _ 4 |
| _ _ _ | _ _ _ | _ _ 1 |
| _ _ 5 | _ _ 6 | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ 6 _ |
| _ _ _ | _ _ 2 | _ 5 _ |
| _ 1 _ | _ 4 3 | _ _ _ |
+-------+-------+-------+
This time, it takes ~ 3116.285 seconds to make sure it has only one
unique solution.
However, my program is kind of translate from my java program.
My origin Java program is something like:
static void SolvePuzzle() {
ShowAllAns();
}
static void ShowAllAns() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (puzzle[i][j] <= 0) {
next_value: for (int value = 1; value <= 9; value++) {
// On the same column, make sure no any row already used it
// On the same row, make sure no any column already used it
for (int k = 0; k < 9; k++) {
if ((puzzle[k][j] == value) || (puzzle[i][k] == value)) {
continue next_value;
}
}
// On the 3x3 box, make sure no other cell already used it
int p = (i / 3) * 3;
int q = (j / 3) * 3;
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (puzzle[p+x][q+y] == value) {
continue next_value;
}
}
}
puzzle[i][j] = value;
ShowAllAns();
puzzle[i][j] = 0;
}
return; // tried all possible value, just return
}
}
}
PrintPuzzle();
}
And the java program solves the 17 cell numbers puzzle takes only ~ 10969 ms.
So for the same "algorithm", for the same problem ( 17 cell numbers,
find and make sure unique solution ),
the java one takes ~ 11 seconds and the ruby one takes ~ 1 hour.
I may need to refactor my ruby program ...
Adam Shelly
I've been messing with ruby for about a year. I actually wrote a version of
this solver with a fxwindows gui a while ago. The quiz was a good excuse to
clean it up and refactor it to handle text input.
It takes grids of almost arbitrary sizes upto 16 (and could be extended
more). It doesn't do any guessing, so it never solves some of the posted
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
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
attr_reader :row, :col, :group, :possible
def initialize(row, col, val=-1, max = 9)
@row = row
@col = col
bounds = GetGroupBounds(max)
@group = col/(bounds[0])+((row/bounds[1])*bounds[1])
@solved = false
case val
when 1..max
@possible = [val]
else
@possible = (1..max).to_a
end
end
def includes?(n)
@possible.include?(n)
end
def markSolved
@solved = true
end
def set(toValue)
if (found = @possible.include?(toValue))
@possible = [toValue];
end
return found
end
def hasFinalValue
if (@possible.length == 1)
return @possible[0]
end
end
def eliminate(n)
@possible.delete(n)
return hasFinalValue && !@solved
end
def show
(v = hasFinalValue)?" "+v.to_s(32):" _"
end
def to_s #for debugging
s = @possible.to_s;
s.length.upto(9) do s << " " end
"(#{row},#{col})["+s+"]"
end
end
class Solver
def initialize(boardlist, size)
@groups =[]
@rows =[]
@cols = []
@queue = [] #a list of cells to check for solutions.
@size = size
0.upto(@size-1) { |n| @groups[n] = [] ; @rows[n]=[]; @cols[n]=[] }
r=c=0
boardlist.each do |v|
cell = Cell.new(r,c,v, size)
@groups[cell.group] <<@rows[r][c] = @cols[c][r] = cell
@queue << cell
c+=1
if (c==size) then c=0; r=r+=1 end
end
end
def solve
while @queue.size > 0
while (cell = @queue.pop)
eliminateChoices(cell)
end
checkForKnownValues()
end
end
#for any resolved cell, eliminate its value from the possible values of the
other cells in the set
def eliminateChoices(cell)
value = 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|
eliminateValueFromCell(n,cell) if (cell != exceptThisCell)
end
end
def eliminateValueFromCell(value, cell)
if (cell.eliminate(value) && !@queue.include?(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 = nil
set.each do |c| #in every cell in the set
if (c.includes?(n))
if (c.hasFinalValue || lastCell) #found a 2nd instance
lastCell = nil
break
end
lastCell = c;
end
end
#if true, there is only one cell in the set with that value, so be the
answer
if (lastCell && !lastCell.hasFinalValue)
lastCell.set(n)
@queue << lastCell
end
end
end
#find any pair of cells in a set with the same 2 possibilities
# - 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 != m && set[n].possible.size == 2 && set[n].possible ==
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|
if (!skipList.include?(i))
values.each {|v| eliminateValueFromCell(v, set[i])}
end
end
end
#formating (vertical line every cbreak)
def showBorder(cbreak)
s = "+"
1.upto(@size) do |n|
s << "--"
if ((n)%cbreak == 0) then s<< "-+" end
end
s <<"\n"
end
def show
r=c=0
cbreak,rbreak = GetGroupBounds(@size)
s = showBorder(cbreak)
@rows.each do |row|
r+=1
s << "|"
row.each do |cell|
c+=1
s << cell.show
if (c==cbreak) then s << " |";c=0; end
end
s<<"\n"
if (r==rbreak) then s << showBorder(cbreak); r=0; end
end
s<<"\n"
print s
end
end
#parses text file containing board. The only significant characters are _,
0-9, A-Z.
#there must be an equal number of significant chars in each line, and the
same number of many rows.
def ParseBoard(file)
row = 0
col = 0
boardlist = [ ]
file.each do |line|
line.chomp.each_byte do |c|
case c
when ?A..?Z
boardlist << c.to_i - ?A + 10
col+=1
when ?0..?9
boardlist << c.to_i - ?0
col+=1
when ?_
boardlist << -1
col+=1
end
end
if (col > 0) then
row+=1
if (row == col) then break end
end
col=0
end
return boardlist,row
end
if __FILE__ == $0
boardlist, size = ParseBoard(ARGF)
sol = Solver.new(boardlist, size)
sol.show
sol.solve()
sol.show
end
--
-Adam Shelly
Adam Shelly
On 8/22/05, Adam Shelly <adam....@gmail.com> wrote:
>
> Hi. This is my first attempt at a ruby quiz, and my first post to
> ruby-talk.
..
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
Dennis Ranke
> sudoku.rb [input file]
It solves the puzzles using some logic rules and brute force where needed.
As a small bonus it can also generate a puzzle by starting it with
> sudoku.rb gen
The generator works by first letting the solver solve the empty puzzle
(and thereby generating a random solution) and then, again starting from
the emtpy puzzle, adding values from the solution to the puzzle until it
is solvable using logic alone.
---
class Cell
attr_reader :sets, :value, :mask
LOG2 = Math.log(2)
def initialize(mask)
self.mask = mask
@sets = []
end
def add_set(s)
@sets << s
end
def mask=(m)
@mask = m
@value = (Math.log(@mask) / LOG2).round + 1 if @mask & (@mask-1) == 0
end
def apply_mask(v)
return false if @mask & v == @mask
throw :failed if @mask & v == 0
self.mask = @mask & v
end
def choices
mask = @mask
c = []
while mask != 0
b = mask & ~(mask-1)
c << b
mask &= ~b
end
c
end
end
class Set
def initialize(cells)
@cells = cells
@open = cells.inject(0) {|m, c| m |= c.mask }
end
def simple_masking
mask = 0
@cells.delete_if do |c|
if v = c.value
b = 1 << (v-1)
throw :failed if @open & b == 0
@open ^= b
mask |= b
true
else
false
end
end
return false if mask == 0
@cells.each {|c| c.apply_mask(~mask) }
return true
end
def place_numbers
active = false
9.times do |n|
mask = 1 << n
next unless @open & mask != 0
cells = @cells.select {|c| c.mask & mask != 0}
if cells.size == 1
cells.first.apply_mask(mask)
active = true
end
next if cells.size <= 1
sets = cells.inject([]) {|a, c| a += c.sets}
sets.uniq!
sets.delete(self)
sets.each {|s| active |= s.mask_if_contains(cells, ~mask)}
end
active
end
def mask_if_contains(cells, mask)
my_cells = @cells.dup
cells.each do |c|
return false unless my_cells.delete(c)
end
active = false
my_cells.each {|c| active |= c.apply_mask(mask)}
active
end
def finished?
@cells.empty?
end
end
class Puzzle
attr_accessor :guessing_used
def initialize(board)
@board = board.map {|c| Cell.new(c) }
@sets = []
9.times do |i|
@sets << Set.new(@board[i*9, 9])
column = (0...9).map {|y| @board[y*9 + i]}
@sets << Set.new(column)
x = i % 3
y = i / 3
block = @board[x*3 + y*27, 3] + @board[x*3 + y*27 + 9, 3] +
@board [x*3 + y*27 + 18, 3]
@sets << Set.new(block)
end
@guessing_used = false
end
def solve
self.copy.solve!
end
protected
def solve!(try_brute_force = true)
catch :failed do
while run
# puts "\n---\n\n"
# puts self
end
return self if finished?
return false unless try_brute_force
best_cells = nil
best_choices_count = 10
@board.each do |c|
choices = c.choices
if choices.size > 1 && choices.size <= best_choices_count
best_cells = [] if choices.size < best_choices_count
best_cells << c
best_choices_count = choices.size
end
end
cell = best_cells[rand(best_cells.size)]
choices = cell.choices
until choices.empty?
c = choices.delete_at(rand(choices.size))
cell.mask = c
if solution = self.copy.solve!
solution.guessing_used = true
return solution
end
end
end
return nil
end
def run
active = false
@sets.each {|s| active |= s.simple_masking }
return true if active
@sets.each {|s| active |= s.place_numbers}
active
end
def copy
Puzzle.new(to_a)
end
public
def to_s
lines = (0...9).map do |y|
line = @board[y*9, 9].map do |c|
if v = c.value
v.to_s
else
'.'
end
end
(0...3).map {|i| line[i*3, 3].join}.join('|')
end
(0...3).map {|i| lines[i*3, 3].join("\n")}.join("\n---+---+---\n")
end
def finished?
@sets.all? {|c| c.finished? }
end
def to_a
@board.map {|c| c.mask}
end
def self.from_string(string)
board = string.scan(/[\.1-9]/)
raise unless board.size == 81
board = board.map do |c|
c == '.' ? 511 : 1 << (c.to_i - 1)
end
self.new(board)
end
def create_puzzle
solution = solve!.to_a
cells = (0...81).to_a
board = [511] * 81
loop do
cell = cells[rand(cells.size)]
board[cell] = solution[cell]
puzzle = Puzzle.new(board)
if puzzle.solve!(false)
return Puzzle.new(board)
else
b = puzzle.to_a
81.times do |i|
if b[i] & (b[i] - 1) == 0
cells.delete(i)
end
end
end
end
end
def self.create
self.new([511] * 81).create_puzzle
end
end
if ARGV[0] == 'gen'
puzzle = Puzzle.create
puts puzzle
exit
end
puzzle = File.read(ARGV[0]).gsub(/[+\-|\s]/, '').gsub(/\D/, '.')
puzzle = Puzzle.from_string(puzzle)
puts puzzle
start_time = Time.now
if solution = puzzle.solve
if solution.guessing_used
puts "\nSolved using guessing\n\n"
else
puts "\nSolved\n\n"
end
puts solution
else
puts "\nfailed to solve puzzle\n\n"
end
printf "%f seconds\n\n", Time.now - start_time
Kroeger Simon (ext)
Ok, I couldn't resist.
Here is my version using bit operations rather than Sets:
(The logic is exactly the same, not very optimal but twice
as fast as with Sets nevertheless - I hacked this very quick,
I hope there are no major flaws in it)
-------------------------------------------------------------
require 'Set'
require 'Benchmark'
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)}}
# this contains the 3 'neighbourhoods' (row/col/box)
# of each of the 81 cells
NEIGHBOURHOODS = Array.new(81) {|o|
[row[o / 9], col[o % 9], box[(o / 27) * 3 + (o % 9) / 3]]}
COMBINEDNEIGHBOURS = Array.new(81) {|o|
NEIGHBOURHOODS[o].flatten.uniq! - [o]}
SINGLEBIT = (1..9).inject({}){|h, i| h[1 << i] = i; h}
def numbits i
c = (i & 1)
while (i = i >> 1) > 0
c += (i & 1)
end
c
end
def eachbit i
c = 0
while i >= (1 << (c+=1))
yield c if (i & (1 << c)).nonzero?
end
end
class Board
attr_reader :cells, :possibilities
#initializes the cells and possibilities
def initialize c
@possibilities = Array.new(81) {(1..9).inject(0){|r, v| r |= 1 << v}}
@cells = Array.new(81, nil)
81.times{|i|set_cell(i, c[i]) if c[i]}
end
def initialize_copy(b)
@cells = b.cells.clone
@possibilities = b.possibilities.clone
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] || "_"
end.join(" ")
end.join(" | ")
end.join(" |\n| ")
end.join(" |\n+-------+-------+-------+\n| ") +
" |\n+-------+-------+-------+\n"
end
#recursively sets cell 'c' to 'v' and all trivial dependend cells
def set_cell c, v
cells[c], possibilities[c], mask = v, 1 << v, ~(1 << v)
COMBINEDNEIGHBOURS[c].each{|i| possibilities[i] &= mask}
COMBINEDNEIGHBOURS[c].each do |i|
if !cells[i] && (v = SINGLEBIT[possibilities[i]])
set_cell(i, v)
end
end
return self
end
#solves with logic and brute force if neccessary',
#returns nil if unsolvable
def solve!
c = i = changed = 0
while i = ((i+1)..(changed+81)).find{|x|!cells[x % 81]}
NEIGHBOURHOODS[c = i % 81].each do |neighbours|
pn = neighbours.inject(possibilities[c]){|r, j| (j != c) ? (r &
~possibilities[j]) : r}
if v = SINGLEBIT[pn]
set_cell(changed = i = c, v)
break
end
end
end
return self if cells.all?
return nil if possibilities.any?{|p| p.zero?}
p, i = possibilities.zip((0..80).to_a).select{|a, b|numbits(a) > 1}.
min{|a, b|numbits(a[0]) <=> numbits(b[0])}
eachbit(p){|j| b=clone.set_cell(i, j).solve! and return b}
return nil
end
end
# main
count, $stdout.sync, total = 0, true, Benchmark::Tms.new
Benchmark.bm(15, "total", "average") do |bm|
loop do
cells = []
while !ARGF.eof? && (cells.size < 81) do
ARGF.gets.scan(/[0-9_.]/).each{|c| cells << c.to_i.nonzero?}
end
break if ARGF.eof?
board = nil
total += bm.report("solving nr #{count+=1}") do
board = Board.new(cells).solve!
end
puts board ? board.to_s : "UNSOLVEABLE!" + "\n\n"
end
[total, total / count]
end
-------------------------------------------------------------
cheers
Simon
Adam Shelly
> If so, download a newer version :) or replace
Thanks, that was it.
And congrats, you win :) I modified your code to run a single puzzle
at at time, and ran the set of 55 puzzles:
$ for i in *.sdk; do time ruby MySolver.rb $i ;done >tmy 2>&1
$ ruby parsetimes.rb tmy
min max total ave
0.037 0.722 11.55 0.21
$ for i in *.sdk; do time ruby SKSolver.rb $i ;done >tsk 2>&1
$ ruby parsetimes.rb tsk
min max total ave
0.049 0.331 10.043 0.1826
Your time on the hard ones is twice as fast as mine.
I really like the idea of the COMBINED_NEIGHBORHOODS array.
I think I learned a lot by deciphering your code even if I'm still not
sure I completely understand the main loop.
-adam
Adam Shelly
> I believe Adam Shelly's parse routine could benefit from similar simplifications
> if you want to try your own hand at a little refactoring.
Ok, I admit I'm a ruby newbie. But I'm trying to learn the Ruby Way.
How's this?
Was:
def ParseBoard(file)
row = 0
col = 0
boxes = 0
boardlist = [ ]
file.each do |line|
line.chomp.each_byte do |c|
case c
when ?0..?9
boardlist << c.to_i - ?0
col+=1
when ?A..?Z
boardlist << c.to_i - ?A + 10
col+=1
when ?a..?z
boardlist << c.to_i - ?a + 10
col+=1
when ?_
boardlist << -1
col+=1
when ?+
boxes+=1 if row == 0
end
end
if (col > 0) then
row+=1
break if (row == col)
end
col=0
end
@@boxcols = boxes-1
return boardlist,row
end
Is:
def ParseBoard(file)
boardlist,size = [ ],0
file.each do |line|
if line.delete!('^0-9A-Za-z_+') =~ /\++/
@@boxcols= line.length-1
else
boardlist += line.split(//).collect{|n| n.hex }
size = line.length
end
p line
end
boardlist,size
end
The only difference is it adds 0's to the boardlist where it used to
add -1's, but the solver constructor handles anything outside 1..size
the same, so it doesn't matter.
It doesn't handle malformed input well, but neither did the old
version. That's for another exercise, maybe.
-Adam
David Brady
> On Aug 24, 2005, at 7:36 AM, James Edward Gray II wrote:
>
>> line.delete!("+-| ")
>
> Oooh, I didn't know/forgot about that method. Nice :)
These are all new to me. I learned Ruby by skimming the manual for the
syntax needed to express my C++ thinking in Ruby. :-)
When I discovered gsub! took a regex, I went back and reread some of the
String documentation. I was going to use
line.squeeze ' '
But line.delete is more clear. I'll probably still use gsub! before it,
because to my thinking the proper behavior is to throw away all
characters that aren't digits. Dono... we're into "proper parsing of
invalid input" at this point. I only squeeze the whitespace because I
was using split() to break up the input. That may be unecessary (split
/\s+/) or avoidable (remove all whitespace, iterate over chars).
James, I'll edit the code, because these are nice changes. I hate to
spam the list, but I'm assuming that reposting is the preferred way to
update code for the Quiz, since you simply reference the web archive of
the post directly?
-dB
--
David Brady
ruby...@shinybit.com
I'm feeling really surreal today... OR AM I?
James Edward Gray II
> If nothing else, how about:
> line.gsub!( /[+| -]/, '' )
Or:
line.delete!("+-| ")
James Edward Gray II
Simon Kröger
> So that's why mine got better, but it was bad before.
> I'd like to directly compare the speed of yours to mine on my machine,
> but I can't get it to run correctly, It reports every board as UNSOLVABLE.
> Has anyone else had any luck with it?
Is it posiible that you use ruby 1.8.1 or older?
If so, download a newer version :) or replace
COMBINEDNEIGHBOURS[c].each{|i|possibilities[i].delete(v)}
by
COMBINEDNEIGHBOURS[c].each{|i|possibilities[i] -= [v]}
I hope that helps (but makes it slower!)
cheers
Simon
Kroeger Simon (ext)
> Ok, here's my latest. My big speedup was figuring out that if I make
> a bad guess, I just eliminate that possibility and re-solve. See the
> startGuessing method..
hmm ... I use cells with only 2 possibilities left for guessing, so if I
guess wrong, at least I know the right guess. (of course only if there
are cells with 2 possibilities - but that happens often) If I interpret
your guess method right you are doing the same thing. So I do not
understand where the speedup comes from.
BTW a lot of speed comes from rather minor changes, like changing
a_set -= [a_value]
to
a_set.delete(a_value)
this makes a HUGE difference. This is obvious if you take some time
to think about it, but it would be realy nice to optimize operators
like -= where you have no chance to use the intermediate objects anyway.
And I don't know why
Set.new(another_set)
seems to be faster than
another_set.clone
I didn't take the time to look into the implementations, yet.
Your 'findPairs' looks promissing... I think I will try something
similar...
> It now solves #30 in 0.194s, and #55 in 0.124
Impressive!
> ( I'm not sure which puzzle you called #1)
The one posted by David Tran, with only 17 numbers given:
+-------+-------+-------+
| _ _ 6 | 9 _ _ | _ 7 _ |
| _ _ _ | _ 1 _ | _ _ 2 |
| 8 _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ 2 _ | _ _ _ | _ _ 4 |
| _ _ _ | _ _ _ | _ _ 1 |
| _ _ 5 | _ _ 6 | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ 6 _ |
| _ _ _ | _ _ 2 | _ 5 _ |
| _ 1 _ | _ 4 3 | _ _ _ |
+-------+-------+-------+
cheers
Simon
Vance A Heron
Input
+-------+-------+-------+
| _ 2 _ | _ _ _ | _ _ _ |
| _ _ _ | 6 _ _ | _ _ 3 |
+-------+-------+-------+
| _ _ _ | _ _ 3 | _ _ 2 |
| 6 _ _ | 5 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ 1 _ | 7 8 _ |
| 5 _ _ | _ _ 9 | _ _ _ |
| _ _ _ | _ _ _ | _ 4 _ |
+-------+-------+-------+
+-------+-------+-------+
| 1 2 6 | 4 3 7 | 9 5 8 |
| 8 9 5 | 6 2 1 | 4 7 3 |
| 3 7 4 | 9 8 5 | 1 2 6 |
+-------+-------+-------+
| 4 5 7 | 1 9 3 | 8 6 2 |
| 9 8 3 | 2 4 6 | 5 1 7 |
| 6 1 2 | 5 7 8 | 3 9 4 |
+-------+-------+-------+
| 2 6 9 | 3 1 4 | 7 8 5 |
| 5 4 8 | 7 6 9 | 2 3 1 |
| 7 3 1 | 8 5 2 | 6 4 9 |
+-------+-------+-------+
real 0m5.160s
user 0m5.150s
sys 0m0.000s
On Tue, 2005-08-23 at 21:15 +0900, Kroeger Simon (ext) wrote:
>
> > From: Brian Schröder [mailto:ruby....@gmail.com]
>
> > > | 7 1 3 | 2 1 8 | 2 4 9 | <----eE.G: two 1s in this row
> > > +-------+-------+-------+
> > >
> > > ? (I missed something, right?)
> >
> > Yes, see above
>
> Thanks!
>
> Simon
>
David Tran
> ...
> And it took a while to figure out that this one was unsolvable:
> +-------+-------+-------+
> | _ 2 _ | _ _ _ | _ _ _ |
> | _ _ _ | 6 _ _ | _ _ 3 |
> | _ 7 4 | _ 8 _ | _ _ _ |
> +-------+-------+-------+
> | _ _ _ | _ _ 3 | _ _ 2 |
> | _ 8 _ | _ 4 _ | _ 1 _ |
> | 6 _ _ | 5 _ _ | _ _ _ |
> +-------+-------+-------+
> | _ _ _ | _ 1 _ | 7 8 _ |
> | 5 _ _ | _ _ 9 | _ _ _ |
> | _ _ _ | _ _ _ | _ 4 _ |
> +-------+-------+-------+
Euh ... mmm....
my program tell me that is one has unique solution ( on 16.672 seconds )
Simon Kröger
> On 8/25/05, Ruby Quiz <ja...@grayproductions.net> wrote:
>
>>I believe Adam Shelly's parse routine could benefit from similar simplifications
>>if you want to try your own hand at a little refactoring.
>
>
> Ok, I admit I'm a ruby newbie. But I'm trying to learn the Ruby Way.
> How's this?
>
> Was:
>
> [...c-style ruby code...]
>
> Is:
> def ParseBoard(file)
> boardlist,size = [ ],0
> file.each do |line|
> if line.delete!('^0-9A-Za-z_+') =~ /\++/
> @@boxcols= line.length-1
> else
> boardlist += line.split(//).collect{|n| n.hex }
> size = line.length
> end
> p line
> end
> boardlist,size
> end
>
> The only difference is it adds 0's to the boardlist where it used to
> add -1's, but the solver constructor handles anything outside 1..size
> the same, so it doesn't matter.
> It doesn't handle malformed input well, but neither did the old
> version. That's for another exercise, maybe.
>
> -Adam
much better!
i have another version for you:
def parse_board(file)
@@boxcols= (s = file.read).scan(/[+-]+/).size() -1
boardlist = s.scan(/[0-9A-Za-z_]/).map{|c| c.hex}
return boardlist, Math.sqrt(boardlist.size).to_i
end
assuming that boxcols is the number of boxes in horizontal or
vertical direction, boardlist is one array (e.g. with 81 cells
for a 9x9 board) and the second return parameter is the number
of columns or rows. right?
cheers
Simon
David Tran
(Someone maybe already sick to see my posts)
I only try to improve myself, everytime, I try to make it better (
clean / elegant / performance ).
I was excited to see my solutions for the same problem from 15 sec
down to 6 sec and now down to ~ 1 sec ...
Here is my other solution:
class Sudoku
attr_reader :solutions
def initialize( input )
@cells = Array.new(81)
@possibilities = {}
@solutions = 0
index = 0
input.to_s.scan(/./) do |c|
case c
when '1'..'9' : @possibilities[index] = [ @cells[index] = c.to_i ]
when '_' : @possibilities[index] = (1..9).to_a
else next
end
break if (index += 1) == 81
end
# raise "Input data incomplete" if index != 81
end
def solve
return false unless reduce_possibilities(@possibilities)
return _solve(@possibilities)
end
# to_s borrow from Simon ...
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] || "_"
end.join(" ")
end.join(" | ")
end.join(" |\n| ")
end.join(" |\n+-------+-------+-------+\n| ") +
" |\n+-------+-------+-------+\n"
end
private
# The cell's neighborhoods are cells need to check to be sure no duplicate
# value with the cell. It has exactly 20 cells neighborhoods per cell.
NEIGHBORHOODS = Array.new(81) do |index|
row, col = index / 9, index % 9
r, c = row / 3 * 3, col / 3 * 3
ary = []
9.times do |i|
ary << (i * 9 + col) # add cells at the same column
ary << (row * 9 + i) # add cells at the same row
ary << ((i/3) + r) * 9 + (i%3) + c # add cells at the same 3x3 box
end
ary.uniq - [index]
end
def reduce_possibilities(possibilities)
index = number = nil
while possibilities.find { |index, number| number.size == 1 }
@cells[index] = number[0]
possibilities.delete(index)
neighborhoods = NEIGHBORHOODS[index]
possibilities.each do |key, value|
next unless neighborhoods.include?(key)
value -= number
if value.size == 0
return false
else
possibilities[key] = value
end
end
end
true
end
def _solve(possibilities)
return true if possibilities.empty?
key, values = possibilities.shift
values.each do |v|
pos = possibilities.dup
pos[key] = [v]
next unless reduce_possibilities(pos)
return true if _solve(pos)
end
false
end
end
if __FILE__ == $0
input = ''
while line = gets
input << line
end
sudoku = Sudoku.new(input)
puts sudoku.solve ? sudoku : "This puzzle has no solution!"
end
David Tran
the while loop may reduce some cells to unique possibility number,
so set back to the cells data to reduce brute force steps.
class Sodoku
attr_reader :solutions
def initialize( input )
@cells = Array.new(81)
@possibilities = {}
@solutions = 0
index = 0
input.to_s.scan(/./) do |c|
case c
when '1'..'9' : @possibilities[index] = [ @cells[index] = c.to_i ]
when '_' : @possibilities[index] = (1..9).to_a
else next
end
break if (index += 1) == 81
end
# raise "Input data incomplete" if index != 81
end
def solve
return false unless reduce_possibilities # reduce only once then
return _solve(0) # brute force to solve it
end
def show_all_solutions
return unless reduce_possibilities # reduce only once then
_solve_all(0) # brute force to solve all solutions
end
index = number = nil
while @possibilities.find { |index, number| number.size == 1 }
@cells[index] = number[0] # add this line compare to previous program
@possibilities.delete(index)
neighborhoods = NEIGHBORHOODS[index]
@possibilities.each do |key, value|
next unless neighborhoods.include?(key)
value -= number
if value.size == 0
return false # invalid input data
else
@possibilities[key] = value
end
end
end
true
end
def _solve(start)
start.upto(80) do |index|
next if @cells[index]
@possibilities[index].each do |value|
next if NEIGHBORHOODS[index].any? { |i| @cells[i] == value }
@cells[index] = value
_solve(index + 1) ? (return true) : @cells[index] = nil
end
return false
end
true
end
def _solve_all(start)
start.upto(80) do |index|
next if @cells[index]
@possibilities[index].each do |value|
next if NEIGHBORHOODS[index].any? { |i| @cells[i] == value }
@cells[index] = value
_solve_all(index + 1)
@cells[index] = nil
end
return
end
@solutions += 1
puts self
end
end
if __FILE__ == $0
input = ''
while line = gets
input << line
end
sodoku = Sodoku.new(input)
puts sodoku.solve ? sodoku : "No solution"
# sodoku = Sodoku.new(input)
# sodoku.show_all_solutions
# puts "Total #{sodoku.solutions} solutions."
end
Simon Kröger
> Should I post my third version, or is everyone sick of looking at my
> code by now?
>
> -Adam
You have been busy, hmm?
I also did some refactoring:
user system total real
solving nr 1 0.062000 0.000000 0.062000 ( 0.093000)
+-------+-------+-------+
| 1 4 6 | 9 2 8 | 3 7 5 |
| 5 9 3 | 6 1 7 | 8 4 2 |
| 8 7 2 | 4 3 5 | 9 1 6 |
+-------+-------+-------+
| 7 2 1 | 3 5 9 | 6 8 4 |
| 9 6 8 | 2 7 4 | 5 3 1 |
| 4 3 5 | 1 8 6 | 2 9 7 |
+-------+-------+-------+
| 2 5 7 | 8 9 1 | 4 6 3 |
| 3 8 4 | 7 6 2 | 1 5 9 |
| 6 1 9 | 5 4 3 | 7 2 8 |
+-------+-------+-------+
..
solving nr 30 1.235000 0.015000 1.250000 ( 1.281000)
+-------+-------+-------+
| 1 2 6 | 4 3 7 | 9 5 8 |
| 8 9 5 | 6 2 1 | 4 7 3 |
| 3 7 4 | 9 8 5 | 1 2 6 |
+-------+-------+-------+
| 4 5 7 | 1 9 3 | 8 6 2 |
| 9 8 3 | 2 4 6 | 5 1 7 |
| 6 1 2 | 5 7 8 | 3 9 4 |
+-------+-------+-------+
| 2 6 9 | 3 1 4 | 7 8 5 |
| 5 4 8 | 7 6 9 | 2 3 1 |
| 7 3 1 | 8 5 2 | 6 4 9 |
+-------+-------+-------+
..
solving nr 55 0.625000 0.016000 0.641000 ( 0.672000)
+-------+-------+-------+
| 9 3 5 | 1 7 2 | 8 6 4 |
| 2 1 6 | 9 8 4 | 7 5 3 |
| 4 7 8 | 6 5 3 | 2 9 1 |
+-------+-------+-------+
| 3 6 4 | 8 1 9 | 5 7 2 |
| 7 8 2 | 3 4 5 | 9 1 6 |
| 1 5 9 | 2 6 7 | 4 3 8 |
+-------+-------+-------+
| 8 9 3 | 7 2 6 | 1 4 5 |
| 5 2 7 | 4 3 1 | 6 8 9 |
| 6 4 1 | 5 9 8 | 3 2 7 |
+-------+-------+-------+
total 36.205000 0.172000 36.377000 ( 38.749000)
average 0.658273 0.003127 0.661400 ( 0.704527)
So it seems like your version is even faster than this, i would
like to see it.
here is mine (i'm especialy delighted on what can be done in 90
lines of code):
-------------------------------------------------------------------
require 'Set'
require 'Benchmark'
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)}}
# this contains the 3 'neighbourhoods' (row/col/box)
# of each of the 81 cells
NEIGHBOURHOODS = Array.new(81) {|o|
[row[o / 9], col[o % 9], box[(o / 27) * 3 + (o % 9) / 3]]}
COMBINEDNEIGHBOURS = Array.new(81) {|o|
NEIGHBOURHOODS[o].flatten.uniq! - [o]}
class Board
attr_reader :cells, :possibilities
#initializes the cells and possibilities
def initialize c
@possibilities = Array.new(81) {(1..9).to_set}
@cells = Array.new(81, nil)
81.times{|i|set_cell(i, c[i]) if c[i]}
end
def initialize_copy(b)
@cells, p = b.cells.clone, b.possibilities
@possibilities = Array.new(81) {|i|Set.new(p[i])}
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] || "_"
end.join(" ")
end.join(" | ")
end.join(" |\n| ")
end.join(" |\n+-------+-------+-------+\n| ") +
" |\n+-------+-------+-------+\n"
end
#recursively sets cell 'c' to 'v' and all trivial dependend cells
def set_cell c, v
cells[c], possibilities[c] = v, Set[v]
COMBINEDNEIGHBOURS[c].each{|i|possibilities[i].delete(v)}
COMBINEDNEIGHBOURS[c].each{|i|
set_cell(i, possibilities[i].min) if !cells[i] &&
possibilities[i].size == 1}
return self
end
#solves with logic and brute force if neccessary',
#returns nil if unsolvable
def solve!
c = i = changed = 0
while i = ((i+1)..(changed+81)).find{|x|!cells[x % 81]}
NEIGHBOURHOODS[c = i % 81].each do |neighbours|
pn = neighbours.inject(possibilities[c].clone){|r, j|
(j != c) ? r.subtract(possibilities[j]) : r}
set_cell(changed = i = c, pn.min) && break if pn.size == 1
end
end
return self if cells.all?
return nil if possibilities.any?{|p| p.empty?}
p, i = possibilities.zip((0..80).to_a).select{|a, b|a.size > 1}.
min{|a, b|a[0].size <=> b[0].size}
p.each{|j| b=clone.set_cell(i, j).solve! and return b}
return nil
end
end
# main
count, $stdout.sync, total = 0, true, Benchmark::Tms.new
Benchmark.bm(15, "total", "average") do |bm|
loop do
cells = []
while !ARGF.eof? && (cells.size < 81) do
ARGF.gets.scan(/[0-9_.]/).each{|c| cells << c.to_i.nonzero?}
end
break if ARGF.eof?
board = nil
total += bm.report("solving nr #{count+=1}") do
board = Board.new(cells).solve!
end
puts board ? board.to_s : "UNSOLVEABLE!" + "\n\n"
end
[total, total / count]
end
------------------------------------------------------------------
Kroeger Simon (ext)
> -----Original Message-----
> From: David Tran [mailto:email...@gmail.com]
> Sent: Tuesday, August 23, 2005 3:49 PM
> To: ruby-talk ML
> Subject: Re: [QUIZ] Sodoku Solver (#43)
>
> > Adam Shelly wrote:
> > ...
> > And it took a while to figure out that this one was unsolvable:
> > +-------+-------+-------+
> > | _ 2 _ | _ _ _ | _ _ _ |
> > | _ _ _ | 6 _ _ | _ _ 3 |
> > | _ 7 4 | _ 8 _ | _ _ _ |
> > +-------+-------+-------+
> > | _ _ _ | _ _ 3 | _ _ 2 |
> > | _ 8 _ | _ 4 _ | _ 1 _ |
> > | 6 _ _ | 5 _ _ | _ _ _ |
> > +-------+-------+-------+
> > | _ _ _ | _ 1 _ | 7 8 _ |
> > | 5 _ _ | _ _ 9 | _ _ _ |
> > | _ _ _ | _ _ _ | _ 4 _ |
> > +-------+-------+-------+
>
> Euh ... mmm....
> my program tell me that is one has unique solution ( on
> 16.672 seconds )
> +-------+-------+-------+
> | 1 2 6 | 4 3 7 | 9 5 8 |
> | 8 9 5 | 6 2 1 | 4 7 3 |
> | 3 7 4 | 9 8 5 | 1 2 6 |
> +-------+-------+-------+
> | 4 5 7 | 1 9 3 | 8 6 2 |
> | 9 8 3 | 2 4 6 | 5 1 7 |
> | 6 1 2 | 5 7 8 | 3 9 4 |
> +-------+-------+-------+
> | 2 6 9 | 3 1 4 | 7 8 5 |
> | 5 4 8 | 7 6 9 | 2 3 1 |
> | 7 3 1 | 8 5 2 | 6 4 9 |
> +-------+-------+-------+
Ok, I figured it out also...
solving nr 1 2.015000 0.000000 2.015000 ( 2.016000)
+-------+-------+-------+
| 1 2 6 | 4 3 7 | 9 5 8 |
| 8 9 5 | 6 2 1 | 4 7 3 |
| 3 7 4 | 9 8 5 | 1 2 6 |
+-------+-------+-------+
| 4 5 7 | 1 9 3 | 8 6 2 |
| 9 8 3 | 2 4 6 | 5 1 7 |
| 6 1 2 | 5 7 8 | 3 9 4 |
+-------+-------+-------+
| 2 6 9 | 3 1 4 | 7 8 5 |
| 5 4 8 | 7 6 9 | 2 3 1 |
| 7 3 1 | 8 5 2 | 6 4 9 |
+-------+-------+-------+
but the other (wrong) version was so damn fast :)
cheers
Simon
p.s.: I vote for a new Quiz:
find false answers to sodukus realy quick :)
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
> i have another version for you:
>
> def parse_board(file)
> @@boxcols= (s = file.read).scan(/[+-]+/).size() -1
> boardlist = s.scan(/[0-9A-Za-z_]/).map{|c| c.hex}
> return boardlist, Math.sqrt(boardlist.size).to_i
> end
>
> assuming that boxcols is the number of boxes in horizontal or
> vertical direction, boardlist is one array (e.g. with 81 cells
> for a 9x9 board) and the second return parameter is the number
> of columns or rows. right?
>
boxcols counted the +'s in the horizontal direction (columns), yours
counts vertical (rows).
The difference is important in solving
+-----+-----+-----+-----+
| 1 _ | _ _ | _ _ | _ _ |
| _ 2 | 1 _ | _ _ | _ _ |
| _ _ | 3 _ | _ _ | _ _ |
| _ _ | _ 4 | _ _ | _ _ |
+-----+-----+-----+-----+
| _ _ | _ _ | 5 _ | _ _ |
| _ _ | _ _ | _ 6 | _ _ |
| _ _ | _ _ | _ _ | _ 8 |
+-----+-----+-----+-----+
vs
+---------+---------+
| 1 _ _ _ | _ _ _ _ |
| _ 2 _ _ | _ _ _ _ |
| _ 1 3 _ | _ _ _ _ |
| _ _ _ 4 | _ _ _ _ |
+---------+---------+
| _ _ _ _ | 5 _ _ _ |
| _ _ _ _ | _ 6 _ _ |
| _ _ _ _ | _ _ 7 _ |
| _ _ _ _ | _ _ _ 8 |
+---------+---------+
My code handles both puzzles. And it's an easy fix to make it work
with your 'boxrows' instead.
Thanks for the tips.
-Adam
Jim Weirich
> So here's one thing I couldn't figure out last night, maybe someone can
> help 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.
You could try something like this:
def search_for_solution
solve
rescue UnsolvableBoard
# Handle Unsolvable Boards ...
end
def solve
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
end
--
-- Jim Weirich j...@weirichhouse.org http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)
David Brady
>Ahem... Mine used array subtraction too. Sorry.
>
>
Doh! I apologize for the oversight.
Well, at least I'm not the only stone-axe ninja here. :-)
I am doing these quizzes as much to learn Ruby as anything else... I
especially like your use of rdoc. I need to pick that up next.
David Brady
>To me, that removes a lot of the wordiness of the original code, without
>sacrificing clarity or functionality. It's probably a touch more efficient too,
>since we trimmed quite a few operations.
>
>
Ahhh... but:
Loaded suite test_sodoku
Started
F.F..FFFFFF.F..FF.F
Finished in 9.439033 seconds.
[verbose results snipped]
19 tests, 27 assertions, 12 failures, 0 errors
My code may be wordier, but it's also workier. :-)
Actually the only thing wrong with your code is that you pulled a Knuth:
"Beware of bugs in the above code; I have merely proved it correct, not
tried it." Your load function calls "Integet" instead of "Integer".
Because of the rescue 0, the script never lets you know that anything's
wrong. Also, using an exception to handle normal behavior seems smelly
to me, but that's a style question.
I tried tightening the rescue to only rescue the expected ArgumentError,
and ended up with this mess:
@board << line.scan(/[\d_]/).collect {|n| begin; Integer(n); rescue
ArgumentError; 0; end }
This works, and "Integet" correctly pukes out a NoMethodError, but it
seems like a lot of work to clean up a syntax error that was getting
caught (indirectly) by the unit tests anyway. So I decided to clean it
up by eliminating the smell coming from the rescue in the first place.
I liked this code a lot better, as it was more "up front" about the
'_'->'0' conversion:
# convert '_' to '0' and turn digit chars into integers.
@board << line.tr!('_','0').scan(/[\d_]/).collect {|n| Integer(n) }
A major part of this exercise for me was learning to work with
test/unit. I actually had a few bugs caused by my ignorance of how Ruby
works get caught by my unit tests. Specifically, Sodoku#copy_board got
written after I spent an hour trying to figure out why @board =
other.board.dup was STILL returning aliased arrays. (Answer: @board
*was* getting dup'ed. But @board[0] is ALSO an array, which was
aliased. copy_board fixes this with a 2-level dup.)
Having unit tests allowed me to verify your refactoring, as well as
probe my own solutions fearlessly in a language I am still coming to
grips with.
Nifty.
-dB
--
David Brady
ruby...@shinybit.com
I'm having a really surreal day... OR AM I?
Josef 'Jupp' SCHUGT
At Tue, 23 Aug 2005 11:11:46 +0900,Adam Shelly wrote:
> aargh. What happened to my tabs?
Vanished. Well-known problem in ASCII-artist communities.
Follows best current practice to prepare a Ruby program before
including it in the text of an e-mail. Valid for all e-mail programs
running in Emacsen:
1. mark whole program
2. issue 'M-x untabify'
3. mark whole program again
4. issue 'M-x comment-region'
This leaves the program readable while at the same time keeping the
whitespace intact.
Using 'M-x comment-region' makes sure that the whitespace is no
leading one. Some MUAs are known to remove *any* leading whitespace -
not just spaces!
For making the program runnable again 'M-x uncomment-region' is
suficient.
irb(main):001:0> algorithm.port(user.mua) == exercise(message.reader)
true
(^_^)
Josef 'Jupp' SCHUGT
--
Receiving this message does not necessarily imply that you are
expected to understand it. If you do not understand it the best
current practice (BCP) is ignoring it. If you only understand parts
of it the BCP is ignoring the rest.
James Edward Gray II
> Is it ok to reply to your summary?
Always. Definitely. The number one goal of Ruby Quiz has always
been to foster learning. Feel free to jump in there and support that
at any time!
> I don't wan't to to be rude in any way, but i thought Davids
> reasoning on Array operators:
>
> "Using a set probably would have been better, but I didn't know
> about Ruby sets until after I finished my code. So my solution is
> a very elegant way of wielding a stone axe."
>
> should have found it's way into the summary, especially as all the
> samples given are wielding the same ancient weapon.
>
> or to put it with your own words:
>
> "Then you'll want to look at the standard "set" library.
> That will make your whole weekend."
>
> Just a thought of mine, it seemed to be one of the gotchas in this
> quiz. Keep up the very good work!
Very good point. Thanks for bringing it up.
James Edward Gray II
Ruby Quiz
I wasn't aware of all the name variations when I wrote this quiz. It looks like
the actual number puzzle is usually called Sudoko, now that I've looked into it.
However, some seem to consider Sodoku a slightly different form of the game
which can have multiple solutions, while "true" Sudoku should have exactly one.
This fact complicated solutions a little, so I thought it was worth bringing up
before we dig into them.
The solutions to this quiz are quite varied and interesting. We have raw speed,
clever algorithms, java ports, and even not-quite-correct approaches. I learned
a lot digging trough the code and I encourage others to do the same.
I would say the overriding theme this time though was the sheer amount of code
that came in. Most of the solutions were over two hundred lines, a few even
over three hundred. This probably tells us that the problem was tricky, but I
also found some plenty wordy expressions in there. Let's look at some of those,
since I believe that rethinking code can be very instructive. Here's a method
from the first submission of David Brady's solution:
# Loads the @board array from a string matching the example above.
def load(str)
line_num = 0
str.each_line do |line|
line.gsub! '+', ''
line.gsub! '-', ''
line.gsub! '|', ''
line.gsub! ' ', ' '
line.gsub! '_', '0'
line.strip!
if line.length > 0
l = line.split
fail "Line length was #{l.length}" unless l.length == 9
@board[line_num] = l.collect {|x| x.to_i}
line_num += 1
end
end
fail "Board is not valid." unless self.valid?
end
This code parses the puzzle input format and uses it to load the initial @board,
which is just and Array (rows) of Arrays (columns). It's currently doing this
by cleaning up the lines and reading each integer. Can we smooth that out a
little?
Often with Ruby, having to use an index is a sign that you're not attacking the
problem in the easiest way. Each index is being used to completely replace a
line, so let's see if we can just append them directly:
# Loads the @board array from a string matching the example above.
def load(str)
@board = Array.new
str.each_line do |line|
line.gsub! '+', ''
line.gsub! '-', ''
line.gsub! '|', ''
line.gsub! ' ', ' '
line.gsub! '_', '0'
line.strip!
if line.length > 0
l = line.split
fail "Line length was #{l.length}" unless l.length == 9
@board << l.collect {|x| x.to_i}
end
end
fail "Board is not valid." unless self.valid?
end
That only saved one line I guess, but conceptually it's getting easier for me to
follow already. That's always a win, I think.
Let's tackle the text processing. My first instinct was:
# Loads the @board array from a string matching the example above.
def load(str)
@board = Array.new
str.each_line do |line|
line.delete! '|+-'
line.tr! '_', '0'
line.squeeze!
line.strip!
if line.length > 0
l = line.split
fail "Line length was #{l.length}" unless l.length == 9
@board << l.collect {|x| x.to_i}
end
end
fail "Board is not valid." unless self.valid?
end
Again, only two lines trimmed, but I'm actually helping myself to understand
what exactly this code is doing and that's far more important to me.
I now see that we're stripping non-digit or underscore characters. We're
leaving the spaces however, so we can later split() on whitespace to get each
cell. That gets me thinking: We don't have to split() on whitespace. If I can
get it down to just what I'm after, we can split() on characters:
# Loads the @board array from a string matching the example above.
def load(str)
@board = Array.new
str.each_line do |line|
line.delete! '^0-9_'
if line.length > 0
l = line.split('')
fail "Line length was #{l.length}" unless l.length == 9
@board << l.collect {|n| Integet(n) rescue 0 }
end
end
fail "Board is not valid." unless self.valid?
end
Note that I did change the collect() to be more obvious, since I removed
translation of '_' to '0'. This isn't strictly needed, as String.to_i() will
return 0 if it can't form a number, but I'm trying not to damage the readability
of this code with my changes.
We're getting close, I can tell, but there's another trick or two left. We have
to check the line length to see if it's one of the lines that contains cells or
just a border row. If we skip border rows altogether, we could the switch our
focus from deleting the unwanted data to grabbing wanted data. (Gavin Kistner
originally pointed this out on Ruby Talk.) Let's see what that does for us:
# Loads the @board array from a string matching the example above.
def load(str)
@board = Array.new
str.each_line do |line|
next unless line =~ /\d|_/
@board << line.scan(/[\d_]/).collect {|n| Integet(n) rescue 0 }
fail "Length was #{@board.last.length}" unless @board.last.length == 9
end
fail "Board is not valid." unless self.valid?
end
Moving the line verification to after I load @board also allowed me to do away
with the extra variable, as you can see.
To me, that removes a lot of the wordiness of the original code, without
sacrificing clarity or functionality. It's probably a touch more efficient too,
since we trimmed quite a few operations.
I believe Adam Shelly's parse routine could benefit from similar simplifications
if you want to try your own hand at a little refactoring.
Here's another chunk of code (from Horndude77's solution) just crying out for
some help:
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
I told myself that was too easy and had the following knee-jerk reaction:
def solve
changed = true
while(changed && @unknown.length>0)
changed = eliminateall || checkallrows || eliminateall ||
checkallcols || eliminateall || checkallboxes
end
puts self
if(@unknown.length>0)
puts "I can't solve this one"
end
end
That's cute, and may even work if the underlying algorithms aren't sensitive to
the call order, but it is not identical in function to the original code. The
original method calls all of those methods and just tracks to see if any one of
them returned true. The second version will short-circuit the call chain as
soon as a method returns true. We'll have to be a bit more clever to avoid
that:
def solve
changed = true
while(changed && @unknown.length>0)
changed = %w{ eliminateall checkallrows eliminateall
checkallcols eliminateall checkallboxes }.map do |m|
send(m)
end.include?(true)
end
puts self
if(@unknown.length>0)
puts "I can't solve this one"
end
end
That should be equivalent to the original, I believe, minus some repetition.
My point in showing the above examples wasn't to pick on anyone and I apologize
if I gave any offense. I just wanted to explore a little idiomatic Ruby through
some examples.
Back to Sudoku itself. Let's look at a solution. Here's the beginning of
Dominik Bathon's solver class:
class SudokuSolver
# sudoku is an array of arrays, containing the rows, which contain the
# cells (all non valid entries are interpreted as open)
def initialize(sudoku)
# determine @n / @sqrt_n
@n = sudoku.size
@sqrt_n = Math.sqrt(@n).to_i
raise "wrong sudoku size" unless @sqrt_n * @sqrt_n == @n
# populate internal representation
@arr = sudoku.collect { |row|
# ensure correct width for all rows
(0...@n).collect { |i|
# fixed cell or all values possible for open cell
((1..@n) === row[i]) ? [row[i]] : (1..@n).to_a
}
}
# initialize fix arrays
# they will contain all fixed cells for all rows, cols and boxes
@rfix=Array.new(@n) { [] }
@cfix=Array.new(@n) { [] }
@bfix=Array.new(@n) { [] }
@n.times { |r| @n.times { |c| update_fix(r, c) } }
# check for non-unique numbers
[@rfix, @cfix, @bfix].each { |fix| fix.each { |x|
unless x.size == x.uniq.size
raise "non-unique numbers in row, col or box"
end
} }
end
# ...
This constructor takes an Array of Arrays, which is simply the board setup read
from the input file. After finding the board size, you can see the method
builds its internal Array (rows) of Arrays (columns) of Arrays (possible numbers
for that cell). Known cells are set to a one element member with the known
value, while other cells are set to an Array of all the possible numbers.
Next, we see that the code also builds representations for rows, columns, and
boxes and repeatedly calls update_fix(), we assume to populate them.
The method ends with a puzzle validation check, ensuring that there are no
duplicate numbers in rows, columns or boxes.
Jumping a little out of order now, let's examine the private methods used by the
constructor:
# ...
private
# returns the box index of row r and col c
def rc2box(r, c)
(r - (r % @sqrt_n)) + (c / @sqrt_n)
end
# if row r, col c contains a fixed cell, it is added to the fixed arrays
def update_fix(r, c)
if @arr[r][c].size == 1
@rfix[r] << @arr[r][c][0]
@cfix[c] << @arr[r][c][0]
@bfix[rc2box(r, c)] << @arr[r][c][0]
end
end
# ...
From here we can see that the rows, columns, and boxes tracking variables only
receive a number that has been narrowed down to a single possibility. Because
of that simplification, these are just two dimensional Arrays. Note that each
new-found number is just appended to the Array. These will not be in the same
order as they really appear in the puzzle, but since they're just used to verify
uniqueness it doesn't matter.
The first method, rc2box() just uses math to locate which box we're in, given a
row and column.
Back to the public methods:
# ...
public
# returns the internal representation as array of arrays
def to_a
@arr.collect { |row| row.collect { |x|
(x.size == 1) ? x[0] : nil
} }
end
# returns a simple string representation
def to_s
fw = @n.to_s.size
to_a.collect { |row| row.collect { |x|
(x ? x.to_s : "_").rjust(fw)
}.join " " }.join "\n"
end
# returns whether the puzzle is solved
def finished?
@arr.each { |row| row.each { |x| return false if x.size > 1 } }
true
end
# ...
The above methods allow you to query the solver for an Array representation, a
String representation, or just to find out if it is finished being solved yet.
Starting with to_a(), you can see that it basically just flattens the third
dimension of Arrays either into a known number choice, or nil for unknowns. The
next method, to_s(), calls to_a(), stringifies, and join()s the results.
On to the actual solving code:
# ...
# for each cell remove the possibilities, that are already used in the
# cell's row, col or box
# return if successful
def reduce
success = false
@n.times { |r| @n.times { |c|
if (sz = @arr[r][c].size) > 1
@arr[r][c] = @arr[r][c] -
(@rfix[r] | @cfix[c] | @bfix[rc2box(r, c)])
raise "impossible to solve" if @arr[r][c].empty?
# have we been successful
if @arr[r][c].size < sz
success = true
update_fix(r, c)
end
end
} }
success
end
# ...
This method is a simple, but important, piece of the solving task. It simply
walks cell by cell reducing the possibilities by what we already know. It uses
the Array union operator (|) to combine all known numbers for the row, column
and box of this cell. All of those numbers are then removed from the
possibilities using the Array difference operator (-). When any cell shrinks in
choices, update_fix() is called again to notify row, column, and box of the
change. As long as a single cell lost a single possibility this method returns
true to report progress.
Here's another solving method:
# ...
# find open cells with unique elements in their row, col or box
# return if successful
# reduce must return false when this method is called (if the
# possibilities aren't reduced, bad things may happen...)
def deduce
success = false
[:col_each, :row_each, :box_each].each { |meth|
@n.times { |i|
u = uniqs_in(meth, i)
unless u.empty?
send(meth, i) { |x|
if x.size > 1 && ((u2 = u & x).size == 1)
success = true
u2
else
nil
end
}
# change only one row/col/box at a time
return success if success
end
}
}
success
end
# ...
Another way to be sure of a cell is to find a unique possibility in the row,
column, or box. In other words, if two is a possibility in the fifth cell of a
row, but not a possibility in any other cell of the row, we know it belongs in
the fifth cell and we can place it.
This code hunts for that using iterators to get all the cells in a row, column,
or box and the helper method uniqs_in(), which performs the search I just
explained. When a unique option is found, the code places it and returns true
to indicate progress.
Here are all four private helper methods:
# ...
private
# yields each cell of row r and assigns the result of the yield unless
# it is nil
def row_each(r)
@n.times { |c|
if (res = yield(@arr[r][c]))
@arr[r][c] = res
update_fix(r, c)
end
}
end
# yields each cell of col c and assigns the result of the yield unless
# it is nil
def col_each(c)
@n.times { |r|
if (res = yield(@arr[r][c]))
@arr[r][c] = res
update_fix(r, c)
end
}
end
# yields each cell of box b and assigns the result of the yield unless
# it is nil
def box_each(b)
off_r, off_c = (b - (b % @sqrt_n)), (b % @sqrt_n) * @sqrt_n
@n.times { |i|
r, c = off_r + (i / @sqrt_n), off_c + (i % @sqrt_n)
if (res = yield(@arr[r][c]))
@arr[r][c] = res
update_fix(r, c)
end
}
end
# find unique numbers in possibility lists of a row, col or box
# each_meth must be :row_each, :col_each or :box_each
def uniqs_in(each_meth, index)
h = Hash.new(0)
send(each_meth, index) { |x|
x.each { |n| h[n] += 1 } if x.size > 1
nil # we didn't change anything
}
h.select { |k, v| v == 1 }.collect { |k, v| k }
end
# ...
The iterators are pretty obvious. The only gotcha to their use is that the
block is expected to return true or false, indicating if the cell was updated.
This allows the iterator to call update_fix() and keep the internal
representations in sync.
The uniqs_in() method just uses those iterators to fill a Hash with seen counts
and then returns all keys that were only seen once.
Finally, we start to see it all come together with the next method:
# ...
public
# tries to solve the sudoku with reduce and deduce
# returns one of :impossible, :solved, :unknown
def solve
begin
until finished?
progress = false
while reduce
progress = true
end
progress = true if deduce
return :unknown unless progress
end
:solved
rescue
:impossible
end
end
# ...
This method just combines calls to to the previously seen reduce() and deduce()
to see if it can use process of elimination to solve the problem. It loops as
long as either method reports some progress. It will eventually return :solved,
if finished?() declares the puzzle done, or :unknown if it runs out of
reductions and deductions. :impossible is returned in the event of a problem.
The above can solve some puzzles quickly and efficiently, but it's not a
complete solution. When it won't go any father, it's time for some guess work:
# ...
# solves the sudoku using solve and if that fails, it tries to guess
# returns one of :impossible, :solved, :multiple_solutions
def backtrack_solve
if (res = solve) == :unknown
# find first open cell
r, c = 0, 0
@rfix.each_with_index { |rf, r|
break if rf.size < @n
}
@arr[r].each_with_index { |x, c|
break if x.size > 1
}
partial = to_a
solutions = []
# try all possibilities for the open cell
@arr[r][c].each { |guess|
partial[r][c] = guess
rsolver = SudokuSolver.new(partial)
case rsolver.backtrack_solve
when :multiple_solutions
initialize(rsolver.to_a)
return :multiple_solutions
when :solved
solutions << rsolver
end
}
if solutions.empty?
return :impossible
else
initialize(solutions[0].to_a)
return solutions.size > 1 ? :multiple_solutions : :solved
end
end
res
end
end
# ...
Note that this method begins by calling solve(). If it yields a complete
solution, the rest of the work can be skipped. Even if it doesn't though, it
should have reduced the possibilities, making the coming job easier.
The next bit of code locates a cell to start guessing with. Rows are scanned to
find one that hasn't been completely filled in, then columns are scanned to find
a cell with more than one possibility. Note how those two iterations
purposefully clobber the local variables (r and c), so they will hold the final
address of the cell when scanning is done.
Finally, we're to the guess work. An Array is prepared to hold solutions and
the current known cells are retrieved with a call to to_a(). Then, each
possibility for the selected cell is inserted and a new solver is built and run.
This amounts to recursion of the entire process. The results of these guesses
are examined by a case statement and added to the solutions Array when found.
The case statement ignores :impossible returns, since these are just wrong
guesses.
Finally the method checks to see if any solutions were found, and returns the
proper Symbol for the results.
The last little chunk of code handles input and output for the solution:
# ...
if $0 == __FILE__
# read a sudoku from stdin
sudoku = []
while sudoku.size < 9
row = gets.scan(/\d|_/).map { |s| s.to_i }
sudoku << row if row.size == 9
end
# solve
begin
solver = SudokuSolver.new(sudoku)
puts "Input:", solver
case solver.backtrack_solve
when :solved
puts "Solution:"
when :multiple_solutions
puts "There are multiple solutions!", "One solution:"
else
puts "Impossible:"
end
puts solver
rescue => e
puts "Error: #{e.message}"
end
end
Look at that four line input read up there. Its similar to what we reduced the
other code to at the beginning of this summary. The output is very straight
forward. It just makes good use of to_s() in the solver object to print the
board before and after.
My thanks to all who sent in their solutions, sometimes many, many times. ;)
Next week's Ruby Quiz is shamelessly stolen from another source of Ruby
challenges. Stay tuned to see the kind of problems Dave Thomas cooks up...
James Edward Gray II
> On 8/25/05, Ruby Quiz <ja...@grayproductions.net> wrote:
>
>> I believe Adam Shelly's parse routine could benefit from similar
>> simplifications
>> if you want to try your own hand at a little refactoring.
>>
>
> Ok, I admit I'm a ruby newbie. But I'm trying to learn the Ruby Way.
> How's this?
<laughs> No worries there!
[snip old code]
> def ParseBoard(file)
> boardlist,size = [ ],0
> file.each do |line|
> if line.delete!('^0-9A-Za-z_+') =~ /\++/
Beware the bang methods (ending in !) in Ruby. Obviously it's fine
to use them, but it's almost never a good idea to chain them. Most
of them return nil when they don't make a change and nil doesn't
support very many calls, like the =~ operator you use here. Feed it
the wrong line and the code will crash.
In this case, you should be able to just drop the !, as delete()
returns a copy of the String when nothing changes.
> @@boxcols= line.length-1
> else
> boardlist += line.split(//).collect{|n| n.hex }
> size = line.length
> end
> p line
> end
> boardlist,size
> end
It's definitely looking more Rubyish, I would say. Have a look at
how the other solutions parsed the input, if you want to compare.
James Edward Gray II
Simon Kröger
I don't wan't to to be rude in any way, but i thought Davids
reasoning on Array operators:
"Using a set probably would have been better, but I didn't know about
Ruby sets until after I finished my code. So my solution is a very
elegant way of wielding a stone axe."
should have found it's way into the summary, especially as all the
samples given are wielding the same ancient weapon.
or to put it with your own words:
"Then you'll want to look at the standard "set" library.
That will make your whole weekend."
Just a thought of mine, it seemed to be one of the gotchas in this
quiz. Keep up the very good work!
cheers
Simon
David Tran
> ...
Adam Shelly
> Adam Shelly wrote:
>
> > Should I post my third version, or is everyone sick of looking at my
> > code by now?
Ok, here's my latest. My big speedup was figuring out that if I make
a bad guess, I just eliminate that possibility and re-solve. See the
startGuessing method..
It now solves #30 in 0.194s, and #55 in 0.124 ( I'm not sure which
puzzle you called #1)
> here is mine (i'm especialy delighted on what can be done in 90
> lines of code):
Mine definitely feels wordy to me at 370 lines:
#!/usr/bin/env ruby
# SodukuSolver.rb
# author: Adam Shelly
# Solves soduku puzzles.
# supports arbitrary grid sizes (tested upto 16x16)
def dprint(s)
print s if $DEBUG
end
class BadGuessException < Exception
end
#Utility function to define the box dimensions inside a grid
@@boxcols = 0
def GetBoxBounds(gridsize)
if (@@boxcols > 0)
[gridsize/@@boxcols, @@boxcols]
else
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 [2,5]
when 12 then [3,4]
when 14 then [2,7]
when 15 then [3,5]
when 16 then [4,4]
else
print "GridSize of #{gridsize} unsupported. Exiting\n"
[0,0]
end
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
attr_reader :row, :col, :box, :possible
def initialize(row, col, val=-1, max = 9)
@row = row
@col = col
bounds = GetBoxBounds(max)
@box = col/(bounds[0])+((row/bounds[1])*bounds[1])
@processed = false
if (val.is_a?(Array))
@possible = val.dup
#if you don't dup here, you get big trouble
# when undoing guesses
elsif ((1..max) === val)
@possible = [val]
else
@possible = (1..max).to_a
end
end
def includes?(n)
@possible.include?(n)
end
def mark
@processed = true
end
def set(toValue)
@possible = [toValue] if found = @possible.include?(toValue)
found
end
def hasFinalValue
return @possible[0] if (@possible.length == 1)
end
def eliminate(n)
raise BadGuessException if (@possible.length == 0)
@possible.delete(n)
hasFinalValue && !@processed
end
def override(a)
@possible = a.dup
@processed = false
end
def to_s
if $DEBUG
s = @possible.to_s;
s.length.upto(9) do s << " " end
"["+s+"]"
else
(v = hasFinalValue)?" "+v.to_s(32):" _"
end
end
def >(other)
return (@row > other.row || (@row == other.row && @col > other.col))
end
end
class Guess
def initialize(cell )
@row,@col = cell.row,cell.col
@store = cell.possible.clone
@index = 0
end
def value
@store[@index]
end
def remove(cellset)
cell=cellset[@row][@col]
cell.eliminate(value)
cell
end
def to_s
"Guess [#{@row},#{@col}] to be #{@store[@index]} from [#{@store}] "
end
end
class Solver
def initialize(boardlist, size, presolved = false, lev=0)
@level = lev+1
@size = size
become(boardlist, presolved)
end
#helper for init and cloning
def become(boardlist, presolved = true)
@boxes =[]
@rows =[]
@cols = []
@queue = [] #a list of cells to check for solutions.
@size.times{ |n| @boxes[n] = [] ; @rows[n]=[]; @cols[n]=[] }
r=c=0
boardlist.each do |v|
cell = Cell.new(r,c,v, @size)
@boxes[cell.box] <<@rows[r][c] = @cols[c][r] = cell
@queue << cell
cell.mark if (presolved && cell.hasFinalValue)
c+=1
if (c==@size) then c=0; r=r+=1 end
end
end
def unsolved
@size.times do |n|
@boxes[n].each {|c| return c if !c.hasFinalValue}
end
nil
end
def solve
while @queue.size > 0
while (cell = @queue.pop)
eliminateChoices(cell)
end
checkForKnownValues()
end
dprint "Solved to...\n#{self}"
return unsolved ? startGuessing : true
end
#for any resolved cell, eliminate its value from the possible values
#of the other cells in the set
def eliminateChoices(cell)
if (value = cell.hasFinalValue)
cell.mark
[@boxes[cell.box],@rows[cell.row],@cols[cell.col]].each do |set|
eliminateChoiceFromSet(set, cell, value)
end
end
end
def eliminateChoiceFromSet(g, exceptCell, n)
g.each {|cell| eliminateValueFromCell(n,cell) if cell != exceptCell }
end
def eliminateValueFromCell(value, cell)
@queue << cell if cell.eliminate(value) && !@queue.include?(cell)
end
def checkForKnownValues()
@size.times do |n|
[@rows[n],@cols[n],@boxes[n]].each do |set|
findPairs(set)
findUniqueChoices(set)
end
end
end
def findUniqueChoices(set)
1.upto(@size) do |n| #check for every possible value
lastCell = nil
set.each do |c| #in every cell in the set
if (c.includes?(n))
if (c.hasFinalValue || lastCell)
#found a 2nd instance, no good
lastCell = nil
break
end
lastCell = c;
end
end
#if true, there is only one cell in the set with that value,
#so let it be the answer
if (lastCell && !lastCell.hasFinalValue)
lastCell.set(n)
@queue << lastCell
end
end
end
#find any pair of cells in a set with the same 2 possibilities
# - these two can be removed from any other cell in the same set
def findPairs(set)
0.upto(@size-1) do |n|
(n+1).upto(@size-1) do |m|
if (set[n].possible.size == 2 && set[n].possible ==
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)
@size.times do |n|
if (!skipList.include?(n))
values.each {|v| eliminateValueFromCell(v, set[n])}
end
end
end
def startGuessing
print "Only Solveable by Guessing\n" if @level == 1
while (c = unsolved)
myclone = Solver.new(boardlist,@size, true,@level)
myguess = myclone.guess
return false if !myguess
dprint myclone
begin
if (myclone.solve)
become(myclone.boardlist)
return true
else
return false
end
rescue BadGuessException
#this is the big speedup - remove the bad guess
#from the possibilities, and re-solve
@queue << myguess.remove(@rows)
dprint "#{@level} Bad Guess\n #{self}"
return solve
end
end
end
def guess
2.upto(@size) do |mincount|
@rows.each do |row|
row.each do |cell|
if cell.possible.size == mincount
g = Guess.new(cell)
cell.set(g.value)
@queue << cell
return g
end
end
end
end
dprint "did not find a guess\n"
return nil
end
#formating (vertical line every cbreak)
def showBorder(cbreak)
s = "+"
1.upto(@size) do |n|
s << "--"
s<< "-+" if ((n)%cbreak == 0)
end
s <<"\n"
end
def to_s
r=c=0
cbreak,rbreak = GetBoxBounds(@size)
s = showBorder(cbreak)
@rows.each do |row|
#r+=1
s << "|"
row.each do |cell|
c+=1
s << cell.to_s
if (c==cbreak) then s << " |";c=0; end
end
s<<"\n"
if (r+=1)==rbreak then s << showBorder(cbreak); r=0; end
end
s<<"\n"
s
end
def boardlist
a = []
@rows.each do |row|
row.each do |cell|
v = cell.hasFinalValue
a<< ( v ? v : cell.possible )
end
end
a
end
end
#parses text file containing board. The only significant characters
are _, 0-9, A-Z.
# if bounded by +---+---+---+, uses the + char to determine the layout
of the boxes
#there must be an equal number of significant chars in each line, and
the same number of rows.
def ParseBoard(file)
row = 0
col = 0
boxes = 0
boardlist = [ ]
file.each do |line|
line.chomp.each_byte do |c|
case c
when ?0..?9
boardlist << c.to_i - ?0
col+=1
when ?A..?Z
boardlist << c.to_i - ?A + 10
col+=1
when ?a..?z
boardlist << c.to_i - ?a + 10
col+=1
when ?_
boardlist << -1
col+=1
when ?+
boxes+=1 if row == 0
end
end
if (col > 0) then
row+=1
break if (row == col)
end
col=0
end
@@boxcols = boxes-1
return boardlist,row
end
if __FILE__ == $0
boardlist, size = ParseBoard(ARGF)
sol = Solver.new(boardlist, size)
print sol
begin
print "UNSOLVABLE\n" if (!sol.solve())
rescue BadGuessException
print "Malformed Puzzle\n"
end
print sol
end
--Adam
Dominik Bathon
wrote:
> And it took a while to figure out that this one was unsolvable:
> +-------+-------+-------+
> | _ 2 _ | _ _ _ | _ _ _ |
> | _ _ _ | 6 _ _ | _ _ 3 |
> | _ 7 4 | _ 8 _ | _ _ _ |
> +-------+-------+-------+
> | _ _ _ | _ _ 3 | _ _ 2 |
> | _ 8 _ | _ 4 _ | _ 1 _ |
> | 6 _ _ | 5 _ _ | _ _ _ |
> +-------+-------+-------+
> | _ _ _ | _ 1 _ | 7 8 _ |
> | 5 _ _ | _ _ 9 | _ _ _ |
> | _ _ _ | _ _ _ | _ 4 _ |
> +-------+-------+-------+
>
> UNSOLVABLE
But it is solvable:
Input:
_ 2 _ _ _ _ _ _ _
_ _ _ 6 _ _ _ _ 3
_ 7 4 _ 8 _ _ _ _
_ _ _ _ _ 3 _ _ 2
_ 8 _ _ 4 _ _ 1 _
6 _ _ 5 _ _ _ _ _
_ _ _ _ 1 _ 7 8 _
5 _ _ _ _ 9 _ _ _
_ _ _ _ _ _ _ 4 _
Solution:
1 2 6 4 3 7 9 5 8
8 9 5 6 2 1 4 7 3
3 7 4 9 8 5 1 2 6
4 5 7 1 9 3 8 6 2
9 8 3 2 4 6 5 1 7
6 1 2 5 7 8 3 9 4
Dominik Bathon
It uses logic to deduce numbers for open cells which is enough for most
easy and intermediate sudokus (this is quite fast, usually <100ms), but it
can also guess and backtrack to solve the hard ones and those with
multiple solutions.
The SudokuSolver class can solve sudokus for all valid square board sizes
(1x1, 4x4, 9x9, 16x16, ...), but the "if $0 == __FILE__"-part only handles
9x9 puzzles.
Dominik
The code:
class SudokuSolver
# returns the internal representation as array of arrays
def to_a
@arr.collect { |row| row.collect { |x|
(x.size == 1) ? x[0] : nil
} }
end
# returns a simple string representation
def to_s
fw = @n.to_s.size
to_a.collect { |row| row.collect { |x|
(x ? x.to_s : "_").rjust(fw)
}.join " " }.join "\n"
end
# returns whether the puzzle is solved
def finished?
@arr.each { |row| row.each { |x| return false if x.size > 1 } }
true
end
# for each cell remove the possibilities, that are already used in the
# cell's row, col or box
# return if successful
def reduce
success = false
@n.times { |r| @n.times { |c|
if (sz = @arr[r][c].size) > 1
@arr[r][c] = @arr[r][c] -
(@rfix[r] | @cfix[c] | @bfix[rc2box(r, c)])
raise "impossible to solve" if @arr[r][c].empty?
# have we been successful
if @arr[r][c].size < sz
success = true
update_fix(r, c)
end
end
} }
success
end
# find open cells with unique elements in their row, col or box
# return if successful
# reduce must return false when this method is called (if the
possibilities
# aren't reduced, bad things may happen...)
def deduce
success = false
[:col_each, :row_each, :box_each].each { |meth|
@n.times { |i|
u = uniqs_in(meth, i)
unless u.empty?
send(meth, i) { |x|
if x.size > 1 && ((u2 = u & x).size == 1)
success = true
u2
else
nil
end
}
# change only one row/col/box at a time
return success if success
end
}
}
success
end
# tries to solve the sudoku with reduce and deduce
# returns one of :impossible, :solved, :unknown
def solve
begin
until finished?
progress = false
while reduce
progress = true
end
progress = true if deduce
return :unknown unless progress
end
:solved
rescue
:impossible
end
end
# solves the sudoku using solve and if that fails, it tries to guess
private
# returns the box index of row r and col c
def rc2box(r, c)
(r - (r % @sqrt_n)) + (c / @sqrt_n)
end
# if row r, col c contains a fixed cell, it is added to the fixed
arrays
def update_fix(r, c)
if @arr[r][c].size == 1
@rfix[r] << @arr[r][c][0]
@cfix[c] << @arr[r][c][0]
@bfix[rc2box(r, c)] << @arr[r][c][0]
end
end
# yields each cell of row r and assigns the result of the yield unless
it
# is nil
def row_each(r)
@n.times { |c|
if (res = yield(@arr[r][c]))
@arr[r][c] = res
update_fix(r, c)
end
}
end
# yields each cell of col c and assigns the result of the yield unless
it
# is nil
def col_each(c)
@n.times { |r|
if (res = yield(@arr[r][c]))
@arr[r][c] = res
update_fix(r, c)
end
}
end
# yields each cell of box b and assigns the result of the yield unless
it
# is nil
def box_each(b)
off_r, off_c = (b - (b % @sqrt_n)), (b % @sqrt_n) * @sqrt_n
@n.times { |i|
r, c = off_r + (i / @sqrt_n), off_c + (i % @sqrt_n)
if (res = yield(@arr[r][c]))
@arr[r][c] = res
update_fix(r, c)
end
}
end
# find unique numbers in possibility lists of a row, col or box
# each_meth must be :row_each, :col_each or :box_each
def uniqs_in(each_meth, index)
h = Hash.new(0)
send(each_meth, index) { |x|
x.each { |n| h[n] += 1 } if x.size > 1
nil # we didn't change anything
}
h.select { |k, v| v == 1 }.collect { |k, v| k }
end
end
Gavin Kistner
> # Loads the @board array from a string matching the example above.
> def load(str)
> line_num = 0
> str.each_line do |line|
> line.gsub! '+', ''
> line.gsub! '-', ''
> line.gsub! '|', ''
> line.gsub! ' ', ' '
> line.gsub! '_', '0'
> line.strip!
> if line.length > 0
> l = line.split
> fail "Line length was #{l.length}" unless l.length == 9
> @board[line_num] = l.collect {|x| x.to_i}
> line_num += 1
> end
> end
>
> fail "Board is not valid." unless self.valid?
> end
How about just:
numbers = str.scan( /[\d_]/ ).collect{ |char| char.to_i }
and then check to see if you got 81 numbers or not (and split them up
into chunks of nine if you so desire).
James Edward Gray II
> James, I'll edit the code, because these are nice changes. I hate
> to spam the list, but I'm assuming that reposting is the preferred
> way to update code for the Quiz, since you simply reference the web
> archive of the post directly?
Sure, feel free to repost. However, I've already edited that method
in the summary. ;)
James Edward Gray II
Travis Smith
> So here's one thing I couldn't figure out last night, maybe someone can help 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.
>
> def solve
> deduce
> startGuessing if !solved
> return solved
> end
>
> def deduce
> ...work...
> raise BadGuess if conflict
> end
>
> def startGuessing
> @depth+=1
> 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
> # 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.
--
~Travis
Kroeger Simon (ext)
> > Is it posiible that you use ruby 1.8.1 or older?
> > If so, download a newer version :) or replace
>
> Thanks, that was it.
It took me some time to figure that out on a second pc :)
> And congrats, you win :) I modified your code to run a single puzzle
> at at time, and ran the set of 55 puzzles:
hmm .. it should be happy with just one puzzle.
But thank you for the flowers anyway :)
> $ for i in *.sdk; do time ruby MySolver.rb $i ;done >tmy 2>&1
>
> $ ruby parsetimes.rb tmy
> min max total ave
> 0.037 0.722 11.55 0.21
>
> $ for i in *.sdk; do time ruby SKSolver.rb $i ;done >tsk 2>&1
>
> $ ruby parsetimes.rb tsk
> min max total ave
> 0.049 0.331 10.043 0.1826
You have a fast machine!
~0.2 average on this set isn't bad at all.
> Your time on the hard ones is twice as fast as mine.
> I really like the idea of the COMBINED_NEIGHBORHOODS array.
> I think I learned a lot by deciphering your code even if I'm still not
> sure I completely understand the main loop.
which one? the one labeled #main or the main solving loop?
Ok, just some random thoughs because I don't have time to come up
with another version before this nice quiz is over:
I tried some more elaborated logic (as others) but it seems they don't
buy you much. e.g. I generalise your findPairs to find groups of
identical possibilities and clear these possibilities from the other
cells (if the group is as large as the number of possibilities
contained) But it never found such a group with more than 2 members.
I also tried a lookahead algorithm:
If there is no stringent next move, look for a cell with only 2
possibilities. Create 2 Boards which these cell set to each of the
possibilities, solve both of them as far as possible without guessing.
If one turns out to be unsolveable this is trivial, if not remove
from the original board for all cells all possibilities that are not in
either of the 2 boards.
(its slower than just brute forcing)
What I had done if I had more time:
Replacing the possibilities Sets by plain Fixnumns, using the first
9 bits as indicators if a move is still possible or not.
Perhaps even move the value of the cell in the upper part of that
fixnum, so there is only one array of 81 fixnums containing the whole
board.
Show that a totally braindead brute force solution written in c is
faster :/
cheers
Simon
p.s.: may I suggest finding hard sodukus one of the next quizes?
David Brady
>I actually worked on this before the Sudoku challenge even came up. I
>think, based on your e-mail, it uses the same recursive algorithm that
>you do, but I haven't verified that yet.
>
Our algorithms are essentially similar. One optimization I made is that
instead of attempting to solve the first empty cell seen, I skim over
all of the empty cells and find the one with the fewest possible
solutions. The value of this optimization appears to be a wash; most
boards I clock under your time by 20-50%, but on the "hard board" you
clock a 20s against my "more efficient" 37s. Wild. Something about
that puzzle forces any solver to grind deep and hard, and your not
taking extra time to think about the next move pays off handsomely.
Your calculate_options method seems to do what my settle method does,
finding unsolved cells with only one option. One question I had while
reading your code, what happens if your loop finds a cell with options,
then finds a cell to settle, and settling it causes the other cell to no
longer have options (but to be settled)? have_options is never reset.
The only valid case this can happen is if calculate_options solves the
puzzle, so you could probably test for it outside the method.
Hmm, you don't use the return value, so I guess the point is moot. :-)
Also, I just noticed that the unit tests I uploaded yesterday were
broken, because I renamed the settle() method. (It used to be called
'flatten', but that has some existing semantics from Array#flatten.
Since they are not similar, I changed the name due to POLS.)
-dB
P.S. James, I made the changes to initialize; they are uploaded now.
For the list's benefit, here is the new load method:
# ----------------------------------------------------------------------
def load(str)
line_num = 0
str.each_line do |line|
line.gsub!('_','0')
line.delete!('+|-')
line.strip!
if line.length > 0
l = line.split /\s+/
fail "Line length was #{l.length}. line: #{line}" unless
l.length == 9
@board[line_num] = l.collect {|x| x.to_i}
line_num += 1
end
end
fail "Board is not valid." unless self.valid?
end
# ----------------------------------------------------------------------
--
David Brady
ruby...@shinybit.com
Gavin Kistner
> On Aug 23, 2005, at 11:14 PM, Gavin Kistner wrote:
>> If nothing else, how about:
>> line.gsub!( /[+| -]/, '' )
>
> line.delete!("+-| ")
Oooh, I didn't know/forgot about that method. Nice :)
Mohit Muthanna
> boards I clock under your time by 20-50%, but on the "hard board" you
> clock a 20s against my "more efficient" 37s. Wild. Something about
> that puzzle forces any solver to grind deep and hard, and your not
> taking extra time to think about the next move pays off handsomely.
Interesting... thanks... :-)
> Your calculate_options method seems to do what my settle method does,
> finding unsolved cells with only one option. One question I had while
> reading your code, what happens if your loop finds a cell with options,
> then finds a cell to settle, and settling it causes the other cell to no
> longer have options (but to be settled)? have_options is never reset.
I initially wanted to use have_options within brute_force, basically
to tell me that the current iteration is a dead end. But then I found
an easier way out, and left it at that.
--
Mohit Muthanna [mohit (at) muthanna (uhuh) com]
"There are 10 types of people. Those who understand binary, and those
who don't."
James Edward Gray II
> Actually the only thing wrong with your code is that you pulled a
> Knuth: "Beware of bugs in the above code; I have merely proved it
> correct, not tried it." Your load function calls "Integet" instead
> of "Integer".
Thank you for bringing my error to my attention. I've corrected it
on the Ruby Quiz web site.
James Edward Gray II
David Brady
>Should I post my third version, or is everyone sick of looking at my
>code by now?
>
He posts an 8000% speed increase and he wants to know if we want to see
his code.... :-)
-dB
Mohit Muthanna
> every column and every 3x3 block, then take their intersection. I
> believe some other authors have already posted this concept; I'm only
> posting because I appear to be the only person to do it using array
> subtraction. :-) I find the intersection that has the fewest options
> available to it, and iterate over those choices, using recursion to
> solve the rest of the board.
Ahem... Mine used array subtraction too. Sorry.
--- SNIP (class Options) ----
def calculate_options_at( row, col )
(
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
board.row( row ) -
board.col( col ) -
board.region(
board.get_region_num( row, col )
)
)
end
--- SNIP -----
I actually worked on this before the Sudoku challenge even came up. I
think, based on your e-mail, it uses the same recursive algorithm that
you do, but I haven't verified that yet.
Also, there's less idiomatic Ruby here than there could / should be.
After re-reading this code I realize that some of these methods can be
reduced to one-liners.
Here it is (Download at http://muthanna.com/ruby-sudoku.tar.gz).
#!/usr/bin/env ruby
=begin rdoc
The Ruby Sudoku Solver
Mohit Muthanna Cheppudira <mo...@muthanna.com>
Sudoku, Japanese, sometimes spelled Su Doku,
is a placement puzzle, also known as Number Place in the
United States. The aim of the puzzle is to enter a numeral
from 1 through 9 in each cell of a grid, most frequently a
9×9 grid made up of 3×3 subgrids (called "regions"), starting
with various numerals given in some cells (the "givens"). Each
row, column and region must contain only one instance of each
numeral.
To Learn more about Sudoku, visit the great Wikipedia.
This implementation of the Sudoku solver uses an educated brute
force approach. By educated brute-force, I mean the solver:
* Narrows down options available in the empty places
* Fills in cells that have only one option
* For cells that have more than one option:
* Try each one, then recurse (Narrow down, fill-in, etc.).
This file consists of five classes:
* Line: Represents a set of 9 cells. This could be a Row, a
Column, or a Region.
* Options: Represents a set of valid options for a cell. This is
meant to be used as a workspace or scratch-pad for the Solver.
* Board: Represents the 9x9 Sudoku board. Has helper methods
to access cells, rows, columns and regions.
* Csv: Utility class used to load boards from CSV files.
* Solver: Our educated brute-force solver.
=end
module Sudoku
=begin rdoc
A Sudoku Line is basically an array that is
1-indexed. A Line could be a complete row, column or region.
=end
class Line < Array
=begin rdoc
This class variable represents the set of digits that
are valid in a Sudoku cell.
=end
@@valid_digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
=begin rdoc
We overload the [] operator so that the cells are
indexed from 1 till 9, instead of 0 till 8.
=end
def []( num )
at( num - 1 )
end
=begin rdoc
The to_s method is called by other methods that
need a string representation of the class. E.g., puts()
In this case, the code:
line = Line.new << 0 << 1 << 4 << 5
puts line
Displays:
0, 1, 4, 5
=end
def to_s
self.join( ", " )
end
=begin
This method returns a list of missing digits
in the line.
=end
def missing_digits
return @@valid_digits - self
end
=begin
Check if the Line or Region is
valid, i.e., has unique digits between
1 and 9, and has no zeros.
This method is used by the Solver to determine
if the solution is correct.
=end
def valid?
digits = Array.new
# Navigate each cell:
(1..9).each do |value|
# Invalid if any zeros.
return false if self[value] == 0
# Invalid if duplicate.
if digits[self[value]] == true
return false
else
# First occurrence. Log it.
digits[self[value]] = true
end
end
# Valid Line.
return true
end
end
=begin rdoc
This class defines a basic 9 x 9 Sudoku
board. The board is subdivided into smaller
3 x 3 regions. These regions are numbered
from 1 to 9 as so: Top to Bottom, Left to Right.
e.g., Top Left is Region 1
The region beneath 1 (row 4, col 1) is 2
Top Middle is Region 4.
You get the picture.
=end
class Board
def initialize( board = nil )
if board == nil
reset
else
# Our copy constructor. In ruby all variables are
# references to classes. Copies have to be
# explicit.
reset
board.each {|row, col, val| self[row,col] = val}
end
end
=begin rdoc
Our board is represented by a two-dimensional 9x9 array.
=end
def reset
@board = Array.new( 9 ) { Array.new( 9, 0 ) }
end
=begin rdoc
Cells in this board can be referenced with this method. Uses row, col; not x, y.
A bit retarded, but works.
=end
def []( row, col )
return @board[col-1][row-1]
end
def []=( row, col, val )
return (@board[col-1][row-1] = val)
end
=begin
Draw up a simple ASCII Sudoku board.
=end
def to_s
string = " 1 2 3 4 5 6 7 8 9\n"
string += " +--------------------------\n"
filled_in = 0
(1..9).each do |r|
row( r ).each { |cell| filled_in += 1 unless cell == 0 }
string += r.to_s + " | " + row( r ).to_s + "\n"
end
return string + "Filled: #{filled_in} / 81\n"
end
def row( row_num )
r = Line.new
(1..9).each { |c| r << self[ row_num, c ] }
return r
end
def col( col_num )
return Line.new( @board[ col_num - 1] )
end
=begin
Return a region (class Line) of cells determined
by a region number. The regions are numbered incrementally
top to bottom, left to right. So the cell at row 2, column
2 is at region 1; 5, 5 is region 5; 7, 4 is region 8.
=end
def region( region_num )
region = Line.new
start_row = ((( (region_num - 1) % 3 )) * 3) + 1
start_col = (((region_num - 1) / 3) * 3) + 1
(start_row..start_row + 2).each do |row|
(start_col..start_col + 2).each do |col|
region << self[row, col]
end
end
return region
end
=begin
Return a region number given a row and column.
=end
def get_region_num( row, col )
region_row = ( (row - 1) / 3 ) + 1
region_col = ( (col - 1) / 3 ) + 1
region_num = region_row + ( 3 * (region_col - 1))
end
=begin
Used to iterate through each cell on the board.
=end
def each
(1..9).each do |row|
(1..9).each do |col|
yield row, col, self[row, col]
end
end
end
=begin rdoc
Go through each row, column and region to
determine if the board is valid.
=end
def valid?
(1..9).each do |line|
return false if (
!row( line ).valid? ||
!col( line ).valid? ||
!region( line ).valid?
)
end
return true
end
end
=begin
This class loads a Sudoku board from a CSV file, A sample
board would look like this:
# Sample Board
0,0,0,0,2,3,4,0,0
0,6,3,0,9,8,0,0,0
4,0,0,5,0,0,0,0,0
0,2,5,0,8,0,0,7,3
0,1,0,0,0,0,0,5,0
6,4,0,0,5,0,1,9,0
0,0,0,0,0,5,0,0,8
0,0,0,9,7,0,3,6,0
0,0,6,8,3,0,0,0,0
Blank lines and lines beginning with hashes (#) are
ignored.
You can also save to CSV files by generating a
string via the to_s method.
=end
class Csv
def initialize( board = nil )
if board == nil
@board = Board.new
else
@board = board
end
end
def load( file_name )
File.open( file_name, "r" ) do |file|
row = 1
while line = file.gets
# Strip out all comments and
# blank lines.
line.chomp!
next if line =~ /^\s*#/
next if line =~ /^\s*$/
col = 1
line.split(",").each do |value|
@board[row, col] = value.to_i
col += 1
end
row += 1
end
end
@board
end
=begin rdoc
Generate a CSV string representing the board.
=end
def to_s
string = ""
(1..9).each do |r|
string += @board.row( r ).to_s + "\n"
end
return string
end
end
=begin
This class is represents a set of options for Sudoku cells. It's
simply a three dimensional array.
=end
class Options
def initialize
@options = Array.new( 9 ) { Array.new( 9 ) { Array.new } }
end
def []( row, col )
return @options[col-1][row-1]
end
def []=( row, col, val )
return (@options[col-1][row-1] = val)
end
def to_s
string = ""
(1..9).each do |row|
(1..9).each do |col|
string += self[row, col].join(",") + ":"
end
string += "\n"
end
string
end
end
=begin
Our Edumicated Brute-Force Sudoku Solver.
=end
class Solver
attr_accessor :board, :options
def initialize( board=nil )
if board
@board = board
else
@board = Board.new
end
@options = Options.new
end
=begin rdoc
This method returns a list of digits that are valid inside
a specific cell. It works by subtracting the set of cells
in the specific row, column and region from a full-line, i.e,
[1, 2, 3, 4, 5, 6, 7, 8, 9].
=end
def calculate_options_at( row, col )
(
[1, 2, 3, 4, 5, 6, 7, 8, 9] -
board.row( row ) -
board.col( col ) -
board.region(
board.get_region_num( row, col )
)
)
end
=begin rdoc
This method navigates through each cell in the board,
calculating a set of options for the cell. For cells
that have just one available option:
* Set the cell with the available option.
* Recalculate options.
If no options could be calculated, we hit a dead-end; return
false.
=end
def calculate_options
again = true
have_options = false
while again
again = false
self.options = Options.new
# Navigate each cell...
board.each do |row, col, value|
# If the cell is empty...
if value == 0
# Set the options for the cell
options[ row, col ] += calculate_options_at( row, col )
end
# How many options do we have?
number_of_options = options[row, col].length
# We had atleast one option; set return code.
have_options = true if number_of_options > 0
# Only one option here, reflect it on the
# board.
if number_of_options == 1
board[row, col] = options[row, col][0]
again = true
end
end
end
have_options
end
=begin rdoc
Our solve algorithm.
=end
def brute_force
# First narrow the board down.
calculate_options
# Navigate each cell
board.each do |row, col, value|
# If we see and empty cell:
if value == 0
# Navigate each option
options[row, col].each do |an_option|
# Save the state of the board, this is
# necessary because calculate_options()
# mangles the board.
old_board = Board.new( board )
# Try this option
board[row, col] = an_option
# Recurse
return true if brute_force
# No solution. Revert to saved board
# and try the next option.
@board = old_board
end
break
end
end
# Did we solve it?
return true if board.valid?
false
end
def solve
brute_force
end
end
=begin rdoc
Example code using this library. Reads a Sudoku-board file
from the command-line and solves it.
=end
def Sudoku.main
puts "Ruby Sudoku Solver - 12 Aug 2005"
puts "Mohit Muthanna Cheppudira <mo...@muthanna.com>"
puts
unless ARGV[0]
puts "Usage: #{$0} filename"
exit
end
# Load the board directly into the Solver.
solver = Solver.new( Csv.new().load( ARGV[0] ))
# Display the unsolved board.
puts "Problem:"
puts solver.board
if solver.solve
puts "\nSolution:"
else
puts "\nNo Solution. Best match:"
end
# Display the final board.
puts solver.board
end
Sudoku.main
end
Adam Shelly
I found a big speedup for the worst cases. I was looking at the debug
output for puzzle 50.
+-------+-------+-------+
| 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 _ _ |
+-------+-------+-------+
I noticed that it spent a lot of time making wrong guesses and only
filling in the upper left corner.
So I made the guesser start with the center box instead. It went from
104 guesses to 36.
before:
$> for i in *.sdk; do time ruby SodukuSolver.rb $i ; done >btime 2>&1
$> ruby parsetime.rb btime
min max total ave
0.032 2.604 14.299 0.259
after:
min max total ave
0.031 0.938 12.667 0.230
And it was a simple change:
in Cell.initialize, replace
@box = col/(bounds[0])+((row/bounds[1])*bounds[1])
with
@box = (col/(bounds[0])+((row/bounds[1])*bounds[1])+max/2)%max
to make the box in the center have 0 index.
and replace the function Solver.guess so that it iterates over the
boxes instead of the rows:
def guess
2.upto(@size) do |min|
@boxes.each do |set|
set.each do |cell|
if cell.possible.size == min
g = Guess.new(cell)
cell.set(g.value)
@queue << cell
dprint g
return g
end
end
end
end
dprint "did not find a guess\n"
return nil
end
Ok, I'm done now.
-Adam
Adam Shelly
> 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
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...
Thanks for any ideas,
-Adam
David Brady
gateway. :-)
You can view my complete solution on the web, however. My code, unit
tests, and board data are at
http://www.xmission.com/~dbrady/ruby/sodoku/sodoku.tgz . All of the
files in that archive are also at that url, so you can grab any of the
files directly by replacing sodoku.tgz with any of: sodoku.rb,
test_sodoku.rb, dbrady_solutions.txt, board1.txt, board2.txt,
board3.txt, board4.txt, board5.txt, board6.txt.
My strategy was to build an array of the possible moves for every row,
every column and every 3x3 block, then take their intersection. I
believe some other authors have already posted this concept; I'm only
posting because I appear to be the only person to do it using array
subtraction. :-) I find the intersection that has the fewest options
available to it, and iterate over those choices, using recursion to
solve the rest of the board. Using a set probably would have been
better, but I didn't know about Ruby sets until after I finished my
code. So my solution is a very elegant way of wielding a stone axe. :-)
My poor, unaccelerated laptop clocks in under 2s in most cases, and
rejects Karl von Lauderman's unsolvable puzzle in 200ms. The really
difficult one takes 33-38 seconds, depending on whether my mp3 player is
going. :-)
One developmental note. Ruby continues to be an exceedingly pleasant
language to work and design in. I wrote a complete solver with loads of
unit tests, and I was pleased to discover that it could even solve
Karl's unsolvable puzzle. Nifty! As I was double-checking everything,
I realized that I had completely overlooked the requirement to have all
the cells in a *block* be unique! (I have never heard of Sodoku before
today.) I thought about it for a moment, then realized that all I
needed to do was add Sodoku#possible_block_values to the class, and make
sure that possible_values intersected that with the results from the
row/column query. I plugged in the extra code, and discovered that my
code became *faster* on account of rejecting more possibilities sooner.
I added another board, that seemed interesting to me to solve:
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ _ _ |
+-------+-------+-------+
Also notably absent in my code is any kind of a custom Exception for bad
boards. They're not idiomatic for me so I used them very sparingly.
Anyway, without further ado, my solution is attached.
Cheers,
Adam Shelly
>
> > Ok, here's my latest. My big speedup was figuring out that if I make
> > a bad guess, I just eliminate that possibility and re-solve. See the
> > startGuessing method..
>
>
> guess wrong, at least I know the right guess. (of course only if there
> are cells with 2 possibilities - but that happens often) If I interpret
> your guess method right you are doing the same thing. So I do not
> understand where the speedup comes from.
>
I went back and looked at the differences between the two versions.
After a bad guess, my first version made another guess with the next
possibility on the same cell.
Now it just removes the bad guess and goes back to the logical solver.
I also speeded up the guesser itself - it used to check all the cells
for the one with the minimum number of possibilites, now it just finds
the first with 2 possibilities.
So that's why mine got better, but it was bad before.
I'd like to directly compare the speed of yours to mine on my machine,
but I can't get it to run correctly, It reports every board as UNSOLVABLE.
Has anyone else had any luck with it?
>Your 'findPairs' looks promissing... I think I will try something
>similar...
I thought that I could speed it up by deducing more cells before I
started guessing, soI tried adding another step to the logic phase:
If any row or col has all it's instances of a given digit in the same
3x3 box, then that digit can be removed from the other 6 cells in the
box.
But it turned out to make the code slower, I think because it wasn't
very efficient, and in most cases it only ended up solving 1 or 2
extra cells before having to go to the guesser anyway.
-Adam
James Edward Gray II
> Should I post my third version, or is everyone sick of looking at my
> code by now?
Please do. I can only talk about in the summary what I see.
James Edward Gray II
Adam Shelly
> But it is solvable:
>
Since everyone pointed this out, I worked on my guessing code more.
Now I get
+-------+-------+-------+
| _ 2 _ | _ _ _ | _ _ _ |
| _ _ _ | 6 _ _ | _ _ 3 |
| _ 7 4 | _ 8 _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ _ 3 | _ _ 2 |
| _ 8 _ | _ 4 _ | _ 1 _ |
| 6 _ _ | 5 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ _ | _ 1 _ | 7 8 _ |
| 5 _ _ | _ _ 9 | _ _ _ |
| _ _ _ | _ _ _ | _ 4 _ |
+-------+-------+-------+
Only Solveable by Guessing
+-------+-------+-------+
| 1 2 6 | 4 3 7 | 9 5 8 |
| 8 9 5 | 6 2 1 | 4 7 3 |
| 3 7 4 | 9 8 5 | 1 2 6 |
+-------+-------+-------+
| 4 5 7 | 1 9 3 | 8 6 2 |
| 9 8 3 | 2 4 6 | 5 1 7 |
| 6 1 2 | 5 7 8 | 3 9 4 |
+-------+-------+-------+
| 2 6 9 | 3 1 4 | 7 8 5 |
| 5 4 8 | 7 6 9 | 2 3 1 |
| 7 3 1 | 8 5 2 | 6 4 9 |
+-------+-------+-------+
real 0m0.203s
user 0m0.218s
sys 0m0.015s
And my previous slowest one went from 16.3s down to 0.37s
The newest slowest is
+-------+-------+-------+
| 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 _ _ |
+-------+-------+-------+
Only Solveable by Guessing
+-------+-------+-------+
| 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 |
+-------+-------+-------+
real 0m2.844s
user 0m2.858s
sys 0m0.015s
Should I post my third version, or is everyone sick of looking at my
code by now?
-Adam
David Tran
It seems difficult and low performace to backtracting possibilities data set ...
I did try to duplicate possibilities data and each guess to reduce the
possibilities data set.
But it is slow then just using brute force.
( Time is wasted on recursive process on the possiblilities data set
maintenance/creation )
This version will just reduce the possibilities data set only once
then using brute force.
It is much faster than my previous program ( of course, it is slower
than others good program ... )
--------------------------------------------
class Sodoku
attr_reader :solutions
def initialize( input )
@cells = Array.new(81)
@possibilities = {}
@solutions = 0
index = 0
input.to_s.scan(/./) do |c|
case c
when '1'..'9' : @possibilities[index] = [ @cells[index] = c.to_i ]
when '_' : @possibilities[index] = (1..9).to_a
else next
end
break if (index += 1) == 81
end
# raise "Input data incomplete" if index != 81
end
def solve
return false unless reduce_possibilities # reduce only once then
return _solve(0) # brute force to solve it
end
def show_all_solutions
return unless reduce_possibilities # reduce only once then
_solve_all(0) # brute force to solve all solutions
end
# to_s borrow from Simon ...
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] || "_"
end.join(" ")
end.join(" | ")
end.join(" |\n| ")
end.join(" |\n+-------+-------+-------+\n| ") +
" |\n+-------+-------+-------+\n"
end
private
# The cell's neighborhoods are cells need to check to be sure no duplicate
# value with the cell. It has exactly 20 cells neighborhoods per cell.
NEIGHBORHOODS = Array.new(81) do |index|
row, col = index / 9, index % 9
r, c = row / 3 * 3, col / 3 * 3
ary = []
9.times do |i|
ary << (i * 9 + col) # add cells at the same column
ary << (row * 9 + i) # add cells at the same row
ary << ((i/3) + r) * 9 + (i%3) + c # add cells at the same 3x3 box
end
ary.uniq - [index]
end
def reduce_possibilities
index = number = nil
while @possibilities.find { |index, number| number.size == 1 }
@possibilities.delete(index)
neighborhoods = NEIGHBORHOODS[index]
@possibilities.each do |key, value|
next unless neighborhoods.include?(key)
value -= number
if value.size == 0
return false # invalid input data
else
@possibilities[key] = value
end
end
end
true
end
def _solve(start)
start.upto(80) do |index|
next if @cells[index]
@possibilities[index].each do |value|
next if NEIGHBORHOODS[index].any? { |i| @cells[i] == value }
@cells[index] = value
_solve(index + 1) ? (return true) : @cells[index] = nil
end
return false
end
true
end
def _solve_all(start)
start.upto(80) do |index|
next if @cells[index]
@possibilities[index].each do |value|
next if NEIGHBORHOODS[index].any? { |i| @cells[i] == value }
@cells[index] = value
_solve_all(index + 1)
@cells[index] = nil
end
return
end
@solutions += 1
puts self
end
end
if __FILE__ == $0
input = ''
while line = gets
input << line
end
sodoku = Sodoku.new(input)
puts sodoku.solve ? sodoku : "No solution"
# sodoku = Sodoku.new(input)
# sodoku.show_all_solutions
# puts "Total #{sodoku.solutions} solutions."
end
David Tran
The java's continue label is like:
static void ShowAllAns() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (puzzle[i][j] <= 0) {
next_value: for (int value = 1; value <= 9; value++) {
// On the same column, make sure no any row already used it
// On the same row, make sure no any column already used it
for (int k = 0; k < 9; k++) {
if ((puzzle[k][j] == value) || (puzzle[i][k] == value)) {
continue next_value; // continue with label
}
}
// On the 3x3 box, make sure no other cell already used it
int p = (i / 3) * 3;
int q = (j / 3) * 3;
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (puzzle[p+x][q+y] == value) {
continue next_value; // continue with label
}
}
}
puzzle[i][j] = value;
ShowAllAns();
puzzle[i][j] = 0;
}
return; // tried all possible value, just return
}
}
}
PrintPuzzle();
}
----------------------------
I translated like :
def solve
9.times do |row|
9.times do |col|
next if @ary[row][col]
# find next possible value for @ary[row][col]
1.upto(9) do |v|
# check on same row/col, no any col/row already used it
next unless 9.times { |i| break if @ary[i][col] == v ||
@ary[row][i] ==v }
# check on 3x3 box, no other cell already used it
next unless 3.times do |i|
break unless 3.times do |j|
break if @ary[i + row / 3 * 3][j + col / 3 * 3] == v
end
end
@ary[row][col] = v
if solve
return true
else
@ary[row][col] = nil # backtracking
end
end
return false
end
end
true
end
-------------------------------
Using too many breaks to simulate Java's continue label...
I almost forget Ruby's throw-catch.
I think translate Java's continue label the "Ruby" way maybe like this:
def solve
9.times do |row|
9.times do |col|
next if @ary[row][col]
# find next possible value for @ary[row][col]
1.upto(9) do |v|
catch :next do
# check on same row/col, no any col/row already used it
9.times { |i| throw :next if @ary[i][col] == v || @ary[row][i] ==v }
# check on 3x3 box, no other cell already used it
3.times do |i|
3.times do |j|
throw :next if @ary[i + row / 3 * 3][j + col / 3 * 3] == v
end
end
@ary[row][col] = v
if solve
return true
else
@ary[row][col] = nil # backtracking
end
end
end
return false
end
end
true
end