For the rainy autumn days to come ;-)

A few years ago there were some discussions and somewhat complicated program concepts here on c.l.f for solving Sudoku puzzles. I wondered if the Forth CLP methods developed for the Hexagon puzzle could be applied to Sudokus as well to improve
performance.

Recently I came across a puzzle that claimed to be particularly difficult to solve using backtracking methods. So it can be used as benchmark. It took about 1s to solve with Prolog on my old laptop, which is quite slow indeed. Can Forth do better?

The puzzle is:
_,_,_, _,_,_, _,_,_,
_,_,_, _,_,3, _,8,5,
_,_,1, _,2,_, _,_,_,

_,_,_, 5,_,7, _,_,_,
_,_,4, _,_,_, 1,_,_,
_,9,_, _,_,_, _,_,_,

5,_,_, _,_,_, _,7,3,
_,_,2, _,1,_, _,_,_,
_,_,_, _,4,_, _,_,9

Another hard one:
8,_,_, _,_,_, _,_,_,
_,_,3, 6,_,_, _,_,_,
_,7,_, _,9,_, 2,_,_,

_,5,_, _,_,7, _,_,_,
_,_,_, _,4,5, 7,_,_,
_,_,_, 1,_,_, _,3,_,

_,_,1, _,_,_, _,6,8,
_,_,8, 5,_,_, _,1,_,
_,9,_, _,_,_, 4,_,_

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Monday, 16 October 2023 at 10:20:16 UTC+2, minforth wrote:

For the rainy autumn days to come ;-)

A few years ago there were some discussions and somewhat complicated program concepts here on c.l.f for solving Sudoku puzzles. I wondered if the Forth CLP methods developed for the Hexagon puzzle could be applied to Sudokus as well to improve

performance.

Recently I came across a puzzle that claimed to be particularly difficult to solve using backtracking methods. So it can be used as benchmark. It took about 1s to solve with Prolog on my old laptop, which is quite slow indeed. Can Forth do better?

It took me 11min 26sec to solve it with my head!, without using backtracking. So Prolog is almost 700 times faster then me ;-)

Peter

The puzzle is:
_,_,_, _,_,_, _,_,_,
_,_,_, _,_,3, _,8,5,
_,_,1, _,2,_, _,_,_,

_,_,_, 5,_,7, _,_,_,
_,_,4, _,_,_, 1,_,_,
_,9,_, _,_,_, _,_,_,

5,_,_, _,_,_, _,7,3,
_,_,2, _,1,_, _,_,_,
_,_,_, _,4,_, _,_,9

Another hard one:
8,_,_, _,_,_, _,_,_,
_,_,3, 6,_,_, _,_,_,
_,7,_, _,9,_, 2,_,_,

_,5,_, _,_,7, _,_,_,
_,_,_, _,4,5, 7,_,_,
_,_,_, 1,_,_, _,3,_,

_,_,1, _,_,_, _,6,8,
_,_,8, 5,_,_, _,1,_,
_,9,_, _,_,_, 4,_,_

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

P Falth schrieb am Montag, 16. Oktober 2023 um 11:01:27 UTC+2:

On Monday, 16 October 2023 at 10:20:16 UTC+2, minforth wrote:

For the rainy autumn days to come ;-)

A few years ago there were some discussions and somewhat complicated program concepts here on c.l.f for solving Sudoku puzzles. I wondered if the Forth CLP methods developed for the Hexagon puzzle could be applied to Sudokus as well to improve

performance.

Recently I came across a puzzle that claimed to be particularly difficult to solve using backtracking methods. So it can be used as benchmark. It took about 1s to solve with Prolog on my old laptop, which is quite slow indeed. Can Forth do better?

It took me 11min 26sec to solve it with my head!, without using backtracking. So Prolog is almost 700 times faster then me ;-)

:-) Congratulations!

I read that the first puzzle had been designed to stress simple backtracking solvers.
Concerning the second puzzle it was said that it is hard for humans.

Personally, I would probably throw my pencil out of the window after some minutes. ;-)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Monday, October 16, 2023 at 11:33:36 AM UTC+2, minforth wrote:

