View mode: basic / threaded / horizontal-split · Log in · Help
December 12, 2005
Re: printf() problems
john schrieb:
> 
> Actually changing poss from bit to int made the problem stop.  I thought
> bit worked just like booleans in java, but something went awry.

Great! Nice knowing everything is fine now.
When you have first sent the message, I didn't know what Sudoku was... 
Afterwards I have seen the game on a local newspaper and noticed that this game seems to be very appreciated by people now.
There are even small pocket computers for sale for this kind of game...
Therefore, I have also decided to write a Sudoku solver in D.
Surprisingly, though, the problem is quite trivial to be solved!
It only took me about two hours to devise an algorithm and to write it in D!
I have ran it over two problems found in newspaper, and solved them quite easily.
You can check my version here - http://www.gasiba.de/D/sudoku.d
Would be nice to compare the running times between your version and mine.
The next step is how to create Sudoku tables, which, using the program I wrote is also a trivial task...

Best,
Tiago

-- 
Tiago Gasiba (M.Sc.) - http://www.gasiba.de
Everything should be made as simple as possible, but not simpler.
December 12, 2005
Re: printf() problems
Lionello Lunesu wrote:
> Uh.... Making a sudoku solver by any chance??? (me too!)

I've written one already, but it would be interesting to see how the 
ones you two are writing work in comparison.

Stewart.

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/M d- s:- C++@ a->--- UB@ P+ L E@ W++@ N+++ o K-@ w++@ O? M V? PS- 
PE- Y? PGP- t- 5? X? R b DI? D G e++>++++ h-- r-- !y
------END GEEK CODE BLOCK------

My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
December 12, 2005
Re: printf() problems
Stewart Gordon schrieb:

> Lionello Lunesu wrote:
>> Uh.... Making a sudoku solver by any chance??? (me too!)
> 
> I've written one already, but it would be interesting to see how the
> ones you two are writing work in comparison.
> 
> Stewart.
> 
Mee to! Look at www.gasiba.de/D/sudoku.d :)
Would be nice to compare your version and mine in terms of speed / code size, etc...

Best,
Tiago

-- 
Tiago Gasiba (M.Sc.) - http://www.gasiba.de
Everything should be made as simple as possible, but not simpler.
December 12, 2005
Re: printf() problems
Tiago Gasiba schrieb:

> Stewart Gordon schrieb:
> 
>> Lionello Lunesu wrote:
>>> Uh.... Making a sudoku solver by any chance??? (me too!)
>> 
>> I've written one already, but it would be interesting to see how the
>> ones you two are writing work in comparison.
>> 
>> Stewart.
>> 
> Mee to! Look at www.gasiba.de/D/sudoku.d :)
> Would be nice to compare your version and mine in terms of speed / code
> size, etc...
> 
> Best,
> Tiago
> 

The solution implemented by myself was looking too simple - and in fact it is!
Initially I though that this would be the ultimate solution, but I was wrong.
There are very hard Sudoku tables that are damm difficult to solve - even for software.
You can take a look at the following website: http://www.sudokusolver.co.uk/
In particular here: http://www.sudokusolver.co.uk/grids_nologic.html
I'm happy with my code and will not work any further on this.
If someone writes a D program to solve these difficult tables... please let us know.

Best,
Tiago 

-- 
Tiago Gasiba (M.Sc.) - http://www.gasiba.de
Everything should be made as simple as possible, but not simpler.
December 12, 2005
Re: printf() problems
Tiago Gasiba wrote:
<snip>
> The solution implemented by myself was looking too simple - and in fact it is!
> Initially I though that this would be the ultimate solution, but I was wrong.
> There are very hard Sudoku tables that are damm difficult to solve - even for software.
> You can take a look at the following website: http://www.sudokusolver.co.uk/
> In particular here: http://www.sudokusolver.co.uk/grids_nologic.html
> I'm happy with my code and will not work any further on this.
> If someone writes a D program to solve these difficult tables... please let us know.

If it can't be solved by logic, then it isn't a true Sudoku.  But I'll 
take those challenge puzzles home and see how far my program gets with 
solving them.

Stewart.

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/M d- s:- C++@ a->--- UB@ P+ L E@ W++@ N+++ o K-@ w++@ O? M V? PS- 
PE- Y? PGP- t- 5? X? R b DI? D G e++>++++ h-- r-- !y
------END GEEK CODE BLOCK------

My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
December 12, 2005
Re: printf() problems
Stewart Gordon wrote:
> Tiago Gasiba wrote:
> <snip>
> 
>> The solution implemented by myself was looking too simple - and in 
>> fact it is!
>> Initially I though that this would be the ultimate solution, but I was 
>> wrong.
>> There are very hard Sudoku tables that are damm difficult to solve - 
>> even for software.
>> You can take a look at the following website: 
>> http://www.sudokusolver.co.uk/
>> In particular here: http://www.sudokusolver.co.uk/grids_nologic.html
>> I'm happy with my code and will not work any further on this.
>> If someone writes a D program to solve these difficult tables... 
>> please let us know.

What's the price? :) The solution is very easy, just plug a depth-first 
search into your Sodoku solver, or for a more generic puzzle solving 
program, implement it using Dancing Links (Knuth, 2000).

> If it can't be solved by logic, then it isn't a true Sudoku.  But I'll 
> take those challenge puzzles home and see how far my program gets with 
> solving them.

It depends on your definition of logic.
Isn't the following logic:

Assume A
  -> Leads to inconsistency (*)
Therefore !A

(*) may of course be a very long chain of events.

If this is logic, all single solution Sodoku puzzles are solvable by 
logic. (Back-tracking search aka depth first search)

Or is human logic defined to have a limited search depth? :)

/Oskar
December 12, 2005
Re: printf() problems
Oskar Linde schrieb:

