How regular is to generate sudoku with difficulty 9+ SE?

Everything about Sudoku that doesn't fit in one of the other sections

Postby gsf » Wed Apr 18, 2007 4:30 pm

tarek wrote:This is a line chart of "Move vs. ER" of this puzzle until the singles tail:
IMO, this method would describe the puzzle's difficulty more accurately than just a simple "Hardest step"

agreed that "hardest step" is insufficient
can you explain the numbers on the x-axis
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Wed Apr 18, 2007 5:11 pm

gsf wrote:can you explain the numbers on the x-axis

They represent Moves that resulted in elimination(s) numbered in succession....

You use the term "Next best move"
Ruud uses "Solving rounds" - because you restart after each successful elimination.
Some people use the term step to describe that but others use it to describe a digit final placement.

here are moves 1 & 2 according to Explainer:
Code: Select all
START
+---------------------+---------------------+---------------------+
| 1589   139    2     | 34589  3458   345789| 6      149    1579  |
| 569    7      359   | 1      23456  34569 | 459    8      259   |
| 4      169    1589  | 25689  2568   56789 | 1579   129    3     |
+---------------------+---------------------+---------------------+
| 1268   5      1348  | 3468   9      3468  | 1348   7      1268  |
| 2689   23469  3489  | 7      1      34568 | 34589  23469  25689 |
| 16789  13469  134789| 34568  34568  2     | 134589 13469  15689 |
+---------------------+---------------------+---------------------+
| 3      129    1579  | 25689  2568   15689 | 1789   169    4     |
| 129    8      149   | 23469  7      13469 | 139    5      169   |
| 1579   149    6     | 34589  3458   134589| 2      139    1789  |
+---------------------+---------------------+---------------------+

MOVE 1: Hidden pair ER 3.4
+---------------------+---------------------+---------------------+
| 1589   139    2     | 34589  3458   345789| 6      149    1579  |
| 569    7      359   | 1      23456  34569 | 459    8      259   |
| 4      169    1589  | 25689  2568   56789 | 1579   129    3     |
+---------------------+---------------------+---------------------+
| 1268   5      1348  | 3468   9      3468  | 1348   7      1268  |
| 2689   23469  3489  | 7      1      34568 | 34589  23469  25689 |
| 16789  13469  134789| 34568  34568  2     | 134589 13469  15689 |
+---------------------+---------------------+---------------------+
| 3      129   *57-19 | 25689  2568   15689 | 1789   169    4     |
| 129    8      149   | 23469  7      13469 | 139    5      169   |
|*57-19  149    6     | 34589  3458   134589| 2      139    1789  |
+---------------------+---------------------+---------------------+

MOVE 2:  Hidden pair ER 3.4
+---------------------+---------------------+---------------------+
| 1589   139    2     | 34589  3458   345789| 6      149    1579  |
| 569    7      359   | 1      23456  34569 | 459    8      259   |
| 4      169    1589  | 25689  2568   56789 | 1579   129    3     |
+---------------------+---------------------+---------------------+
| 1268   5      1348  | 3468   9      3468  | 1348   7      1268  |
| 2689   23469  3489  | 7      1      34568 | 34589  23469  25689 |
| 16789  13469  134789| 34568  34568  2     | 134589 13469  15689 |
+---------------------+---------------------+---------------------+
| 3      129    57    | 25689  2568   15689 |*78-19  169    4     |
| 129    8      149   | 23469  7      13469 | 139    5      169   |
| 57     149    6     | 34589  3458   134589| 2      139   *78-19 |
+---------------------+---------------------+---------------------+


tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby ravel » Wed Apr 18, 2007 7:08 pm

And then ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Wed Apr 18, 2007 7:18 pm

tarek wrote:
gsf wrote:can you explain the numbers on the x-axis

They represent Moves that resulted in elimination(s) numbered in succession....

You use the term "Next best move"
Ruud uses "Solving rounds" - because you restart after each successful elimination.
Some people use the term step to describe that but others use it to describe a digit final placement.

thanks
in general I use (or think of) move == one placement or elimination
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Wed Apr 18, 2007 7:56 pm

JPF wrote:Like ravel, gsf, AW and others I agree that it's time to think about what we are really looking for in term of rating.
A public program (or at least a common methodology) should be set up accordingly to evaluate quickly these very hard puzzles and to find what we are looking for in them.

I have a catalog of 651 different puzzles from this thread, ~50 waiting SE rating, the remaining 600
had SE already posted -- good news is I started with the hardest first

when SE finishes I'll post it
it will include some stats from the re-worked proposition logic in my solver
along with a description of the stats
those stats might provide some insight into hardness

side note: one of the difficulties in rating is that just about every person with a solver has
at least one killer method that skews the ratings of other solvers -- this is because, by
nature, a hard puzzle is one that folils the basic techniques and forces a solver into
trial and error (for this discussion I consider any technique that makes a proposition
and then tests it for success or failure trial and error, so this includes my proposition
method and any of the forcing chain methods that start with "if this cell has this value then ...")

to avoid this I'm taking a different approach using singles (and now box/line (locked candidates)
with the fall of the singles conjecture) to characterize puzzles
even though a killer technique may solve a particular puzzle, the affect of singles/box/line
on the puzzle may still provide insight into its place in the hardness spectrum

its sort of like using a turing machine to measure complexity
you wouldn't necessarily code a turing machine to solve a real world problem,
but the turing machine equivalent might provide insight into the problem's complexity
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Wed Apr 25, 2007 6:55 am

I held off posting the latest hardest with ER (and new -q1 from my solver) ratings
because for the longest time I couldn't factor out isomorphisms from the proposition logic
after stepping away from it for a week it became clear that knee-jerk coding optimizations were the culprit
i.e., the more optimizations the more the rating algorithms became susceptable to
differences between isomorphic puzzle permutations

its still not perfect (some differences still surface between isomorphic permutations)
but the differences seem to be under 1%

as with the inferior and superior step counting threads from last year, batching moves
(eliminations and placements) plays a big part in counting steps across equivalent puzzles

the harder puzzles require single propositions to solve
and more recently the hardest puzzles require paired propositions with singles and
box-line (locked candidate) constraints

here is the -q1 rating setup:

first, let the degree of a candidate be the number of choices the candidate is part of
e.g., the degree of a clue (given) is 1, the degree of each candidate in a bivalue cell is 2,
the degree of a candidate at one end of a strong link is 2
the degree of each candidate in a cell with n candidates is at most n, but may
be less depending on the links to each candidate

when singles fail to progress the solution:
1-candidate propositions using singles are attempted for all candidates with degree 2
if that fails to progress the solution then degrees 3 .. 9 are tried in order
stopping at the degree that progresses the solution and restarting with singles

(stepping by degree is the backtrack tree search heuristic that explores the most
constrained paths first with the hopes of early pruning -- without this ordering, counting all
propositions for the hardest puzzles would explode)

if 1-candidate propositions fail to progress the solution:
2-candidate propositions (paired/nested) using singles are attempted for all candidates with degree 2
2x3, 2x4, ..., 3x3, 3x4, ..., 9x9 and so on until paired candidates with degrees d,e progress the solution

if 2-candidate propositions using singles fail to progress the solution:
the whole process is restarted with propositions using singles and box-line constraints
(the hardest of the recent hardest fall to propositions using singles and box-line)

the rating counts singles steps as in the inferior and superior threads, and counts
all proposition constraint iterations, with some extra weight for box-line constraints

constraint iterations counts the number of times the basic constraints (singles box-line)
are reapplied, after an initial candidate placement, to reach steady state
i.e., after a placement the singles constraints may induce more placements, and those more placements, and so on
eventually reapplication of the constraints will either solve the puzzle or stop making new placements

but nobody solves with just singles and box-line!
true, but observing how puzzles react to singles (box-line) with 1 and 2 candidate propositions
precipitates the puzzles into strata that reasonably match the progression of hardness
we've seen in this forum

I've compiled the 651 puzzles in CSV form with a #! schema header so it can be run back through my solver

Code: Select all
#!sudoku -c4,Q1,ER,XR,puzzle,label,Q1time,ERtime,stats


Q1 my solver -q1 rating
ER SE rating
XR dukosu's suexrat rating
puzzle the puzzle
label puzzle label / author / date
Q1time the elapsed time to compute Q1 @ 3.2Ghz
ERtime the elapsed time to compute ER @ 2.0 Ghz one took 10h58m!
stats the constraint stats listed by %#c#/q in my solver
of interest for the hardest are the P (proposition) constraint stats:

P0 number of times propositions were applied
P1 number of moves (placements/eliminations) for all propositions
P2 total number of propositions
P3 total number of proposition solutions
P4 total number of proposition contradictions
P5 total number of proposition constraint iterations
P6 maximum single proposition constraint interation
P7 maximum proposition candidate degree
P8 1: single proposition, 2: nested (paired) proposition

the Q1 rating counts simple steps, P5, and the total number of box-line moves (including
those used by propositions) x 1000
Code: Select all
-R'I0+P5+B*1000'

you can try your own ratings with a -R expression after the -q1 option

the Q is for quick -- ~4min to rate the 651 @ 3.2Ghz
I'm fairly satisfied with the spread
the singles backdoor size 3 (conjecture breakers) puzzles are at the top
there will be disagreement with SE because it weights the single hardest move over all others,
and Q1 takes into account all moves (within the given constraints and proposition logic)

the data file is here
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Wed Apr 25, 2007 9:29 am

Thanks gsf.

At least, your new q1 option is quick:)
Looking at your file with the different ratings, I was wondering about some values.
Example :
Code: Select all
100000002003400050060000700000068040000392000009500000020000100700000006005080030# jpf-04/14/65


SE= 10.6 ; 57m47s
XR = 1074
gsfr = 99821 (old rating)
gsfrq = 22486 (new rating)

Any reasons for these discrepancies ?
Thanks.

JPF
JPF
2017 Supporter
 
Posts: 6139
Joined: 06 December 2005
Location: Paris, France

Postby gsf » Wed Apr 25, 2007 2:16 pm

JPF wrote:Looking at your file with the different ratings, I was wondering about some values.
Example :
Code: Select all
100000002003400050060000700000068040000392000009500000020000100700000006005080030# jpf-04/14/65


SE= 10.6 ; 57m47s
XR = 1074
gsfr = 99821 (old rating)
gsfq = 22486 (new rating)

Any reasons for these discrepancies ?

discrepancies between gsfr and the new gsfq are easy -- the old one needed improvement

use the solver to get some hints
-v2 will list the proposition progress along with all other constraints
-T0x20 (T for test) just lists the proposition progress
Code: Select all
sudoku -q1 -T0x20 100000002003400050060000700000068040000392000009500000020000100700000006005080030
---- subexpression 2 ----
                propositions    163  solutions   0  contradictions   2  iterations    312  girth   5  degree   3  nesting 1
                propositions    205  solutions   0  contradictions   6  iterations    400  girth   5  degree   4  nesting 1
                propositions   8562  solutions   8  contradictions   5  iterations  21766  girth  20  degree   3  nesting 2

one proposition line takes into account all 1 or 2 candidate tuples of the specified max degree
e.g., the first proposition made 163 propositions on all 163 candidate values of degree 3 one by one
the last proposition made 8562 propositions on all candidate pairs with largest candidate degree 3
for rating propositions check every candidate combination for the specified degree even when solutions are found

the puzzle cracks with 2 1-candidate singles propositions and one 2-candidate (nested) proposition
degree is the max degree candidate used in all propositions for the proposition and girth is the max number of
constraint iterations (singles for subexpression 2) for all propositions in the proposition round

compare this with a puzzle with higher Q1 rating
e.g., the hardest one in the list with Q1 rating 99408 had 1,697,341 total constraint iterations
and requires { singles box-line }, as opposed to this example with 22,478 total iterations and just { singles }

if you don't like a particular rating then you can play with -R<expression> on all of the
constraint stat vars and then propose that as an improvement
the defaults for -q1 (listed by --man) are a starting point for discussion
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Wed Apr 25, 2007 5:53 pm

Interesting gsf.....

I used your new -q1 to rate a long list of -qo rated candidates that scored highly.... The results were variable........

The following is a list of all that had a -q1 rating >95000
Puzzle____________________________________________________________________________ qo___ q1___ Sx9_ ER_ Name
900000005040300060002000100080740000000020000000806070100000900030007040005000002 99991 99039 1433 111 ULTRA0300
700000004020600010005000800030910000000050000000203090800000700060009020004000005 99991 98910 1419 111 ULTRA0301
500000003020600010008000900040701000000030000000420070900000500010007020003000008 99992 97548 1446 110 ULTRA0302
700000003090800050002000400060058000000197000000600010400000700050001090003000002 99994 95811 1434 110 ULTRA0303
900000005070300080002000100060480000000020000000076040100000900080004070005000002 99993 95569 1503 110 ULTRA0304
700000009030400060005000200010806000000070000000031080200000700040008030009000005 99992 95471 1213 111 ULTRA0305
300000009010500020007000400060810000000096000000205080400000300020008010009000007 99991 95464 1342 110 ULTRA0306
200000007090800010006000400050380000000049000000501030400000200010003090007000006 99992 95454 1328 110 ULTRA0307
700000004050900080002000600030190000000040000000805010600000700080001050004000002 99992 95394 1521 110 ULTRA0308
100000009070600020004000300050806000000090000000072080300000100020008070009000004 99992 95374 1501 110 ULTRA0309
800000001040500030009000600020705000000010000000430070600000800030007040001000009 99992 95374 1444 108 ULTRA0310
700000008030200040006000900050140000000702000000035010900000700040001030008000006 99993 95339 1582 112 ULTRA0311
600000008030400050009000700010205000000070000000310020700000600040002030008000009 99997 95272 1491 114 ULTRA0312
300000008070500010006000400090201000000040000000970020400000300050002070008000006 99994 95266 1502 108 ULTRA0313
800000005070900020003000100020600000000030000000207040100000800090004070005000003 99996 95260 1355 107 ULTRA0314
700000006010900080002000300050081000000060000000507040300000700080004010006000002 99991 95157 1132 106 ULTRA0315
700000003060400020008000500010906000000070000000208090500000700020009060003000008 99991 95153 0915 107 ULTRA0316
300000009060800050004000100070206000000090000000503020100000300050002060009000004 99991 95135 0998 107 ULTRA0317
200000004090600070001000500080360000000804000000790030500000200070003090004000001 99991 95120 0974 107 ULTRA0318
400000009080200050006000100070538000000020000000790030100000400050003080009000006 99991 95113 1309 107 ULTRA0319
200000005040800030009000100070608000000710000000039060100000200030006040005000009 99991 95099 1041 107 ULTRA0320
700000002090800060005000100030091000000050000000603040100000700060004090002000005 99991 95098 1238 109 ULTRA0321
100000002080400070006000900030574000000308000000090050900000100070005080002000006 99991 95084 1127 110 ULTRA0322
800000007050300090001000600090104000000080000000053020600000800030002050007000001 99884 95077 0974 106 ULTRA0323
900000001040500030002000600080730000000060000000049070600000900030007040001000002 99991 95076 1084 106 ULTRA0324
100000009070800050004000200060307000000689000000500030200000100080003070009000004 99992 95066 0991 106 ULTRA0325
300000007050600080002000900010056000000408000000190040900000300080004050007000002 99992 95061 1328 109 ULTRA0326
900000008020300050004000600070105000000062000000730010600000900050001020008000004 99992 95058 1339 109 ULTRA0327
400000009080200070001000500070608000000040000000701030500000400060003080009000001 99992 95058 0906 106 ULTRA0328
800000009070300060005000400020106000000042000000730010400000800030001070009000005 99994 95055 1296 109 ULTRA0329
700000002080900010006000400030509000000023000000180050400000700010005080002000006 99992 95047 1396 109 ULTRA0330
300000009010200070004000600080570000000090000000810050600000300070005010009000004 99991 95045 1336 109 ULTRA0331
500000004020700060001000800090306000000040000000029030800000500060003020004000001 99992 95044 1351 107 ULTRA0332
300000005090600070004000100070080000000197000000006020100000300060002090005000004 99876 95033 1011 108 ULTRA0333
400000006050900010002000700010300000000751000000009080700000400090008050006000002 99874 95033 1170 108 ULTRA0334
900000001060800020003000400050206000000090000000503070400000900080007060001000003 99992 95032 0750 105 ULTRA0335
300000002080900070005000100060409000000820000000076040100000300070004080002000005 99992 95031 1349 110 ULTRA0336
300000008090200070006000100070904000000010000000720050100000300040005090008000006 99993 95028 1525 110 ULTRA0337
400000001060300020008000500070023000000040000000708090500000400020009060001000008 99991 95021 0994 106 ULTRA0338
200000003060700090004000500080097000000160000000805010500000200090001060003000004 99995 95017 1631 112 ULTRA0339
800000005040200030009000100060704000000010000000630070100000800030007040005000009 99992 95004 1457 110 ULTRA0340

The following however, scored 99990+ in -qo but your new -q1 did not like it at all & scored only 1825 !
Code: Select all
100050000006009000080200400005010000040800003900006000000000058000300940070000302

tarek
Last edited by tarek on Mon Apr 30, 2007 3:22 am, edited 4 times in total.
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby gsf » Wed Apr 25, 2007 6:16 pm

tarek wrote:Interesting gsf.....

I used your new -q1 to rate a long list of -qo rated candidates that scored highly.... The results were variable........