It took me 11min 26sec to solve it with my head!, without using backtracking. So Prolog is almost 700 times faster then me ;-)

:-) Congratulations!

I read that the first puzzle had been designed to stress simple backtracking solvers.
Concerning the second puzzle it was said that it is hard for humans.

I've had a sudoku solver in my repository since 2005 (Version: 1900 01092005 - Robert Spykerman)
https://sourceforge.net/p/forth-4th/code/HEAD/tree/trunk/4th.src/sudoku.4th

It solved the second one in 0s flat:
8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
------+-------+------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
------+-------+------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2

The first one - a tiny delay (let's say a second):

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

Hans Bezemer

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Hans Bezemer schrieb am Montag, 16. Oktober 2023 um 16:16:33 UTC+2:

On Monday, October 16, 2023 at 11:33:36 AM UTC+2, minforth wrote:

It took me 11min 26sec to solve it with my head!, without using backtracking. So Prolog is almost 700 times faster then me ;-)

:-) Congratulations!

I read that the first puzzle had been designed to stress simple backtracking solvers.
Concerning the second puzzle it was said that it is hard for humans.

I've had a sudoku solver in my repository since 2005 (Version: 1900 01092005 - Robert Spykerman)
https://sourceforge.net/p/forth-4th/code/HEAD/tree/trunk/4th.src/sudoku.4th

It solved the second one in 0s flat:
8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
------+-------+------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
------+-------+------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2

The first one - a tiny delay (let's say a second):

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

The first one looks like a synthetic exercise made up only as backtracking benchmark.
Look at the first row. So it is perhaps easier to solve with non-backtracking methods.

The second one perhaps just demonstrates that a computer can hold more variables
in his memory than most human beings in their mind. See https://abcnews.go.com/blogs/headlines/2012/06/can-you-solve-the-hardest-ever-sudoku

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Monday, October 16, 2023 at 4:35:36 PM UTC+2, minforth wrote:

The second one perhaps just demonstrates that a computer can hold more variables
in his memory than most human beings in their mind. See https://abcnews.go.com/blogs/headlines/2012/06/can-you-solve-the-hardest-ever-sudoku

The solvers behavior on that one was more like the second one - instantaneous. But it's an
interesting exercise - as a person you have almost zero "sure" digits. But like I said - not a
challenge for the algorithm.

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

Hans Bezemer

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Monday, October 16, 2023 at 10:20:16 AM UTC+2, minforth wrote:

For the rainy autumn days to come ;-)
Recently I came across a puzzle that claimed to be particularly difficult to solve using backtracking
methods. So it can be used as benchmark. It took about 1s to solve with Prolog on my old laptop,
which is quite slow indeed. Can Forth do better?

One second? How old is that laptop?

AMD Ryzen 7 5800X 8-Core Processor
TICKS-GET uses os time & PROCESSOR-CLOCK 4192MHz

I do not use parallel tricks here (on my Z840 a speedup of 88 times would be expected)

The puzzle is:
_,_,_, _,_,_, _,_,_,
_,_,_, _,_,3, _,8,5,
_,_,1, _,2,_, _,_,_,

_,_,_, 5,_,7, _,_,_,
_,_,4, _,_,_, 1,_,_,
_,9,_, _,_,_, _,_,_,

5,_,_, _,_,_, _,7,3,
_,_,2, _,1,_, _,_,_,
_,_,_, _,4,_, _,_,9

Another hard one:
8,_,_, _,_,_, _,_,_,
_,_,3, 6,_,_, _,_,_,
_,7,_, _,9,_, 2,_,_,

_,5,_, _,_,7, _,_,_,
_,_,_, _,4,5, 7,_,_,
_,_,_, 1,_,_, _,3,_,

_,_,1, _,_,_, _,6,8,
_,_,8, 5,_,_, _,1,_,
_,9,_, _,_,_, 4,_,_