> Stewart Gordon wrote:
>> Tiago Gasiba wrote:
>> <snip>
>> 
>>> The solution implemented by myself was looking too simple - and in
>>> fact it is!
>>> Initially I though that this would be the ultimate solution, but I was
>>> wrong.
>>> There are very hard Sudoku tables that are damm difficult to solve -
>>> even for software.
>>> You can take a look at the following website:
>>> http://www.sudokusolver.co.uk/
>>> In particular here: http://www.sudokusolver.co.uk/grids_nologic.html
>>> I'm happy with my code and will not work any further on this.
>>> If someone writes a D program to solve these difficult tables...
>>> please let us know.
> 
> What's the price? :) The solution is very easy, just plug a depth-first
> search into your Sodoku solver, or for a more generic puzzle solving
> program, implement it using Dancing Links (Knuth, 2000).
> 
>> If it can't be solved by logic, then it isn't a true Sudoku.  But I'll
>> take those challenge puzzles home and see how far my program gets with
>> solving them.
> 
> It depends on your definition of logic.
> Isn't the following logic:
> 
> Assume A
>    -> Leads to inconsistency (*)
> Therefore !A
> 
> (*) may of course be a very long chain of events.
> 
> If this is logic, all single solution Sodoku puzzles are solvable by
> logic. (Back-tracking search aka depth first search)
> 
> Or is human logic defined to have a limited search depth? :)
> 
> /Oskar
No. The description in the website says that it can be solved using a "Guess Algorithm", which is what you have just described.
However, logic means (IMHO) that each decision you take is a final decision - i.e. no guessing, no consistency test, etc...
They have software that solves these problems with guessing but not "by logic" :)

Tiago Gasiba

-- 
Tiago Gasiba (M.Sc.) - http://www.gasiba.de
Everything should be made as simple as possible, but not simpler.
December 13, 2005
Sudoku solving (was: printf() problems)
Stewart Gordon wrote:
> Tiago Gasiba wrote:
<snip>
>> http://www.sudokusolver.co.uk/
>> In particular here: http://www.sudokusolver.co.uk/grids_nologic.html
>> I'm happy with my code and will not work any further on this.
>> If someone writes a D program to solve these difficult tables... 
>> please let us know.
> 
> If it can't be solved by logic, then it isn't a true Sudoku.  But I'll 
> take those challenge puzzles home and see how far my program gets with 
> solving them.

What a nuisance!  I saved the page onto my USB drive, but hadn't 
realised that the content is in an invisible iframe and so didn't get 
saved.  So I brought my program here, and at first I thought I'd exposed 
a bug in my solver, but it turns out to be a bug in GDC (which I'll have 
to try and track down) stopping it working on this Mac.

Oh well, BLNT....

Meanwhile, here's my program.

Stewart.

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/M d- s:- C++@ a->--- UB@ P+ L E@ W++@ N+++ o K-@ w++@ O? M V? PS- 
PE- Y? PGP- t- 5? X? R b DI? D G e++>++++ h-- r-- !y
------END GEEK CODE BLOCK------

My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
December 13, 2005
Re: Sudoku solving (was: printf() problems)
Stewart Gordon schrieb:

> 
> Oh well, BLNT....
> 
> Meanwhile, here's my program.
> 
> Stewart.
> 

Didn't manage to get your program to choke.
However, with the initial matrix:
<snip>
.2. ... ...
... 6.. ..3
.74 .8. ...

... ..3 ..2
.8. .4. .1.
6.. 5.. ...

... .1. 78.
5.. ..9 ...
... ... .4.
<snip>

which is one of the "non-logic-solvable" tables in the website, I get the
following answer with your program:

<snip>
.26 ..7 ..8
895 62. .73
.74 .8. ...

457 193 862
983 246 517
612 578 ..4

2.9 .1. 78.
548 7.9 ...
7.1 8.2 .4.
<snip>

and the solution is (according to the website):

<snip>
126 437 958
895 62. 473
374 985 126

457 193 862
983 246 517
612 578 394

2.9 314 785
548 7.9 231
731 852 649
<snip>

Your program preforms very well and also puts mine into shame, because
the result from mine is:
<snip>
- 2 6   - - -   - - -
- - -   6 - -   - - 3
- 7 4   - 8 -   - - -

- - -   - - 3   - - 2
- 8 -   - 4 -   - 1 -
6 - -   5 - -   - - -

- - -   - 1 -   7 8 -
5 - -   - - 9   - - -
- - -   - - -   - 4 -
<snip>

However, notice that before writing the program I didn't know what Sudoku
was and it only took me 2hrs to devise the algorithm and write it down in
D. :)
I have compiled your program with DMD on Linux. Didn't notice any problem
with it. The bug you have must be GDC specific.

Best,
Tiago

-- 
Tiago Gasiba (M.Sc.) - http://www.gasiba.de
Everything should be made as simple as possible, but not simpler.
December 13, 2005
Re: Sudoku solving (was: printf() problems)
Tiago Gasiba schrieb:

> 
> and the solution is (according to the website):
> 
> <snip>
> 126 437 958
> 895 62. 473
> 374 985 126
> 
> 457 193 862
> 983 246 517
> 612 578 394
> 
> 2.9 314 785
> 548 7.9 231
> 731 852 649
> <snip>
> 

Oops... forgot to copy-paste a few numbers
Here it goes the final (complete) and unique solution:

126 437 958
895 621 473
374 985 126

457 193 862
983 246 517
612 578 394

269 314 785
548 769 231
731 852 649


Best,
Tiago 

-- 
Tiago Gasiba (M.Sc.) - http://www.gasiba.de
Everything should be made as simple as possible, but not simpler.
1 2 3
Top | Discussion index | About this forum | D home