I intended -q1 to be more stable than -qo
tarek wrote:The following however, scored 99990+ in -qo but your new -q1 did not like it at all & scored only 1825 !
Code: Select all
100050000006009000080200400005010000040800003900006000000000058000300940070000302


there are some surprises
but the proposition trace shows why it rates so low
Code: Select all
propositions    917  solutions   4  contradictions   0  iterations   1761  girth  15  degree   2  nesting 2

size 2 propositions (nested), but only degree 2 candidates were needed
i.e., by using only bivalue/bilocation candidates (degree 2), and guessing 2 cells at a time,
the puzzle solves with singles in 917 guesses or less
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Wed Apr 25, 2007 6:40 pm

gsf wrote:.
.
.
but the proposition trace shows why it rates so low
Code: Select all
propositions    917  solutions   4  contradictions   0  iterations   1761  girth  15  degree   2  nesting 2

size 2 propositions (nested), but only degree 2 candidates were needed
i.e., by using only bivalue/bilocation candidates (degree 2), and guessing 2 cells at a time,
the puzzle solves with singles in 917 guesses or less

Thanx, I'll need to look at how this works compared to non-nesting Puzzles (non FNPG according to -qo) that scored 95000+ according to -q1.

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby coloin » Thu Apr 26, 2007 4:49 pm

Thanks gsf for that work-i had got stuck in the SE - now I know why.

As I understand how you have analysed things...

You have a valid 20 clue puzzle, difficult because clues cant be inserted by simple logic - so complixicated logic has to be employed......propositions.

OK so far

Now there are 61 empty spaces in the puzzle - potentially they could have 61*9 different values but only 61 of these will be correct. As yet we dont know what the correct ones are....except we sort of do - because you have shown that in the hardest puzzles you can add 2 [correct] clues and get a non minimal puzzle which cant be solved with just singles. But it can be solved with slightly less simple methods - or with 3 [correct] clues.

Have you thought about analysing the effects of the incorrect clue placements ?

If we look at these 61*8 incorrect clues some will be wrong straight away due to simple constraints - but some almost fill in the grid - but lead to a constraint just before the end.

Here we have a valid puzzle [StrmCkr]
Code: Select all
+---+---+---+
|5..|...|..9|
|.2.|1..|.7.|
|..8|...|3..|
+---+---+---+
|.4.|..2|...|
|...|.5.|...|
|...|7.6|.1.|
+---+---+---+
|..3|...|8..|
|.6.|..4|.2.|
|9..|...|..5|
+---+---+---+
add a wrong clue an 3 at r4c1
+---+---+---+
|5..|...|..9|
|.2.|1..|.7.|
|..8|...|3..|
+---+---+---+
|34.|..2|...|
|...|.5.|...|
|...|7.6|.1.|
+---+---+---+
|..3|...|8..|
|.6.|..4|.2.|
|9..|...|..5|
+---+---+---+
which fills [or can be filled with the help of a correct 8 at r6c9] out to this stage
+---+---+---+
|534|627|189|
|629|183|574|
|718|945|362|
+---+---+---+
|346|812|957|
|187|459|23.|
|295|736|418|
+---+---+---+
|453|271|896|
|861|594|723|
|972|368|.45|
+---+---+---+
with a constraint in r5c9 and r9c7


So the incorrect poposition clue the 3 at r4c1 gives an invalid puzzle with 59/61 possible clues filled in obeying sudoku rules.

Perhaps this is the worst case scenario.....60/61 cant occur ?

This is what would happen if we proposed that the 3 at r4c1 was correct - and what we would have to do if we felt inclined to solve these puzzles !

C
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Postby gsf » Thu Apr 26, 2007 5:54 pm

coloin wrote:You have a valid 20 clue puzzle, difficult because clues cant be inserted by simple logic - so complixicated logic has to be employed......propositions.

OK so far

Now there are 61 empty spaces in the puzzle - potentially they could have 61*9 different values but only 61 of these will be correct. As yet we dont know what the correct ones are....except we sort of do - because you have shown that in the hardest puzzles you can add 2 [correct] clues and get a non minimal puzzle which cant be solved with just singles. But it can be solved with slightly less simple methods.

Have you thought about analysing the effects of the incorrect clue placements ?

yes, propositions advance the solution by { elimination placement }
for a 1-candidate proposition of degree d -- d candidate value tests are made
a placement results when all but one fail with a contradiction
an elimination results when all fail with a contradiction
depending on the constraints in scope (singles, box-line, ...) some propositions may be inconclusive
coloin wrote:If we look at these 61*8 incorrect clues some will be wrong straight away due to simple constraints - but some almost fill in the grid - but lead to a constraint just before the end.

