The New Sudoku Players' Forum

[Jo88]

ps:

I mean this puzzle :

--- --- ---
--- --3 -85
--1 -2- ---

--- 5-7 ---
--4 --- 1--
-9- --- ---

5-- --- -73
--2 -1- ---
--- -4- --9

[SHuisman]

--- --- ---
--- --3 -85
--1 -2- ---

--- 5-7 ---
--4 --- 1--
-9- --- ---

5-- --- -73
--2 -1- ---
--- -4- --9

That thing is MEAN, it starts with 987654321. So it will find the solution on the very END of the loop! It took me 9603 seconds, in visual basic on a 1 GHz laptop.

I was looking at the following code:

Code: Select all

L = 1
FOR I = 1 TO 20
IF A(P) = A(C(P, I)) THEN
L = 0
EXIT FOR
END IF
NEXT I
IF L = 0 THEN GOTO NLGL

If did not use the L at all, it is a wasted of time since you could do this:

Code: Select all

FOR I = 1 TO 20
IF A(P) = A(C(P, I)) THEN GOTO NLGL
NEXT I


It saves quite some time, because if an contraint is 'fullfilled' it will goto nlgl directly, it won't finish the 1 to 20 loop and THEN goto nlgl BUT you have to watch out with the 'return'

[oysterkite]

After I posted that "mean" puzzle I'm glad you used Paul's alogorithm to solve it. I guess a few others have played the puzzle but you are the first to point out the solution has a top row of 987654321 and therefore really puts the CPU to work for "brute-force" type solvers.

(Thats 33 days after I posted the puzzle).

Nevertheless, Pauls algorithm tackles the puzzle correctly. Thanks for posting the solution time/ processor speed which I have not done myself.

BTW, I believe the lines you point out are already quite efficient. If the constraint is "fulfilled" then the commands "L=0" and "EXIT FOR" are processed. The "EXIT FOR" knocks execution out of the 1-20 loop.

[gsf]

After I posted that "mean" puzzle I'm glad you used Paul's alogorithm to solve it. I guess a few others have played the puzzle but you are the first to point out the solution has a top row of 987654321 and therefore really puts the CPU to work for "brute-force" type solvers.

pj's early post of code was great
but there has been some progress since that posting
9K seconds for a 9x9 sudoku today is stupid force, not brute force
why dwell on an implementation that is at least 6 orders of magnitude slower
than any of the solvers posted on the programmer's forum?

[oysterkite]

How about if we want to study suduko grids with an unknown number of solutions?

Can you give an example of any other solver (with source code provided) that finds ALL solutions to a Sudoku grid?

[gsf]

How about if we want to study suduko grids with an unknown number of solutions?

Can you give an example of any other solver (with source code provided) that finds ALL solutions to a Sudoku grid?

yes, on the programmer's forum
time to count all solutions for this puzzle with 957263 solutions on a 3.2GHz p4

Code: Select all

536020900008000000000000000600285009000903000800761004000000000004000000201000007


dukosu's (10.3s)
soultalker's dlx modified to count (2.7s)
3 of mine (5.9s 40.9s 0.66s)

[Unk]

Regarding

4...3....
...6..8..
........1
....5..9.
.8.....6.
.7.2.....
...1.27..
5.3....4.
9........

I get to this point

4 5 1 8 3 7 6 2 9
7 3 2 6 1 9 8 5 4
6 9 8 4 2 5 3 7 1

1 46 46 3 5 8 2 9 7
2 8 5 9 7 1 4 6 3
3 7 9 2 6 4 5 1 8

8 46 46 1 9 2 7 3 5
5 1 3 7 8 6 9 4 2
9 2 7 5 4 3 1 8 6

which implies at least 2 solutions exist.

Here's my solver (for PC only). It's fast and free. Download www.eop.mu.edu/lawrence/Sudoku.zip and follow the instructions in README.TXT.

[Pat]

Regarding

Code: Select all

4...3....
...6..8..
........1

....5..9.
.8.....6.
.7.2.....

...1.27..
5.3....4.
9........

I get to this point

Code: Select all

4        5        1        8        3        7        6        2        9
7        3        2        6        1        9        8        5        4
6        9        8        4        2        5        3        7        1

1        46      46      3        5        8        2        9        7
2        8        5        9        7        1        4        6        3
3        7        9        2        6        4        5        1        8

8        46      46      1        9        2        7        3        5
5        1        3        7        8        6        9        4        2
9        2        7        5        4        3        1        8        6

which implies at least 2 solutions exist.

you mis-placed a clue in box6.

the puzzle

Code: Select all

 4 . . | . 3 . | . . .
 . . . | 6 . . | 8 . .
 . . . | . . . | . . 1
-------+-------+------
 . . . | . 5 . | . 9 .
 . 8 . | . . . | 6 . .
 . 7 . | 2 . . | . . .
-------+-------+------
 . . . | 1 . 2 | 7 . .
 5 . 3 | . . . | . 4 .
 9 . . | . . . | . . .

has only one answer.

[Unk]

My error. Never mind.

[m_b_metcalf]

yes, on the programmer's forum
time to count all solutions for this puzzle with 957263 solutions on a 3.2GHz p4

Code: Select all

536020900008000000000000000600285009000903000800761004000000000004000000201000007


dukosu's (10.3s)
soultalker's dlx modified to count (2.7s)
3 of mine (5.9s 40.9s 0.66s)

Mine weighs in at a modest:

brute found 957263 solution(s) in 23.24 seconds.

on a 1.6GHz PC.

Regards,

Mike Metcalf