Meet My Nemesis!

Post the puzzle or solving technique that's causing you trouble and someone will help

Re: re: 17 clues

Postby gsf » Wed Mar 19, 2008 10:58 am

ronk wrote:
Pat wrote: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.:D

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

Re: re: 17 clues

Postby gsf » Wed Mar 19, 2008 11:57 am

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
Last edited by gsf on Wed Mar 19, 2008 12:07 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

re: Sudoku Explorer

Postby Pat » Wed Mar 19, 2008 12:59 pm

Adak wrote: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
User avatar
Pat
 
Posts: 3425
Joined: 18 July 2005

Postby Adak » Wed Mar 19, 2008 1:57 pm

@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.
Adak
 
Posts: 10
Joined: 03 March 2008

Re: re: 17 clues

Postby hobiwan » Wed Mar 19, 2008 2:15 pm

gsf wrote: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"?
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Re: re: 17 clues

Postby gsf » Wed Mar 19, 2008 4:42 pm

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

Re: re: 17 clues

Postby hobiwan » Wed Mar 19, 2008 5:12 pm

gsf, thanks for your detailed explanation.

gsf wrote: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.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby Adak » Sat Mar 22, 2008 6:14 am

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!:D

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.
Adak
 
Posts: 10
Joined: 03 March 2008

on the computer, brute force is faster than logic

Postby Pat » Sun Mar 23, 2008 12:32 pm

Adak wrote: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)
User avatar
Pat
 
Posts: 3425
Joined: 18 July 2005

Re: re: 17 clues

Postby daj95376 » Sun Mar 23, 2008 4:34 pm

gsf wrote: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:!:
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Pat » Sun Mar 23, 2008 5:33 pm

daj95376 wrote: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
User avatar
Pat
 
Posts: 3425
Joined: 18 July 2005

Re: on the computer, brute force is faster than logic

Postby Adak » Sun Mar 23, 2008 6:21 pm

Pat wrote:
Adak wrote: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).
Adak
 
Posts: 10
Joined: 03 March 2008

Postby daj95376 » Sun Mar 23, 2008 6:27 pm

Pat wrote:the puzzle as shown
is not there --
but an equivalent puzzle is

Thanks for the clarification Pat:!:
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Mike Barker » Sun Mar 23, 2008 11:21 pm

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.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby gsf » Mon Mar 24, 2008 3:20 pm

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

PreviousNext

Return to Help with puzzles and solving techniques