Who likes Sudoku?

casper_the_ghost · July 15, 2006, 5:00pm

Here is the smallest Ruby Sudoku solver I could come up with. I’ve
seen a bunch that are really big, but this is the most simplistic. I’d
like to shrink it a bit more, but it works well for now. Things like
reading in the ARGV line as Integers could remove all the “.to_i” tags.
Another line could be removed if the hash is declared within the loop
instead of the top of the subroutine. Is there are way to loop through
numbers 1…9 using the 10.times notation so I don’t have to skip ‘0’ –
it’d be nice to remove that line too? Can we GOLF this anymore? I’m
going to keep refining it, so I’ll post any updates later on. This was
a fun problem - Ruby Rocks!

/----------------------------------------------------------------------------------------------------/

A ruby script to solve sudoku puzzle

USAGE: ruby sudoku.rb <Sudoku puzzle on one line/no spaces with 0’s

being the blanks>

Example:ruby sudoku.rb 000201600…09605000

Written by: Studlee2 at Gmail dot com

algorithm by http://www.ecclestoad.co.uk/

$puzzle = ARGV.shift.split(//)

def sudoku_solver
hash = Hash.new()
80.times do |j|
next if $puzzle[j].to_i != 0
80.times {|k| hash[k.to_i / 9 == j / 9 ||k.to_i%9 == j%9 || k.to_i
/ 27 == j / 27 && k.to_i%9/3 == j%9/3 ?$puzzle[k.to_i]:0] = 1}
10.times {|v| next if v==0 || hash.has_key?(v.to_s); $puzzle[j] =
v.to_s; sudoku_solver}
return $puzzle[j] = 0;
end
return puts “The solution is:#{$puzzle}”
end

sudoku_solver
/----------------------------------------------------------------------------------------------------/

Enjoy,
_Steve

casper_the_ghost · July 15, 2006, 5:57pm

Hi –

On Sun, 16 Jul 2006, [email protected] wrote:

Here is the smallest Ruby Sudoku solver I could come up with. I’ve
seen a bunch that are really big, but this is the most simplistic. I’d
like to shrink it a bit more, but it works well for now. Things like
reading in the ARGV line as Integers could remove all the “.to_i” tags.
Another line could be removed if the hash is declared within the loop
instead of the top of the subroutine. Is there are way to loop through
numbers 1…9 using the 10.times notation so I don’t have to skip ‘0’ –
it’d be nice to remove that line too? Can we GOLF this anymore? I’m

Has GOLF become a “backronym”? I thought it was just “golf”, but I
keep seeing it in uppercase.

going to keep refining it, so I’ll post any updates later on. This was
a fun problem - Ruby Rocks!

Anyway – sure you can reduce it a bit. Change $puzzle to $p, to
start with, and get rid of a bunch of spaces (I haven’t looked at
the logic yet so my suggestions are pretty cosmetic.)

David

casper_the_ghost · July 15, 2006, 6:07pm

I’m not really sure about the whole “GOLF” vs. “golf”. We’ll say
‘GOLF’.downcase and call it even. I think ‘golf’ is the right way to
refer to squeezing code.

_Steve

casper_the_ghost · July 15, 2006, 7:11pm

[email protected] wrote:

Is there are way to loop through
numbers 1…9 using the 10.times notation so I don’t have to skip ‘0’ –
it’d be nice to remove that line too?

1.upto(10){|i| … }

Cheers,
Daniel

casper_the_ghost · July 15, 2006, 7:17pm

$p = $*[0].split //
def s
h={};80.times{|j|next if $p[j]!=0;80.times
{|k|h[k/9==j/9||k%9==j%9||k/27==j/27&&k%9/3==j%9/3 ?$p[k]:0]=1}
10.times{|v| next if v==0||h[v];$p[j]=v;s};return $p[j]=0}
return (puts “\nSolution:#{$p}” )
end

I havent looked at anything special in particular to cut it down!

J`ey
http://www.eachmapinject.com
http://www.eachmapinject.com/treasure_chest

casper_the_ghost · July 15, 2006, 7:11pm

This is a little smaller.

$p = ARGV.shift.split(//)

def s
h = Hash.new()
80.times do |j|
next if $p[j].to_i != 0
80.times {|k| h[k.to_i / 9 == j / 9 ||k.to_i%9 == j%9 || k.to_i /
27 == j / 27 && k.to_i%9/3 == j%9/3 ?$p[k.to_i]:0] = 1}
10.times {|v| next if v==0 || h.has_key?(v.to_s); $p[j] = v.to_s;
s}
return $p[j] = 0;
end
return (puts “\nSolution:#{$p}” )
end

s

casper_the_ghost · July 15, 2006, 7:36pm

On 7/15/06, [email protected] [email protected] wrote:

1.upto(9){|v|next if h.has_key?(v.to_s);$p[j]=v.to_s;s}
  return $p[j]=0;
end
return (puts “\nSolution:#{$p}”)
end

s

change h=Hash.new() to h={}

Phil

casper_the_ghost · July 15, 2006, 7:27pm

Smaller still. Thanks David/Daniel:

$p = ARGV.shift.split(//)

def s
h=Hash.new()
80.times do |j|
next if $p[j].to_i!=0

80.times{|k|h[k.to_i/9==j/9||k.to_i%9==j%9||k.to_i/27==j/27&&k.to_i%9/3==j%9/3?$p[k.to_i]:0]=1}
1.upto(9){|v|next if h.has_key?(v.to_s);$p[j]=v.to_s;s}
return $p[j]=0;
end
return (puts “\nSolution:#{$p}”)
end

s

casper_the_ghost · July 15, 2006, 8:07pm

Sorry, mine doesnt work. would you mind giving us an input and an output
to
test with?

j`ey
http://www.eachmapinject.com
http://www.eachmapinject.com/treasure_chest

casper_the_ghost · July 15, 2006, 8:01pm

Again:

$p=$*[0].split //;def s;h={};(a=0…80).map{|j|next if
$p[j]!=0;a.map{|k|h[k/9==j/9||k%9==j%9||k/27==j/27&&k%9/3==j%9/3?$p[k]:0]=1};
1.upto(9){|v|next if h.has_key?(v);$p[j]=v;s}end

j`ey
http://www.eachmapinject.com

casper_the_ghost · July 15, 2006, 10:34pm

On 7/15/06, Joey [email protected] wrote:

Sorry, mine doesnt work. would you mind giving us an input and an output to
test with?

Yes, before we golf this further, does it even work?
I gave the original version the input
003020600900305001001806400008102900700000008006708200002609500800203009005010300
which should solve to
483921657967345821251876493548132976729564138136798245372689514814253769695417382
but it just kept running and running and printing variations on strings
like
The solution is:
21345678945678912378912345612436589736589721489721436554163297867894153293257864
which is one digit too short, and has incorrect numbers in many
places…
It’s possible I didn’t wait long enough, but most solvers can finds
that answer in under a second.
-Adam

casper_the_ghost · July 15, 2006, 9:47pm

[email protected] wrote:

1.upto(9){|v|next if h.has_key?(v.to_s);$p[j]=v.to_s;s}
  return $p[j]=0;
end
return (puts “\nSolution:#{$p}”)
end

s

Other cosmetic suggestions:
change:
ARGV to $*
h=Hash.new to h={}
next if $p[j].to_i!=0 to $p[j].to_i!=0&&next
all do…end to {…}
get rid of new lines

lopex

casper_the_ghost · July 15, 2006, 11:12pm

Marcin MielÅ¼yÅ?ski wrote:

all do…end to {…}
get rid of new lines

Personally, I’d much rather have more do…end and more lines. Terseness
cannot be measured in mere character counts.

Daniel

casper_the_ghost · July 15, 2006, 11:15pm

“Adam S.” [email protected] wrote in message
news:[email protected]…

but it just kept running and running and printing variations on strings
like
The solution is:
21345678945678912378912345612436589736589721489721436554163297867894153293257864
which is one digit too short, and has incorrect numbers in many places…
It’s possible I didn’t wait long enough, but most solvers can finds
that answer in under a second.

Well, I've seen someone else on this newsgroup (or the mailing list)

write a sudoku solver in Ruby and their execution time was more than 30
seconds! This is quite understandable if the goal of the script was
minimizing lines of code rather than minimizing execution time…

However, if someone else finds the script to be broken then I think

it
likely is…

casper_the_ghost · July 15, 2006, 11:35pm

On 7/15/06, Adam S. [email protected] wrote:

Yes, before we golf this further, does it even work?

oops, my mistake. I was giving it a filename containing a puzzle on
the command line instead of the puzzle itself. It does run and
converge - but it leaves the last digit 0 unless you make the outer
loop 81.times. Here’s what I’ve got - I mapped the input to
integers, which removed a bunch of ‘to_i’s.
def s; h={}
81.times{|j| next if $p[j]>0
80.times {|k| h[$p[k]] = 1 if k/9==j/9 || k%9==j%9 || k/27==j/27
&& k%9/3==j%9/3}
1.upto(9){|v| $p[j]=v and s unless h[v]}
return $p[j]=0; }
p “Solution: #{$p}”
end;
$p = $*[0].split(’').map{|v|v.to_i}; s

casper_the_ghost · July 16, 2006, 2:06am

Adam S. wrote:

80.times {|k| h[$p[k]] = 1 if k/9==j/9 || k%9==j%9 || k/27==j/27
&& k%9/3==j%9/3}
1.upto(9){|v| $p[j]=v and s unless h[v]}
return $p[j]=0; }

There’s no need for the `return’ keyword, nor for the semicolon.

$p[j]=0}

p “Solution: #{$p}”
end;

The semicolon is unnecessary.

$p = $*[0].split(’’).map{|v|v.to_i}; s

Cheers,
Daniel

casper_the_ghost · July 16, 2006, 1:41am

Cut down, and formatted:
def s;h={};81.times{|j|next if$p[j]>0;80.times{|k|h[
$p[k]]=1 if k/9==j/9||k%9==j%9||k/27==j/27&&k%9/3==j%
9/3};1.upto(9){|v|($p[j]=v;s)if !h[v]};return$p[j]=0}
p "Solution:#$p"end;$p=$*[0].split(//).map{|v|v.to_i};s

j`ey
http://www.eachmapinject.com

casper_the_ghost · July 16, 2006, 10:07am

There is a need for the return, as it breaks execution.

casper_the_ghost · July 16, 2006, 5:42am

Thanks for all of the comments and suggestions.

_Steve