Who likes Sudoku?

S

studlee2

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
 
D

dblack

Hi --

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

--
http://www.rubypowerandlight.com => Ruby/Rails training & consultancy
http://www.manning.com/black => RUBY FOR RAILS (reviewed on
Slashdot, 7/12/2006!)
http://dablog.rubypal.com => D[avid ]A[. ]B[lack's][ Web]log
(e-mail address removed) => me
 
S

studlee2

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


Hi --

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

--
http://www.rubypowerandlight.com => Ruby/Rails training & consultancy
http://www.manning.com/black => RUBY FOR RAILS (reviewed on
Slashdot, 7/12/2006!)
http://dablog.rubypal.com => D[avid ]A[. ]B[lack's][ Web]log
(e-mail address removed) => me
 
D

Daniel Schierbeck

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
 
S

studlee2

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
 
S

studlee2

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
 
P

Phil Tomson

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
change h=Hash.new() to h={}

Phil
 
M

Marcin Mielżyński

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

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
 
A

Adam Shelly

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
 
D

Daniel Schierbeck

Marcin said:
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
 
J

Just Another Victim of the Ambient Morality

Adam Shelly said:
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.

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...
 
A

Adam Shelly

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
 
D

dblack

---2049402039-2037181348-1153004584=:21394
Content-Type: MULTIPART/MIXED; BOUNDARY="-2049402039-2037181348-1153004584=:21394"

This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.

---2049402039-2037181348-1153004584=:21394
Content-Type: TEXT/PLAIN; charset=X-UNKNOWN; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

Hi --

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

Definitely, but this is explicitly a round of code "golf", i.e.,
trying to get the code to work with the fewest "strokes" (keystrokes).
No one (I hope :) would claim that golf code has a nice style. I
like these things simply because I tend to learn interesting things
from them; like any exercise, it forces attention onto a subset of
available faculties.


David

--=20
http://www.rubypowerandlight.com =3D> Ruby/Rails training & consultancy
http://www.manning.com/black =3D> RUBY FOR RAILS (reviewed on
Slashdot, 7/12/2006!)
http://dablog.rubypal.com =3D> D[avid ]A[. ]B[lack's][ Web]log
(e-mail address removed) =3D> me
---2049402039-2037181348-1153004584=:21394--
---2049402039-2037181348-1153004584=:21394--
 
K

Kevin Olbrich

---2049402039-2037181348-1153004584=:21394
Content-Type: MULTIPART/MIXED;
BOUNDARY="-2049402039-2037181348-1153004584=:21394"

This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.

---2049402039-2037181348-1153004584=:21394
Content-Type: TEXT/PLAIN; charset=X-UNKNOWN; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

Hi --

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

Definitely, but this is explicitly a round of code "golf", i.e.,
trying to get the code to work with the fewest "strokes" (keystrokes).
No one (I hope :) would claim that golf code has a nice style. I
like these things simply because I tend to learn interesting things
from them; like any exercise, it forces attention onto a subset of
available faculties.


David

--=20
http://www.rubypowerandlight.com =3D> Ruby/Rails training & consultancy
http://www.manning.com/black =3D> RUBY FOR RAILS (reviewed on
Slashdot, 7/12/2006!)
http://dablog.rubypal.com =3D> D[avid ]A[. ]B[lack's][ Web]log
(e-mail address removed) =3D> me
---2049402039-2037181348-1153004584=:21394--
---2049402039-2037181348-1153004584=:21394--

FYI:

http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver

_Kevin
www.sciwerks.com
 
D

Daniel Schierbeck

Adam said:
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; }

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Members online

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,898
Latest member
BlairH7607

Latest Threads

Top