[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Idea for Ruby Quiz - Su Doku solver

Lyndon Samson

4/23/2005 11:32:00 AM

How the following look?

From http://news.bbc.co.uk/1/hi/magazine/4...

For those who don't know, it's a puzzle found in newspapers, books and
online. A simple-looking grid of nine rows by nine, split into nine
boxes, each containing nine squares, it looks like just another
numbers game.

But, say Su Doku experts, the difference is it can be played using
logic alone, so maths phobics read on.

To be pure Su Doku each of the unique puzzles - which come in varying
levels of difficulty - must have only one solution. The aim? To fill
in the grid so that every row, every column, and every box contains
the digits one to nine


--
Into RFID? www.rfidnewsupdate.com Simple, fast, news.
11 Answers

Douglas Livingstone

4/23/2005 1:26:00 PM

0

On 4/23/05, Lyndon Samson <lyndon.samson@gmail.com> wrote:
> How the following look?
>
> From http://news.bbc.co.uk/1/hi/magazine/4...
>

How about a Su Doku writer; the Su Doku solver would just be the unit tests :)

Douglas

Christian Neukirchen

4/23/2005 2:01:00 PM

0

Douglas Livingstone <rampant@gmail.com> writes:

> On 4/23/05, Lyndon Samson <lyndon.samson@gmail.com> wrote:
>> How the following look?
>>
>> From http://news.bbc.co.uk/1/hi/magazine/4...
>>
>
> How about a Su Doku writer; the Su Doku solver would just be the unit tests :)

After doing this evil game for an hour or so now, I agree. I think
programming a puzzle maker is harder than solving it automatically.
More useful, too. :-)

Evil game, beware.

> Douglas
--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

Bill Guindon

4/23/2005 2:11:00 PM

0

On 4/23/05, Christian Neukirchen <chneukirchen@gmail.com> wrote:
> Douglas Livingstone <rampant@gmail.com> writes:
>
> > On 4/23/05, Lyndon Samson <lyndon.samson@gmail.com> wrote:
> >> How the following look?
> >>
> >> From http://news.bbc.co.uk/1/hi/magazine/4...
> >>
> >
> > How about a Su Doku writer; the Su Doku solver would just be the unit tests :)
>
> After doing this evil game for an hour or so now, I agree. I think
> programming a puzzle maker is harder than solving it automatically.
> More useful, too. :-)
>
> Evil game, beware.

"He is pleased with the global growth of the game, to which he
contributed by taking it from a puzzle book he bought in Tokyo in 1997
and spending six years - "on and off" - writing a computer program
that produces new Su Dokus on the spot."

If somebody does this in 3 days with Ruby, it's probably gonna make
this guy cry.

> > Douglas
> --
> Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...
>
>

--
Bill Guindon (aka aGorilla)

dblack

4/23/2005 2:15:00 PM

0

Christian Neukirchen

4/23/2005 2:52:00 PM

0

Bill Guindon <agorilla@gmail.com> writes:

> On 4/23/05, Christian Neukirchen <chneukirchen@gmail.com> wrote:
>> Douglas Livingstone <rampant@gmail.com> writes:
>>
>> > On 4/23/05, Lyndon Samson <lyndon.samson@gmail.com> wrote:
>> >> How the following look?
>> >>
>> >> From http://news.bbc.co.uk/1/hi/magazine/4...
>> >>
>> >
>> > How about a Su Doku writer; the Su Doku solver would just be the unit tests :)
>>
>> After doing this evil game for an hour or so now, I agree. I think
>> programming a puzzle maker is harder than solving it automatically.
>> More useful, too. :-)
>>
>> Evil game, beware.
>
> "He is pleased with the global growth of the game, to which he
> contributed by taking it from a puzzle book he bought in Tokyo in 1997
> and spending six years - "on and off" - writing a computer program
> that produces new Su Dokus on the spot."
>
> If somebody does this in 3 days with Ruby, it's probably gonna make
> this guy cry.

IMO 3 days non-stop coding is pretty realistic (= 1 week of "ordinary"
coding). The game is not *that* hard to implement. The problem is
rather making it efficient enough to actually use it... I'd do it in
C, personally. Ruby doesn't provide a lot of support for 2d-Arrays
and there is not a lot to abstract.