FORTH> speedthem
0.032 milliseconds (originally 4.36 ms for the computer)
0.028 milliseconds (45 minutes human)
0.140 milliseconds (2 hours human)
0.029 milliseconds (2 hours for a human, maybe impossible)
0.003 milliseconds (unknown source)
0.004 milliseconds (Paul Hsieh's example #1)
0.003 milliseconds (Paul Hsieh's example #2)
0.003 milliseconds (Paul Hsieh's example #3)
0.302 milliseconds (A `minimal' Sudoku (thought impossible for humans))
0.006 milliseconds (Ertl #1)
0.014 milliseconds (Ertl #2)
0.432 milliseconds (Ertl #3)
0.002 milliseconds (Ertl #4)
0.004 milliseconds (Ertl #5)
0.015 milliseconds (Ertl #6)
0.002 milliseconds (Ertl #7)
0.009 milliseconds (Ertl #8)
0.006 milliseconds (Rickman ExtraHard)
0.029 milliseconds (Albert van der Horst's Python example)
112.000 milliseconds (Sudoku17.txt line 527)
348.000 milliseconds (Sudoku17.txt line 6361)
0.993 milliseconds (Arto Inkala, unsolvable to all but the sharpest minds) 5.345 milliseconds (David Filmer, rated above extreme)
16.000 milliseconds (W_a_x_man's challenge)
3.857 milliseconds (minforth's challenge #1)
0.993 milliseconds (minforth's challenge #2) ok

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Marcel Hendrix schrieb am Montag, 16. Oktober 2023 um 21:28:54 UTC+2:

On Monday, October 16, 2023 at 10:20:16 AM UTC+2, minforth wrote:

For the rainy autumn days to come ;-)
Recently I came across a puzzle that claimed to be particularly difficult to solve using backtracking
methods. So it can be used as benchmark. It took about 1s to solve with Prolog on my old laptop,
which is quite slow indeed. Can Forth do better?

One second? How old is that laptop?

Old ?? 22y isn't old here !! ;-)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

minforth schrieb am Montag, 16. Oktober 2023 um 16:35:36 UTC+2:

Hans Bezemer schrieb am Montag, 16. Oktober 2023 um 16:16:33 UTC+2:

On Monday, October 16, 2023 at 11:33:36 AM UTC+2, minforth wrote:

It took me 11min 26sec to solve it with my head!, without using backtracking. So Prolog is almost 700 times faster then me ;-)

:-) Congratulations!

I read that the first puzzle had been designed to stress simple backtracking solvers.
Concerning the second puzzle it was said that it is hard for humans.

I've had a sudoku solver in my repository since 2005 (Version: 1900 01092005 - Robert Spykerman)
https://sourceforge.net/p/forth-4th/code/HEAD/tree/trunk/4th.src/sudoku.4th

It solved the second one in 0s flat:
8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
------+-------+------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
------+-------+------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2

The first one - a tiny delay (let's say a second):

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

The first one looks like a synthetic exercise made up only as backtracking benchmark.
Look at the first row. So it is perhaps easier to solve with non-backtracking methods.

Sudokus can be rotated by n x 90 degrees, rows/columns 1-3 or 4-6 or 7-9 can be swapped, without destroying solvability.

Such symmetries could be used to precondition the matrix for a speedier solver (less backtracking).
Don't ask if it is worth it. ;-) It is only a game.


--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <[email protected]>,
minforth <[email protected]> wrote:

minforth schrieb am Montag, 16. Oktober 2023 um 16:35:36 UTC+2:

Hans Bezemer schrieb am Montag, 16. Oktober 2023 um 16:16:33 UTC+2:

On Monday, October 16, 2023 at 11:33:36 AM UTC+2, minforth wrote:

It took me 11min 26sec to solve it with my head!, without using >backtracking. So Prolog is almost 700 times faster then me ;-)

:-) Congratulations!

I read that the first puzzle had been designed to stress simple >backtracking solvers.
Concerning the second puzzle it was said that it is hard for humans.

I've had a sudoku solver in my repository since 2005 (Version: 1900 >01092005 - Robert Spykerman)
https://sourceforge.net/p/forth-4th/code/HEAD/tree/trunk/4th.src/sudoku.4th

It solved the second one in 0s flat:
8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
------+-------+------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
------+-------+------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2

The first one - a tiny delay (let's say a second):

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

The first one looks like a synthetic exercise made up only as

backtracking benchmark.

Look at the first row. So it is perhaps easier to solve with >non-backtracking methods.

Sudokus can be rotated by n x 90 degrees, rows/columns 1-3 or 4-6 or 7-9 can be
swapped, without destroying solvability.

Such symmetries could be used to precondition the matrix for a speedier >solver (less backtracking).
Don't ask if it is worth it. ;-) It is only a game.

I sort the fields to be probed once in the beginning, on the
remaining possibilities of the content. This order is relevant
throughout.
It is remarkable that the second sudoku is much harder in my book also.
28 ms versus 180 ms on my 4 Ghz AMD system.
(11 versus 75 if I kill mprime that is running on 8 cores.).

It is remarkable that Marcel Hendrix solved the second soduku
substantially faster than the first. Is that an error?

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

none albert schrieb am Mittwoch, 18. Oktober 2023 um 14:37:34 UTC+2:

In article <[email protected]>,
minforth <[email protected]> wrote:

minforth schrieb am Montag, 16. Oktober 2023 um 16:35:36 UTC+2:

Hans Bezemer schrieb am Montag, 16. Oktober 2023 um 16:16:33 UTC+2:

On Monday, October 16, 2023 at 11:33:36 AM UTC+2, minforth wrote:

It took me 11min 26sec to solve it with my head!, without using >backtracking. So Prolog is almost 700 times faster then me ;-)

:-) Congratulations!

I read that the first puzzle had been designed to stress simple >backtracking solvers.
Concerning the second puzzle it was said that it is hard for humans. >> > I've had a sudoku solver in my repository since 2005 (Version: 1900 >01092005 - Robert Spykerman)

https://sourceforge.net/p/forth-4th/code/HEAD/tree/trunk/4th.src/sudoku.4th

It solved the second one in 0s flat:
8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
------+-------+------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
------+-------+------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2

The first one - a tiny delay (let's say a second):

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

The first one looks like a synthetic exercise made up only as >backtracking benchmark.
Look at the first row. So it is perhaps easier to solve with >non-backtracking methods.

Sudokus can be rotated by n x 90 degrees, rows/columns 1-3 or 4-6 or 7-9 can be
swapped, without destroying solvability.

Such symmetries could be used to precondition the matrix for a speedier >solver (less backtracking).
Don't ask if it is worth it. ;-) It is only a game.

I sort the fields to be probed once in the beginning, on the
remaining possibilities of the content. This order is relevant
throughout.
It is remarkable that the second sudoku is much harder in my book also.
28 ms versus 180 ms on my 4 Ghz AMD system.
(11 versus 75 if I kill mprime that is running on 8 cores.).

It is remarkable that Marcel Hendrix solved the second soduku
substantially faster than the first. Is that an error?

The majority of Marcel's timings were in the sub-milliseconds range,
while some puzzles took substantially longer. I wondered if this
"discrepancy" was caused by where in the matrix the algorithm started.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wednesday, October 18, 2023 at 3:27:16 PM UTC+2, minforth wrote:
[..]

The majority of Marcel's timings were in the sub-milliseconds range,
while some puzzles took substantially longer. I wondered if this "discrepancy" was caused by where in the matrix the algorithm started.

A really good deduction.

I changed SOLVER to test for 9 to 1 instead of from 1 to 9 in sudoku_fast

: solver ( -- bool )
findnextmove dup 0< IF DROP morespaces? 0= EXIT THEN
\ #10 1
1 9 DO I OVER try
IF I OVER addnumber
recurse IF DROP TRUE UNLOOP EXIT
ELSE DUP removenumber
ENDIF
ENDIF
\ LOOP
-1 +LOOP DROP FALSE ; PRIVATE

This gave the following substantial differences:

FORTH> speedthem
0.170 milliseconds (originally 4.36 ms for the computer)
0.014 milliseconds (45 minutes human)
0.016 milliseconds (2 hours human)
0.017 milliseconds (2 hours for a human, maybe impossible)
0.002 milliseconds (unknown source)
0.005 milliseconds (Paul Hsieh's example #1)
0.003 milliseconds (Paul Hsieh's example #2)
0.002 milliseconds (Paul Hsieh's example #3)
0.023 milliseconds (A `minimal' Sudoku (thought impossible for humans))
0.003 milliseconds (Ertl #1)
0.002 milliseconds (Ertl #2)
0.289 milliseconds (Ertl #3)
0.002 milliseconds (Ertl #4)
0.007 milliseconds (Ertl #5)
0.020 milliseconds (Ertl #6)
0.003 milliseconds (Ertl #7)
0.009 milliseconds (Ertl #8)
0.006 milliseconds (Rickman ExtraHard)
0.013 milliseconds (Albert van der Horst's Python example)
1.000 milliseconds (Sudoku17.txt line 527)
72.000 milliseconds (Sudoku17.txt line 6361)
0.689 milliseconds (Arto Inkala, unsolvable to all but the sharpest minds) 7.418 milliseconds (David Filmer, rated above extreme)
8.000 milliseconds (W_a_x_man's challenge)
2.079 milliseconds (minforth's challenge #1)
0.689 milliseconds (minforth's challenge #2) ok

It does not really explain explain why challenge #2 is easier
than challenge #1, but a different starting value definitely
makes a difference.
If I had to beat Go, a parallel program (9 threads) might be worth a try.

-marcel

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wednesday, October 18, 2023 at 3:27:16 PM UTC+2, minforth wrote:
[..]

The majority of Marcel's timings were in the sub-milliseconds range,
while some puzzles took substantially longer. I wondered if this "discrepancy" was caused by where in the matrix the algorithm started.

A really good deduction.

I changed SOLVER to test for 9 to 1 instead of from 1 to 9 in sudoku_fast

: solver ( -- bool )
findnextmove dup 0< IF DROP morespaces? 0= EXIT THEN
\ #10 1
1 9 DO I OVER try
IF I OVER addnumber
recurse IF DROP TRUE UNLOOP EXIT
ELSE DUP removenumber
ENDIF
ENDIF
\ LOOP
-1 +LOOP DROP FALSE ; PRIVATE

This gave the following substantial differences:

FORTH> speedthem
0.170 milliseconds (originally 4.36 ms for the computer)
0.014 milliseconds (45 minutes human)
0.016 milliseconds (2 hours human)
0.017 milliseconds (2 hours for a human, maybe impossible)
0.002 milliseconds (unknown source)
0.005 milliseconds (Paul Hsieh's example #1)
0.003 milliseconds (Paul Hsieh's example #2)
0.002 milliseconds (Paul Hsieh's example #3)
0.023 milliseconds (A `minimal' Sudoku (thought impossible for humans))
0.003 milliseconds (Ertl #1)
0.002 milliseconds (Ertl #2)
0.289 milliseconds (Ertl #3)
0.002 milliseconds (Ertl #4)
0.007 milliseconds (Ertl #5)
0.020 milliseconds (Ertl #6)
0.003 milliseconds (Ertl #7)
0.009 milliseconds (Ertl #8)
0.006 milliseconds (Rickman ExtraHard)
0.013 milliseconds (Albert van der Horst's Python example)
1.000 milliseconds (Sudoku17.txt line 527)
72.000 milliseconds (Sudoku17.txt line 6361)
0.689 milliseconds (Arto Inkala, unsolvable to all but the sharpest minds) 7.418 milliseconds (David Filmer, rated above extreme)
8.000 milliseconds (W_a_x_man's challenge)
2.079 milliseconds (minforth's challenge #1)
0.689 milliseconds (minforth's challenge #2) ok

It does not really explain why challenge #2 is easier
than challenge #1, but a different starting value definitely
makes a difference.
If I had to beat Go, a parallel program (9 threads) might be worth a try.

-marcel

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)