December 12, 2005 Re: printf() problems | ||||
---|---|---|---|---|

| ||||

Posted in reply to john | 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Lionello Lunesu | 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Stewart Gordon | 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Tiago Gasiba | 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Tiago Gasiba | 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Stewart Gordon | 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Oskar Linde | 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) | ||||
---|---|---|---|---|

| ||||

Posted in reply to Stewart Gordon Attachments: | 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) | ||||
---|---|---|---|---|

| ||||

Posted in reply to Stewart Gordon | 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) | ||||
---|---|---|---|---|

| ||||

Posted in reply to Tiago Gasiba | 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. |