The New Sudoku Players' Forum

[gsf]

the big list of 17-clue puzzles has now been updated to include 47621 puzzles

It was 47,693 just a few posts ago. First time for everything, I guess.

there's the counter on Gordon's Sudoku Identification Service that ronk cited
and then there's the list of 17s in one text file that Gordon periodically updates from the id service that Pat cited
the list usually lags the counter which is now at 47698

[gsf]

here are the entries from |G|=47698 (Gordon's sudoku17 with 47698 entries) that require guessing in my solver
(my solver doesn't do { uniqeness ALS } constraints, and all chained constraints propagate naked/hidden singles only)

it took < 4 min @ 3.2GHz to solve the 47698 (~ 65 puzzles/sec/Ghz)
these 9 took ~6 sec total to solve (backdoor stats disabled), or ~ 6.5 puzzles/sec/Ghz
which mainly illustrates the expense of the higher order constraints

000010800090000030200000000400503060701000004000000000050200000008000100000300000 # 2973 90156 FNBXG C17.m/F7.30/N6.33/B2.12.6.1/X1.3/G1.0.2/M1.33.11
000010800090000030200000000400503060701000004000000000050200000008000100000600000 # 2974 90153 FNBXG C17.m/F7.32/N6.31/B2.12.6.1/X1.3/G1.0.2/M1.39.3
350002000010000080000090700400060000000800010030000000600000200700000004000100000 # 30038 90736 FNBTHXYG C17.m/F11.38/N6.28/B2.9.6/T3.11.4/H1.2.1/X3.29/Y2.33/G2.0.2/M1.38.1
600302000010000050000000000702600000000000084300000000080150000000080200000000700 # 35042 90479 FNBTHXYG C17.m/F12.50/N6.24/B4.29.10.1/T2.9.3/H1.2.1/X2.2/Y1.16/G2.0.2/M1.40.2
602050000000003040000000000430008000010000200000000700500270000000000081000600000 # 35409 95161 FNBTHXYKG C17.m/F4.36/N5.30/B4.23.9.1/T1.6.2/H3.6.3/X2.3/Y3.19/K1.3.27.0.0.0.0.1.0.2/G2.0.2/M1.50.1
602050000000004030000000000430008000010000200000000700500270000000000081000600000 # 35410 91033 FNBTHXYKG C17.m/F15.51/N5.19/B5.31.12.2/T1.6.2/H2.4.2/X2.2/Y1.4/K1.1.23.0.0.0.0.0.1/G3.0.3/M1.45.1
000000001000000020003045000000000300010000000260007000000002460008000070100900000 # 40086 90159 FNBYG C17.m/F8.32/N6.28/B2.12.6.1/Y1.9/G1.0.2/M1.29.2
000000000000001002003040050000000340010006000200000070000002008004050000005000006 # 41164 90734 FNBTHYG C17.m/F17.70/N6.26/B5.16.6.1/T2.3.2/H3.6.3/Y3.19/G9.0.4/M1.28.1
000000000000001023004560000000000000007080400010002500000600000020000010300040000 # 41826 95254 FNBWXYKOG C17.m/F5.29/N7.28/B3.6.3/W1.6.0.1/X2.11/Y1.2/K1.1.16.0.0.0.0.1/O1.3/G1.0.2/M1.30.1

[Pat]

I put the puzzle into Sudoku Explorer, which can not find a solution, but gives a message that there are two solutions, before quitting.

Are there more than two solutions to any of the Sudoku 17 puzzles?
Or did the hard puzzle just "bust" Sudoku Explorer?

hi Adak

haven't heard of "Sudoku Explorer"

but all the puzzles in the collection are valid
i.e. exactly one answer

[Adak]

@Pat: thank you, good to know. My program currently doesn't care, but I do want to be able to check the answers I get.

@gsf: Your solver is more advanced than mine, for sure! Although it's written in C, it's not optimized yet. Of the 99 Gordon's puzzles I have, only 89 are solved by it's simple logic functions (in a loop). Total time is now 114 seconds on my P3 @ 900Mhz, with #11 (previously misidentified as #8), taking up a full 22 seconds of that time.

My brute force guesser apparently still has "da dumb", and not "da brain".

One "problem" with it's speed is it prints up a LOT of stuff, as it goes about it's guessing. I like that, but I need to trim it back. It flashes stuff up on the screen so fast, it could be almost mistaken for a Macy's Christmas window display.

[hobiwan]

here are the entries from |G|=47698 (Gordon's sudoku17 with 47698 entries) that require guessing in my solver
(my solver doesn't do uniqeness constraints and all chained constraints propagate naked/hidden singles only)

it took < 4 min @ 3.2GHz to solve the 47698 (~ 65 puzzles/sec/Ghz)
these 9 took ~6 sec total to solve (backdoor stats disabled), or ~ 6.5 puzzles/sec/Ghz
which mainly illustrates the expense of the higher order constraints

000010800090000030200000000400503060701000004000000000050200000008000100000300000 # 2973 90156 FNBXG C17.m/F7.30/N6.33/B2.12.6.1/X1.3/G1.0.2/M1.33.11
000010800090000030200000000400503060701000004000000000050200000008000100000600000 # 2974 90153 FNBXG C17.m/F7.32/N6.31/B2.12.6.1/X1.3/G1.0.2/M1.39.3
350002000010000080000090700400060000000800010030000000600000200700000004000100000 # 30038 90736 FNBTHXYG C17.m/F11.38/N6.28/B2.9.6/T3.11.4/H1.2.1/X3.29/Y2.33/G2.0.2/M1.38.1
600302000010000050000000000702600000000000084300000000080150000000080200000000700 # 35042 90479 FNBTHXYG C17.m/F12.50/N6.24/B4.29.10.1/T2.9.3/H1.2.1/X2.2/Y1.16/G2.0.2/M1.40.2
602050000000003040000000000430008000010000200000000700500270000000000081000600000 # 35409 95161 FNBTHXYKG C17.m/F4.36/N5.30/B4.23.9.1/T1.6.2/H3.6.3/X2.3/Y3.19/K1.3.27.0.0.0.0.1.0.2/G2.0.2/M1.50.1
602050000000004030000000000430008000010000200000000700500270000000000081000600000 # 35410 91033 FNBTHXYKG C17.m/F15.51/N5.19/B5.31.12.2/T1.6.2/H2.4.2/X2.2/Y1.4/K1.1.23.0.0.0.0.0.1/G3.0.3/M1.45.1
000000001000000020003045000000000300010000000260007000000002460008000070100900000 # 40086 90159 FNBYG C17.m/F8.32/N6.28/B2.12.6.1/Y1.9/G1.0.2/M1.29.2
000000000000001002003040050000000340010006000200000070000002008004050000005000006 # 41164 90734 FNBTHYG C17.m/F17.70/N6.26/B5.16.6.1/T2.3.2/H3.6.3/Y3.19/G9.0.4/M1.28.1
000000000000001023004560000000000000007080400010002500000600000020000010300040000 # 41826 95254 FNBWXYKOG C17.m/F5.29/N7.28/B3.6.3/W1.6.0.1/X2.11/Y1.2/K1.1.16.0.0.0.0.1/O1.3/G1.0.2/M1.30.1

My solver solved the first three puzzles with finned fish, ALS and remote pairs only. Do you consider ALS-XY-Wing a "Chained constraint"?

[gsf]

here are the entries from |G|=47698 (Gordon's sudoku17 with 47698 entries) that require guessing in my solver

000010800090000030200000000400503060701000004000000000050200000008000100000300000 # 2973 90156 FNBXG C17.m/F7.30/N6.33/B2.12.6.1/X1.3/G1.0.2/M1.33.11
000010800090000030200000000400503060701000004000000000050200000008000100000600000 # 2974 90153 FNBXG C17.m/F7.32/N6.31/B2.12.6.1/X1.3/G1.0.2/M1.39.3
350002000010000080000090700400060000000800010030000000600000200700000004000100000 # 30038 90736 FNBTHXYG

My solver solved the first three puzzles with finned fish, ALS and remote pairs only. Do you consider ALS-XY-Wing a "Chained constraint"?

I edited the post to include ALS to the constraints/techniques that my solver does not do
the chained constraints are labelled (and documented via --man) XYK in my solver
the first comment field is the puzzle ordinal in sudoku17 -- those will not change thanks to gfroyle
the third field is the label of each constraint used in the solution, G for guess, shows the limits of implemented techniques
if O (pattern overlay) is listed then it would have done finned fish at that point
the fourth field lists puzzle/constraint stats (C17.m: 17 clues minimal, F7.32: 7 nakes singles 32 eliminations, ... G1.*: 1 guess)
my guess is that ALS would change the landscape at the point where my solver constraints dried up here (using the options: -E -f%#ph):

Code: Select all

  5     47    3   | 4679   1    269  |  8    2479  2679
  1     9    467  |  8   24567 24567 | 246    3    2567
  2     8    467  | 4679   3   45679 | 469    1    5679
------------------+------------------+------------------
  4     2     9   |  5     8     3   |  7     6     1
  7     3     1   |  69   269   269  |  5     8     4
  8     6     5   |  1     47    47  | 239    29   239
------------------+------------------+------------------
 369    5     47  |  2    4679   1   | 3469  479    8
 369    47    8   | 4679 45679 45679 |  1   24579  2369
  69    1     2   |  3   45679   8   | 469   4579  679


[hobiwan]

gsf, thanks for your detailed explanation.

my guess is that ALS would change the landscape at the point where my solver constraints dried up here (using the options: -E -f%#ph):

Code: Select all

  5     47    3   | 4679   1    269  |  8    2479  2679
  1     9    467  |  8   24567 24567 | 246    3    2567
  2     8    467  | 4679   3   45679 | 469    1    5679
------------------+------------------+------------------
  4     2     9   |  5     8     3   |  7     6     1
  7     3     1   |  69   269   269  |  5     8     4
  8     6     5   |  1     47    47  | 239    29   239
------------------+------------------+------------------
 369    5     47  |  2    4679   1   | 3469  479    8
 369    47    8   | 4679 45679 45679 |  1   24579  2369
  69    1     2   |  3   45679   8   | 469   4579  679


Exactly.

[Adak]

Although I've been lagging at getting the next solving technique coded up, I did find a notable bottleneck in the brute force function that tests a candidate to see if it would be legal to put it in the grid.

Times for the first 100 of Gordon's 17 file, has now shrunk from 133 seconds to just 33 seconds. on the same 900MHz lappy.

I don't like doing optimizations before all the logic is in play, but this was too sweet to pass up.

And no, I have no idea why I wrote that first version with such a slow algorithm. I plead sickness of course - Sudoku fever!

Update: Compiled the program for speed, and put it on my desktop E6700 @ stock 2.67GHz.

It solved the same first 100 games of Sudoku17 (from Gordon's massive game list of games with 17 givens), in 4.5 seconds!

Since only 3 functions have been optimized, and the logic solvers don't include any fish, or other intermediate or advanced code yet, I'm very pleased.

[Pat]

Since only 3 functions have been optimized, and the logic solvers don't include any fish, or other intermediate or advanced code yet, I'm very pleased.

on the computer,
brute force will be faster than most logic (fish etc)

[daj95376]

here are the entries from |G|=47698 (Gordon's sudoku17 with 47698 entries) that require guessing in my solver
(my solver doesn't do { uniqeness ALS } constraints, and all chained constraints propagate naked/hidden singles only)

it took < 4 min @ 3.2GHz to solve the 47698 (~ 65 puzzles/sec/Ghz)
these 9 took ~6 sec total to solve (backdoor stats disabled), or ~ 6.5 puzzles/sec/Ghz
which mainly illustrates the expense of the higher order constraints

000010800090000030200000000400503060701000004000000000050200000008000100000300000 # 2973 90156 FNBXG C17.m/F7.30/N6.33/B2.12.6.1/X1.3/G1.0.2/M1.33.11
000010800090000030200000000400503060701000004000000000050200000008000100000600000 # 2974 90153 FNBXG C17.m/F7.32/N6.31/B2.12.6.1/X1.3/G1.0.2/M1.39.3
350002000010000080000090700400060000000800010030000000600000200700000004000100000 # 30038 90736 FNBTHXYG C17.m/F11.38/N6.28/B2.9.6/T3.11.4/H1.2.1/X3.29/Y2.33/G2.0.2/M1.38.1
600302000010000050000000000702600000000000084300000000080150000000080200000000700 # 35042 90479 FNBTHXYG C17.m/F12.50/N6.24/B4.29.10.1/T2.9.3/H1.2.1/X2.2/Y1.16/G2.0.2/M1.40.2
602050000000003040000000000430008000010000200000000700500270000000000081000600000 # 35409 95161 FNBTHXYKG C17.m/F4.36/N5.30/B4.23.9.1/T1.6.2/H3.6.3/X2.3/Y3.19/K1.3.27.0.0.0.0.1.0.2/G2.0.2/M1.50.1
602050000000004030000000000430008000010000200000000700500270000000000081000600000 # 35410 91033 FNBTHXYKG C17.m/F15.51/N5.19/B5.31.12.2/T1.6.2/H2.4.2/X2.2/Y1.4/K1.1.23.0.0.0.0.0.1/G3.0.3/M1.45.1
000000001000000020003045000000000300010000000260007000000002460008000070100900000 # 40086 90159 FNBYG C17.m/F8.32/N6.28/B2.12.6.1/Y1.9/G1.0.2/M1.29.2
000000000000001002003040050000000340010006000200000070000002008004050000005000006 # 41164 90734 FNBTHYG C17.m/F17.70/N6.26/B5.16.6.1/T2.3.2/H3.6.3/Y3.19/G9.0.4/M1.28.1
000000000000001023004560000000000000007080400010002500000600000020000010300040000 # 41826 95254 FNBWXYKOG C17.m/F5.29/N7.28/B3.6.3/W1.6.0.1/X2.11/Y1.2/K1.1.16.0.0.0.0.1/O1.3/G1.0.2/M1.30.1

I retrieved 47,621 "17s" from Gordon Royle's web site recently. Your last three entries are not among them. I thought the list of "17s" were being maintained in chronological order

[Pat]

I retrieved 47,621 "17s" from Gordon Royle's web site recently. Your last three entries are not among them. I thought the list of "17s" were being maintained in chronological order

the puzzle as shown
is not there --
but an equivalent puzzle is

e.g.

000000000000001023004560000000000000007080400010002500000600000020000010300040000

is equivalent to #41826

[Adak]

Since only 3 functions have been optimized, and the logic solvers don't include any fish, or other intermediate or advanced code yet, I'm very pleased.

on the computer,
brute force will be faster than most logic (fish etc)

Thanks for the info, Pat.

Although I've made a few big improvements to my brute force solving function, it is still MUCH slower than my logic solving functions.

It's kind of funny because the program has about 8 logic functions (although some are quite small with just one block of code). It looks like this:

Code: Select all

do   {
   RowPossibles();
   ColPossibles();
   BoxPossibles();
   LiftSolos();
   MustBees();
   Locked1();
   Locked2();
   RuleOfPairs();
}while(TotalPossibles is < last loop's TotalPossibles);

In my (almost non-existent) testing, the do loop is run through, on average,  4 to 5 times. Despite this, if these "logic" functions can solve the puzzle,  (they solve about 80% of all puzzles in limited testing (mostly with Gordon's 17 first 100), then the puzzle will be solved in about 0.11 seconds, on average.


I'll have to start a new thread on that and get some opinions on how to improve it, after I get back to making further improvements on the brute force function.

First, I'll be trying the "graph" idea of recognizing basic fish. I can't see writing up a function for every type of fish, when they're so much alike (at least the base fish types).

[daj95376]

the puzzle as shown
is not there --
but an equivalent puzzle is

Thanks for the clarification Pat

[Mike Barker]

Interestingly the results from Glenn's solver will vary depending on which version of the puzzle is used. 41826 is the toughest of the 47621 puzzles I downloaded (with SE rating 9.1). Solved as it is found in Gordon's file the result does not require guessing:

Code: Select all

050600000000000730000100000000070800060000050100000000700040200004030000000500060 #95731 FNBWXYKO C17.m

But when the same puzzle is solved in canonical form it does:

Code: Select all

..............1.23..456...............7.8.4...1...25.....6......2.....1.3...4.... # 95254 FNBWXYKOG C17.m/M1.30.1

I found only 1 puzzle (41826) which could not be solved with grouped nice loops, nrct-chains, or multi-inference nice loops as implemented in my solver; one (41164) which required a multi-inference nice loop (a Kraken blossom); and two (12538 and 21752) which required either a mutant fish or a multi-inference nice loop. In general the 17's seem much easier in general than a random set of puzzles generated by suexg.

[gsf]

Interestingly the results from Glenn's solver will vary depending on which version of the puzzle is used. 41826 is the toughest of the 47621 puzzles I downloaded (with SE rating 9.1).

meet my nemesis (order dependent constraints/methods/techniques)
thanks for pointing this out
after a few tests I think it lies in the K (y-knot ~= singles only contradiction net constraint method)
its really tough to wash out the for(i=0;i<81;i++) and for(j=0;j<9;j++) coding bias