Math Is Fun Forum

hammana

Member

Registered: 2012-03-02

Posts: 48

Re: Suduku solver

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.

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,893

Re: Suduku solver

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

Last edited by phrontister (2012-04-14 21:07:03)

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,893

Re: Suduku solver

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

Last edited by phrontister (2012-04-14 23:49:46)

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,893

Re: Suduku solver

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

Last edited by phrontister (2012-04-26 04:36:05)

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson