Modified P.J. Downey Algorithm

Programs which generate, solve, and analyze Sudoku puzzles
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

--- --- ---
--- --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 = 1FOR I = 1 TO 20IF A(P) = A(C(P, I)) THENL = 0EXIT FOREND IFNEXT IIF 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 20IF A(P) = A(C(P, I)) THEN GOTO NLGLNEXT 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!

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!

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

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

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

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.

Unk

Posts: 4
Joined: 21 April 2006

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        97        3        2        6        1        9        8        5        46        9        8        4        2        5        3        7        11        46      46      3        5        8        2        9        72        8        5        9        7        1        4        6        33        7        9        2        6        4        5        1        88        46      46      1        9        2        7        3        55        1        3        7        8        6        9        4        29        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 . . | . . . | . . . `

Pat

Posts: 3674
Joined: 18 July 2005

My error. Never mind.
Unk

Posts: 4
Joined: 21 April 2006

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

m_b_metcalf
2017 Supporter

Posts: 9376
Joined: 15 May 2006
Location: Berlin

Previous