Basically, you create a 9x9 array of numbers that fulfil the solution
(you can probably do that like the n-queens problem), assure there are
no symmetries (exchange numbers if needed) and then drop all
"unneeded" elements.

This will generate puzzles, at least, but I'm not sure if they will be
fun to solve.

> Bill Guindon (aka aGorilla)
--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

Florian Groß

4/23/2005 5:06:00 PM

0

Christian Neukirchen wrote:

> Ruby doesn't provide a lot of support for 2d-Arrays
> and there is not a lot to abstract.

What about NArray?

Christian Neukirchen

4/23/2005 5:34:00 PM

0

Florian Groß <florgro@gmail.com> writes:

> Christian Neukirchen wrote:
>
>> Ruby doesn't provide a lot of support for 2d-Arrays
>> and there is not a lot to abstract.
>
> What about NArray?

It exists, but where is the advantage over int[][]?

Anyway, I quickly wrote a Su Doku solver in gprolog, you can look at
it here:

http://rafb.net/paste/results/1og...

There are languages that have even less support for 2d-arrays. :-)

Happy hacking,
--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

Vance A Heron

4/24/2005 9:02:00 AM

0

I wrote a solver in Ruby in about 2 hrs - not pretty, but it
works. As mentioned by Christian, I used the same approach as
the 8-queens problem. I'm using the int[][] notation...

Solving runs fast enough in ruby - no need for 'C'. I find
it interesting to note the number of times you need to backtrack
in the puzzles rated "fiendish" difficulty. (In some, there
no backtracking at all!).

I'll think about a generator tomorrow - but it seems that much
of the "difficulty" is determined by *which* numbers you remove
from the answer. I haven't spent much time playing by
hand, but I'm figuring the difficulty from a computer stantpoint
is directly related to the bactracking. Looking at it, one might
be able to start recognizing patterns and make choices that require
less backtracking.

Vance


On Sun, 2005-04-24 at 02:34 +0900, Christian Neukirchen wrote:
> Florian Groß <florgro@gmail.com> writes:
>
> > Christian Neukirchen wrote:
> >
> >> Ruby doesn't provide a lot of support for 2d-Arrays
> >> and there is not a lot to abstract.
> >
> > What about NArray?
>
> It exists, but where is the advantage over int[][]?
>
> Anyway, I quickly wrote a Su Doku solver in gprolog, you can look at
> it here:
>
> http://rafb.net/paste/results/1og...
>
> There are languages that have even less support for 2d-arrays. :-)
>
> Happy hacking,

Christian Neukirchen

4/24/2005 1:13:00 PM

0

Vance A Heron <heron@jpl.nasa.gov> writes:

> I wrote a solver in Ruby in about 2 hrs - not pretty, but it
> works. As mentioned by Christian, I used the same approach as
> the 8-queens problem. I'm using the int[][] notation...
>
> Solving runs fast enough in ruby - no need for 'C'. I find
> it interesting to note the number of times you need to backtrack
> in the puzzles rated "fiendish" difficulty. (In some, there
> no backtracking at all!).

Yeah, exactly the same here. My prolog solver runs in 10-100ms per
puzzle.

> I'll think about a generator tomorrow - but it seems that much
> of the "difficulty" is determined by *which* numbers you remove
> from the answer. I haven't spent much time playing by
> hand, but I'm figuring the difficulty from a computer stantpoint
> is directly related to the bactracking. Looking at it, one might
> be able to start recognizing patterns and make choices that require
> less backtracking.

Generation turned out to me much harder than I thought, while I can
generate random puzzles very easily, I lack the prolog knowledge to
figure what fields can be deduced and which cannot.

Playing Sudoku by hand is pretty fun btw, after a few minutes you find
the patterns to look for. Still not easy, though.

> Vance
--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

James Gray

4/24/2005 3:25:00 PM

0

On Apr 24, 2005, at 4:01 AM, Vance A Heron wrote:

> I wrote a solver in Ruby in about 2 hrs - not pretty, but it
> works. As mentioned by Christian, I used the same approach as
> the 8-queens problem. I'm using the int[][] notation...

This sounds like a fine difficultly for a Ruby Quiz problem then.
Anyone willing to write up the quiz and send it to
suggestion@rubyquiz.com? I will sure run it.

James Edward Gray II