Modified P.J. Downey Algorithm

Programs which generate, solve, and analyze Sudoku puzzles

Postby Jo88 » Tue Mar 28, 2006 5:14 am

ps:

I mean this puzzle :

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

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

5-- --- -73
--2 -1- ---
--- -4- --9
Jo88
 
Posts: 12
Joined: 22 March 2006

Postby SHuisman » Mon Apr 10, 2006 2:53 pm

--- --- ---
--- --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'
SHuisman
 
Posts: 17
Joined: 23 March 2006

Good work!

Postby oysterkite » Mon Apr 24, 2006 1:12 am

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.
oysterkite
 
Posts: 6
Joined: 06 March 2006

Re: Good work!

Postby gsf » Mon Apr 24, 2006 3:05 am

oysterkite wrote: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?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby oysterkite » Mon Apr 24, 2006 3:28 am

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?
oysterkite
 
Posts: 6
Joined: 06 March 2006

Postby gsf » Mon Apr 24, 2006 5:08 am

oysterkite wrote: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)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Unk » Mon Apr 24, 2006 1:37 pm

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.
Unk
 
Posts: 4
Joined: 21 April 2006

only one answer

Postby Pat » Mon Apr 24, 2006 1:52 pm

Unk wrote: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.
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Postby Unk » Mon Apr 24, 2006 4:21 pm

My error. Never mind.
Unk
 
Posts: 4
Joined: 21 April 2006

Postby m_b_metcalf » Mon May 15, 2006 6:18 pm

gsf wrote: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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13577
Joined: 15 May 2006
Location: Berlin

Previous

Return to Software