Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

Post a reply

Go back

Write your message and submit
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool: | :dizzy :eek :kiss :roflol :rolleyes :shame :down :up :touched :sleep :wave :swear :tongue :what :faint :dunno
Options

Go back

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

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

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.

Board footer

Powered by FluxBB