You are not logged in.
- Index
- » Coder's Corner
- » Suduku solver
Post a reply
Topic review (newest first)
- phrontister
- 2012-04-27 02:20:29
hammana wrote:
In fact it took me 9 hours to solve it, but the same grid rotated 90 degrees is solved in 18 minutes.
In which direction was your rotation?
My computer took 12.75 hours to solve the unrotated version.
I tried to see if the compiled version runs faster, but the .exe file i obtain does not work.
I ran this puzzle in the LibertyBASIC Booster compiler, with the following times:
Unrotated: 115 minutes;
90° clockwise rotation: 89 minutes;
180° rotation: 82 seconds;
90° anticlockwise rotation: 226 seconds
I also tried the puzzle (unrotated) using fqvarfort's solver that I mentioned in post #27, and got these times:
LibertyBASIC: 145 minutes;
LibertyBASIC Booster compiler: 68 minutes
I had a bit of spare time and played around with the idea of incorporating a grid rotation option into my amended version of your program. Here's the result, which seems to work ok, both in LB and the LBB compiler:
Here's the string I used for the puzzle input:
..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9
- phrontister
- 2012-04-15 01:37:22
Hi hammana,
I changed the code in my post #3 to add box borders to your program's output for both the starting grid and the solution.
I also included an error trap to print "No solution" if none found (eg, for puzzles incorrectly entered).
- phrontister
- 2012-04-14 03:16:36
Hi hammana,
Thanks for that Wiki link. I didn't try to follow what they said there because I'm not really into sudokus anymore, but out of curiosity I ran the four 'hardest sudokus' in your program, and it solved them all.
Solution times:
Discrepancy: 282 seconds
golden nugget: 283 seconds
Red_Dwarf: 124 seconds
coloin: 2 seconds
Here is a link to a solver discussion on a JustBasic forum (JustBasic is the freeware version of LibertyBasic).
I ran fqvarfort's solver, and got these times, which are about an eighth of yours:
Discrepancy: 38 seconds
golden nugget: 36 seconds
Red_Dwarf: 16 seconds
coloin: 0.3 seconds
I didn't compare the coding of the two programs, but you might find it interesting.
I also ran purecardmagic's GUI that incorporates fqvarfort's solver. It requires typing the initial puzzle cells into a typical sudoku-style grid, and it works well, but I prefer single-string entry for actions such as copy/pasting puzzles from other software and repeat puzzle entry.
fqvarfort's solver requires hard coding each puzzle into the program, doesn't display the original puzzle and outputs the solution as a string...and so I changed the code like I did yours.
An innovative freeware program I have is SudokuSusser, which is a very strong solver and good tutor. It supports image entry, whereby you can simply copy/paste a puzzle graphic from a website or your computer and run it in SS. Unfortunately it seems to be no longer supported, and it may be difficult to find a download for it.
I tried to see if the compiled version runs faster, but the .exe file i obtain does not work.
What compiler did you use? The only one I found that is specifically for LB is GLBCC - program and docs at lbpp.sourceforge.net/ - but I can't get it to work on my computer (Windows XP).
- hammana
- 2012-04-13 21:16:49
Hi phrontister
http://en.wikipedia.org/wiki/Sudoku_algorithms
The above site discusses the various algorithms to solve Sudoku. I learned that I am using the "Brute Force Algorithm" which is the least elegant one. The site gives the worst case grid to show the disadvantage of this algorithm. In fact it ooks me 9 hours to solve it, but the same grid rotated 90 degrees is solved in 18 minutes. I tried tho see if the compiled version runs faster, but the .exe file i obtain does not work.
- bobbym
- 2012-04-12 17:41:58
Hi phrontister;
Okay, I was just wondering whether you would show the code if you had written it.
- phrontister
- 2012-04-12 14:21:32
Hi Bobby,
Do you mean the generator? The solver is hammana's. Anyway, I haven't written either.
The generator is one written by Henk Westhuis. It's called IntoSudoku, and I own a registered version of the software. It's a solver too, plus being a good teaching aid and worksheet.
When sudokus were all the rage I learnt some of the complex patterns so I could solve the diabolicals, but they bored me after a while and I've now lost interest in them. Scanning, scanning, scanning and more scanning of candidates... 
I haven't done a sudoku for ages.
- bobbym
- 2012-04-12 11:38:35
Hi phrontister;
Is your solver handwritten?
- phrontister
- 2012-04-12 11:17:21
Hi hammana,
I ran my sudoku generator overnight to give it a good amount of time to come up with a more difficult puzzle than the ones I've been testing your solver with, and this was the one it rated as the hardest it found:
6.....9.......7.18.7.5....6..798..3...........9..732..3....2.8.94.7.......6.....3
It took the solver nearly 7 minutes. That is quite a different result from the other tests, none of which went over 20 seconds.
I tested it in your original version and my altered one, with similar results.
I have several freeware solvers, and all of them found the solution pretty much instantaneously. Same with two online solvers I tried it on.
Interesting... 
- bobbym
- 2012-04-12 05:57:55
Ask around someone will provide you with a lot of help.
- anonimnystefy
- 2012-04-12 05:55:54
I will see if the my school has Mathematica or any other useful math package.
- bobbym
- 2012-04-12 05:48:32
Last time I saw it at 49 bucks american. But the prices change and may be different elsewhere. Your professor should know more about it than I do. Most college kids get it for nothing at school and then sort of take it home with them.
- anonimnystefy
- 2012-04-12 05:44:49
How much is it for students?
- bobbym
- 2012-04-12 05:38:07
149 dollars back then. It is much cheaper now, especially for students.
- anonimnystefy
- 2012-04-12 05:37:06
How much did it cost?
- bobbym
- 2012-04-12 05:11:40
Yes, I have it.