right, the proposition logic uses the candidate (pencilmark) grid as a first order prune
the rest of the combinatorial explosion is reigned in by ordering the propositions to
use candidates of least degree first (bivalue/bilocation first, and so on ...)
coloin wrote:Here we have a valid puzzle [StrmCkr]
Code: Select all
+---+---+---+
|5..|...|..9|
|.2.|1..|.7.|
|..8|...|3..|
+---+---+---+
|.4.|..2|...|
|...|.5.|...|
|...|7.6|.1.|
+---+---+---+
|..3|...|8..|
|.6.|..4|.2.|
|9..|...|..5|
+---+---+---+
(this is the original puzzle with r4c1 empty)


Does this happen often with our difficult puzzles ?

the hardest puzzles do not yield to any 1-candidate propositions at the start
this means that all 1-candidate propositions are inconclusive for { singles box-line }
for the puzzle above -q1 -v2 shows that the first 1-candidate propositions yield these 8 contradictions
Code: Select all
P8  [17][39]^4 [17][39]^6 [71][93]^1 [71][93]^7

r1c7!=4 r3c9!=4 ...
you can verify this by hand with my solver (I alias sudoku to g for 'graph theory') on the Easter Monster
Code: Select all
$  g -qFN -f%#ph 100000002090400050006000700050903000000070000000850040700000600030009080002000001

   1     478   34578 | 3567   3689   5678  | 3489    369     2
  238     9     378  |   4    12368  12678 |  138     5     368
 23458   248     6   | 1235   12389  1258  |   7     139   3489
---------------------+---------------------+---------------------
 2468     5    1478  |   9    1246     3   |  128   1267    678
234689  12468  13489 |  126     7    1246  |123589  12369  35689
 2369   1267   1379  |   8      5     126  | 1239     4    3679
---------------------+---------------------+---------------------
   7     148   14589 | 1235   12348  12458 |   6     239   3459
  456     3     145  | 12567  1246     9   |  245     8     457
 45689   468     2   | 3567   3468   45678 | 3459    379     1

$  g -qFNB-G 100000002090400050006000700050903000000070000000850040700000600030009080002000001 12=4
14......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1 #     2 no-solution no-solution
$  g -qFNB-G 100000002090400050006000700050903000000070000000850040700000600030009080002000001 12=7
17......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1 #     2 no-solution no-solution
$  g -qFNB-G 100000002090400050006000700050903000000070000000850040700000600030009080002000001 12=8
18......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1 #     2 no-solution no-solution

a contradiction would result in invalid-move or invalid rather than no-solution (meaning inconclusive for the given constraints)

so the very hardest ones like Easter Monster that require many 2-candidate proposition applications
are bad news for backtrack solvers because they render first order forward/back checking using
simple constraints (like singles box-line) useless
and as a rule of thumb throwing more power into the forward/back checking is almost always
counterproductive to the global search
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Thu Apr 26, 2007 6:04 pm

coloin wrote:So the incorrect poposition clue the 3 at r4c1 gives an invalid puzzle with 59/61 possible clues filled in obeying sudoku rules.

Perhaps this is the worst case scenario.....60/61 cant occur ?

This is what would happen if we proposed that the 3 at r4c1 was correct - and what we would have to do if we felt inclined to solve these puzzles !

another follow up to coloin's insight
the -q1 rating mainly mirrors the total number of constraint iterations, conclusive or not
an ultimately invalid proposition like 41=3 that almost fills the grid will use many constraint iterations to get to that point
so puzzles with low proposition/iteration ratio probably have many such candidates (or candidate pairs)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Mon Apr 30, 2007 11:57 pm

Thanks for the explaination - it will be fun to see the sword and jelly count on your top 5.
Code: Select all
+---+---+---+
|534|627|189|
|629|183|574|
|718|945|362|
+---+---+---+
|346|812|957|
|187|459|23.|
|295|736|418|
+---+---+---+
|453|271|896|
|861|594|723|
|972|368|.45|
+---+---+---+

with a constraint in r5c9 and r9c7

So the incorrect poposition clue the 3 at r4c1 gives an invalid puzzle with 79/81 possible clues filled in obeying sudoku rules.

Perhaps this is the worst case scenario.....instinct tells me 80/81 cant occur ?

Im sure it is too simple to suggest that all the "wrong" proposition clues in our hardest puzzle gave the highest count of these almost complete pseudogrids.

C
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

PreviousNext

Return to General