One flew over the backdoors

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

bd4 in singles

Postby dobrichev » Mon Apr 15, 2013 7:17 pm

eleven wrote:Mladen, if i saw it right, all your backdoor size 4 puzzles are minimals of this one ...
Code: Select all
12.4..7...5.1......8..3.1.....36..9..91...84....9.8...71.59346..3462.....658...3. # 98896 FNBTHG C33/M4.2047.259


Right. All puzzles have these givens ("1"-"9"), non-givens (".") where the backdoor lies, and "optional givens" ("*") which make them unique but don't participate in the backdoor.
Code: Select all
**.*..7...5.*......8..3.1.....36..9..*1...84....*.*...7*.*****..***2.....*5*...3.

Minimizing this puzzle resulted in total 279 puzzles with 22-26 givens and as expected all they have backdoor 4.
Hidden Text: Show
Code: Select all
000400700050000000080030100000360090001000840000008000700590060034620000065000030   24   4 6.6/1.2/1.2
000400700050000000080030100000360090001000840000008000700593060004620000065000030   24   4 6.6/2.6/2.6
000400700050000000080030100000360090001000840000008000710090060004620000065800030   24   4 6.6/2.3/2.3
000400700050000000080030100000360090001000840000008000710090400004620000065800030   24   4 6.6/2.3/2.3
000400700050000000080030100000360090001000840000008000710500400004620000065800030   24   4 6.6/2.3/2.3
000400700050000000080030100000360090001000840000008000710590060004620000065000030   24   4 6.6/4.4/2.6
000400700050000000080030100000360090001000840000008000710590400004620000065000030   24   4 6.6/2.3/2.3
000400700050000000080030100000360090001000840000900000700590060034620000005800030   24   4 6.6/1.2/1.2
000400700050000000080030100000360090001000840000900000700590460030620000065800030   25   4 7.1/1.2/1.2
000400700050000000080030100000360090001000840000900000700593060004620000005800030   24   4 6.6/1.5/1.5
000400700050000000080030100000360090001000840000900000710000400004620000065800030   23   4 6.6/1.5/1.5
000400700050000000080030100000360090001000840000900000710000400030620000065800030   23   4 6.6/1.2/1.2
000400700050000000080030100000360090001000840000900000710000460004620000005800030   23   4 6.6/1.5/1.5
000400700050000000080030100000360090001000840000900000710090060004620000005800030   23   4 7.2/1.5/1.5
000400700050000000080030100000360090001000840000908000700590060034620000005000030   24   4 6.6/1.2/1.2
000400700050000000080030100000360090001000840000908000700593060004620000005000030   24   4 6.6/2.6/2.6
000400700050000000080030100000360090001000840000908000710590060004620000005000030   24   4 7.2/7.1/2.6
000400700050000000080030100000360090091000840000008000700590060004620000005000030   23   4 7.1/1.2/1.2
000400700050000000080030100000360090091000840000008000700590460030620000065800030   26   4 7.1/1.2/1.2
000400700050000000080030100000360090091000840000008000710090060004620000005800030   24   4 6.6/1.2/1.2
000400700050000000080030100000360090091000840000008000710090400030620000065800030   25   4 6.6/1.2/1.2
000400700050000000080030100000360090091000840000008000710500400030620000065800030   25   4 6.6/1.2/1.2
000400700050000000080030100000360090091000840000008000710500460004620000005800030   25   4 6.6/2.0/2.0
000400700050000000080030100000360090091000840000900000700590060004620000005800030   24   4 7.1/1.5/1.5
000400700050100000080030100000360090001000840000000000700090060034020000065800030   23   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000000000700093060004020000065800030   23   4 6.6/2.3/2.3
000400700050100000080030100000360090001000840000000000710000400004620000065800030   23   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000000000710000460004020000065800030   23   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000000000710090060004020000065800030   23   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000000000710500400034020000065800030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000000000710503400004020000065800030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000008000710500400004620000065000030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000900000700090060034020000005800030   23   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000900000700090460030020000065800030   24   4 7.1/1.2/1.2
000400700050100000080030100000360090001000840000900000700093060004020000005800030   23   4 6.6/2.3/2.3
000400700050100000080030100000360090001000840000900000700590060034620000005000030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000900000700590460030620000065000030   25   4 7.1/1.2/1.2
000400700050100000080030100000360090001000840000900000700593060004620000005000030   24   4 6.6/1.5/1.5
000400700050100000080030100000360090001000840000900000710000460004020000005800030   23   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000900000710000460030020000065800030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000900000710090060004020000005800030   23   4 7.2/1.2/1.2
000400700050100000080030100000360090001000840000900000710500400004020000065000030   23   4 8.3/1.2/1.2
000400700050100000080030100000360090001000840000900000710500400030020000065000030   23   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000900000710500460004620000005000030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000900000710500460034020000005000030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090001000840000900000710590060004020000065000030   24   4 7.1/1.2/1.2
000400700050100000080030100000360090001000840000900000710590060004620000005000030   24   4 7.2/1.2/1.2
000400700050100000080030100000360090001000840000900000710590060034020000005000030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090091000840000000000700090060004020000005800030   22   4 7.1/2.3/2.3
000400700050100000080030100000360090091000840000000000700090460030020000065800030   24   4 7.1/1.2/1.2
000400700050100000080030100000360090091000840000000000710000400030620000065800030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090091000840000000000710000460004020000005800030   23   4 6.6/1.2/1.2
000400700050100000080030100000360090091000840000000000710000460030020000065800030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090091000840000000000710500400004020000065800030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090091000840000000000710500400030020000065800030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090091000840000008000700590460030620000065000030   26   4 7.1/1.2/1.2
000400700050100000080030100000360090091000840000008000710500400004020000065000030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090091000840000008000710500400030020000065000030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090091000840000008000710500460004020000005000030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090091000840000008000710590060004020000005000030   24   4 7.1/1.2/1.2
000400700050100000080030100000360090091000840000900000700590060004620000005000030   24   4 7.1/1.5/1.5
000400700050100000080030100000360090091000840000900000710500460004020000005000030   24   4 6.6/1.2/1.2
000400700050100000080030100000360090091000840000900000710590060004020000005000030   24   4 7.1/1.2/1.2
020000700050100000080030100000360090001000840000000000700000400034620000065800030   23   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000000000700003400004620000065800030   23   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000000000700090400004620000065800030   23   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000000000700590060004620000065800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000000000710000400004620000065800030   23   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000008000700590060004620000065000030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000008000700590400004620000065000030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000900000700000400030620000065800030   23   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000900000700000460034620000005800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000900000700003460004620000005800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000900000700090460004620000005800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000900000700590060004620000005000030   23   4 7.1/1.2/1.2
020000700050100000080030100000360090001000840000900000700590400004620000065000030   24   4 7.1/1.2/1.2
020000700050100000080030100000360090001000840000900000700590400030620000065000030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000900000710000460004620000005800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090001000840000908000700000460030620000005800030   24   4 7.6/1.2/1.2
020000700050100000080030100000360090001000840000908000700590460030620000005000030   25   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000000000700000460034620000005800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000000000700003460004620000005800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000000000700090460004620000005800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000000000700590060004620000005800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000000000710000400004620000005800030   23   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000008000700000400030620000065800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000008000700000460030620000005800030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000008000700590060004620000005000030   24   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000008000700590400030620000065000030   25   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000008000700590460030620000005000030   25   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000008000710590400004620000005000030   25   4 6.6/1.2/1.2
020000700050100000080030100000360090091000840000900000710590400004620000005000030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090001000840000008000700090060034620000065800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090001000840000008000700090400034620000065800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090001000840000008000700093060004620000065800030   25   4 6.6/2.3/2.3
020400700050000000080030100000360090001000840000008000700093400004620000065800030   25   4 6.6/2.3/2.3
020400700050000000080030100000360090001000840000008000700500400034620000065800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090001000840000008000700503400004620000065800030   25   4 6.6/6.6/2.6
020400700050000000080030100000360090001000840000008000700590060004620000065000030   24   4 6.6/4.4/2.6
020400700050000000080030100000360090001000840000008000700590400004620000065000030   24   4 6.6/6.6/2.6
020400700050000000080030100000360090001000840000900000700000400030620000065800030   23   4 6.6/1.2/1.2
020400700050000000080030100000360090001000840000900000700003400004620000065800030   24   4 6.6/6.6/2.6
020400700050000000080030100000360090001000840000900000700090060034620000005800030   24   4 6.6/1.2/1.2
020400700050000000080030100000360090001000840000900000700093060004620000005800030   24   4 6.6/2.3/2.3
020400700050000000080030100000360090001000840000900000700500460034620000005800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090001000840000900000700503460004620000005800030   25   4 6.6/1.5/1.5
020400700050000000080030100000360090001000840000900000700590060004620000005800030   24   4 7.1/1.5/1.5
020400700050000000080030100000360090001000840000900000700590400004620000065800030   25   4 6.6/1.5/1.5
020400700050000000080030100000360090001000840000908000700090460030620000005800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090001000840000908000700500460030620000005800030   25   4 7.6/1.2/1.2
020400700050000000080030100000360090001000840000908000700590060004620000005000030   24   4 7.1/7.1/2.6
020400700050000000080030100000360090001000840000908000710000460030620000005800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090091000840000008000700090060034620000005800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090091000840000008000700090400030620000065800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090091000840000008000700090460030620000005800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090091000840000008000700093060004620000005800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090091000840000008000700500400030620000065800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090091000840000008000700500460030620000005800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090091000840000008000700503460004620000005800030   26   4 6.6/2.0/2.0
020400700050000000080030100000360090091000840000008000710090400004620000005800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090091000840000008000710500400004620000005800030   25   4 6.6/2.0/2.0
020400700050000000080030100000360090091000840000008000710590400004620000005000030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090091000840000900000700000460034620000005800030   25   4 6.6/1.2/1.2
020400700050000000080030100000360090091000840000900000700003460004620000005800030   25   4 6.6/2.0/2.0
020400700050000000080030100000360090091000840000900000710000400004620000005800030   24   4 6.6/1.5/1.5
020400700050000000080030100000360090091000840000908000700000460030620000005800030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000000000700000460034020000065800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000000000700003460004020000065800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000000000700090060004020000065800030   23   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000000000700500400034020000065800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000000000700503400004020000065800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000000000710500400004020000065800030   24   4 7.1/1.2/1.2
020400700050100000080030100000360090001000840000008000700500400034020000065000030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000008000700503400004620000065000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000008000700590060034020000065000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000900000700000460030020000065800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000900000700000460034020000005800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000900000700003460004020000005800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000900000700090060004020000005800030   23   4 7.1/1.2/1.2
020400700050100000080030100000360090001000840000900000700500400030020000065000030   23   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000900000700500460034020000005000030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000900000700503400004020000065000030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000900000700503460004620000005000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000900000700590060004020000065000030   24   4 7.1/1.2/1.2
020400700050100000080030100000360090001000840000900000700590060034020000005000030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090001000840000908000700500460030620000005000030   25   4 7.6/1.2/1.2
020400700050100000080030100000360090091000840000000000700000400030620000065800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000000000700000460030020000065800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000000000700000460034020000005800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000000000700003460004020000005800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000000000700500400030020000065800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000000000710500400004020000005800030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000008000700500400030020000065000030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000008000700500460030620000005000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000008000700500460034020000005000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000008000700503400004020000065000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000008000700503460004020000005000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000008000700590060004020000065000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000008000700590060034020000005000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000008000700593060004020000005000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000008000710500400004020000005000030   24   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000900000700503460004020000005000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000900000700593060004020000005000030   25   4 6.6/1.2/1.2
020400700050100000080030100000360090091000840000900000710500400004020000005000030   24   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000008000700090060034020000065800030   24   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000008000700090400034620000065800030   25   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000008000700500400034020000065800030   24   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000008000700503460004020000065800030   25   4 6.6/6.6/2.6
100400700050000000080030100000360090001000840000008000700590060004020000065800030   24   4 6.7/4.4/2.6
100400700050000000080030100000360090001000840000008000700590060004620000065000030   24   4 6.7/4.4/2.6
100400700050000000080030100000360090001000840000008000700590400034620000065000030   25   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000008000710090060004020000065800030   24   4 6.6/2.3/2.3
100400700050000000080030100000360090001000840000008000710500460004020000065800030   25   4 6.6/2.0/2.0
100400700050000000080030100000360090001000840000008000710503400004020000065800030   25   4 6.6/2.3/2.3
100400700050000000080030100000360090001000840000900000700000400030620000065800030   23   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000900000700000460030020000065800030   23   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000900000700090060034020000065800030   24   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000900000700090060034620000005800030   24   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000900000700500400030020000065800030   23   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000900000700503460004020000065800030   25   4 6.6/4.4/2.6
100400700050000000080030100000360090001000840000900000700590060004020000065800030   24   4 6.7/4.4/2.6
100400700050000000080030100000360090001000840000900000700590060034020000005800030   24   4 6.9/1.2/1.2
100400700050000000080030100000360090001000840000900000700593060004020000005800030   24   4 7.1/2.6/2.6
100400700050000000080030100000360090001000840000900000710000460004020000005800030   23   4 6.6/2.0/2.0
100400700050000000080030100000360090001000840000900000710090060004020000005800030   23   4 7.2/2.3/2.3
100400700050000000080030100000360090001000840000900000710500400004020000065800030   24   4 7.1/2.3/2.3
100400700050000000080030100000360090001000840000908000700590060034020000005000030   24   4 7.2/1.2/1.2
100400700050000000080030100000360090001000840000908000700590400030020000065000030   24   4 6.6/1.2/1.2
100400700050000000080030100000360090001000840000908000710590060004020000065000030   25   4 7.1/3.4/2.6
100400700050000000080030100000360090001000840000908000710590400004020000065000030   25   4 8.3/3.4/2.6
100400700050000000080030100000360090091000840000008000700090060034620000005800030   25   4 6.6/1.2/1.2
100400700050000000080030100000360090091000840000008000700090400030620000065800030   25   4 6.6/1.2/1.2
100400700050000000080030100000360090091000840000008000700090460030020000065800030   25   4 6.6/1.2/1.2
100400700050000000080030100000360090091000840000008000700500400030020000065800030   24   4 6.6/1.2/1.2
100400700050000000080030100000360090091000840000008000700590060004020000005800030   24   4 7.1/1.2/1.2
100400700050000000080030100000360090091000840000008000700590060034020000005000030   24   4 7.2/1.2/1.2
100400700050000000080030100000360090091000840000008000700590400030020000065000030   24   4 6.6/1.2/1.2
100400700050000000080030100000360090091000840000008000710090060004020000005800030   24   4 7.1/1.2/1.2
100400700050000000080030100000360090091000840000008000710500400004020000065800030   25   4 6.6/2.0/2.0
100400700050000000080030100000360090091000840000008000710500460004020000005800030   25   4 6.6/2.0/2.0
100400700050000000080030100000360090091000840000008000710590060004020000065000030   25   4 6.6/1.2/1.2
100400700050000000080030100000360090091000840000008000710590400004020000065000030   25   4 6.6/1.2/1.2
100400700050000000080030100000360090091000840000008000710590460004020000005000030   25   4 6.6/1.2/1.2
100400700050000000080030100000360090091000840000008000710593060004020000005000030   25   4 6.6/1.2/1.2
100400700050000000080030100000360090091000840000900000700590060004020000005800030   24   4 7.1/7.1/2.6
100400700050100000080030100000360090001000840000000000700000400034620000065800030   24   4 6.6/1.2/1.2
100400700050100000080030100000360090001000840000000000700000460034020000065800030   24   4 6.6/1.2/1.2
100400700050100000080030100000360090001000840000000000700090060004020000065800030   23   4 6.6/2.3/2.3
100400700050100000080030100000360090001000840000000000700500400034020000065800030   24   4 6.6/1.2/1.2
100400700050100000080030100000360090001000840000000000700503460004020000065800030   25   4 6.6/6.6/2.6
100400700050100000080030100000360090001000840000008000700500400034620000065000030   25   4 6.6/1.2/1.2
100400700050100000080030100000360090001000840000008000700503460004620000065000030   26   4 6.6/1.5/1.5
100400700050100000080030100000360090001000840000900000700003460004020000065800030   25   4 6.6/2.3/2.3
100400700050100000080030100000360090001000840000900000700500400030020000065000030   23   4 6.6/1.2/1.2
100400700050100000080030100000360090001000840000900000700503460004620000065000030   26   4 6.6/1.5/1.5
100400700050100000080030100000360090001000840000900000700590060004620000065000030   25   4 6.6/1.5/1.5
100400700050100000080030100000360090001000840000900000700590060034020000005000030   24   4 6.6/1.2/1.2
100400700050100000080030100000360090091000840000000000700000400030620000065800030   24   4 6.6/1.2/1.2
100400700050100000080030100000360090091000840000000000700000460030020000065800030   24   4 6.6/1.2/1.2
100400700050100000080030100000360090091000840000000000700003460004020000065800030   25   4 6.6/2.5/2.5
100400700050100000080030100000360090091000840000000000700500400030020000065800030   24   4 6.6/1.2/1.2
100400700050100000080030100000360090091000840000008000700500400030020000065000030   24   4 6.6/1.2/1.2
120000700050000000080030100000360090001000840000008000700090400034620000065800030   25   4 6.6/1.2/1.2
120000700050000000080030100000360090001000840000008000700093400004620000065800030   25   4 6.6/2.3/2.3
120000700050000000080030100000360090001000840000008000700500400034620000065800030   25   4 6.6/1.2/1.2
120000700050000000080030100000360090001000840000008000700503400004620000065800030   25   4 6.6/6.6/2.6
120000700050000000080030100000360090001000840000008000700590060004620000065000030   24   4 6.6/4.4/2.6
120000700050000000080030100000360090001000840000008000700590400004620000065000030   24   4 6.6/6.6/2.6
120000700050000000080030100000360090001000840000008000710090400004620000065800030   25   4 6.6/2.3/2.3
120000700050000000080030100000360090001000840000008000710500400004620000065800030   25   4 6.6/2.3/2.3
120000700050000000080030100000360090001000840000900000700000400030620000065800030   23   4 6.6/1.2/1.2
120000700050000000080030100000360090001000840000900000700000460034620000005800030   24   4 6.6/1.2/1.2
120000700050000000080030100000360090001000840000900000700003400004620000065800030   24   4 6.6/6.6/2.6
120000700050000000080030100000360090001000840000900000700003460004620000005800030   24   4 6.6/6.6/2.6
120000700050000000080030100000360090001000840000900000700590060004620000005800030   24   4 7.1/1.5/1.5
120000700050000000080030100000360090001000840000900000700590400004620000065800030   25   4 6.6/1.5/1.5
120000700050000000080030100000360090001000840000900000710000400004620000065800030   24   4 6.6/1.5/1.5
120000700050000000080030100000360090001000840000900000710000460004620000005800030   24   4 6.6/1.5/1.5
120000700050000000080030100000360090001000840000908000700000460030620000005800030   24   4 7.6/1.2/1.2
120000700050000000080030100000360090001000840000908000700590060004620000005000030   24   4 7.1/7.1/2.6
120000700050000000080030100000360090001000840000908000700590400030620000065000030   25   4 6.6/1.2/1.2
120000700050000000080030100000360090001000840000908000700590460030620000005000030   25   4 7.1/1.2/1.2
120000700050000000080030100000360090091000840000008000700090400030620000065800030   25   4 6.6/1.2/1.2
120000700050000000080030100000360090091000840000008000700090460030620000005800030   25   4 6.6/1.2/1.2
120000700050000000080030100000360090091000840000008000700093460004620000005800030   26   4 6.6/1.2/1.2
120000700050000000080030100000360090091000840000008000700500400030620000065800030   25   4 6.6/1.2/1.2
120000700050000000080030100000360090091000840000008000700500460030620000005800030   25   4 6.6/1.2/1.2
120000700050000000080030100000360090091000840000008000700503460004620000005800030   26   4 6.6/2.0/2.0
120000700050000000080030100000360090091000840000008000700590060004620000005000030   24   4 6.6/1.2/1.2
120000700050000000080030100000360090091000840000008000700590400030620000065000030   25   4 6.6/1.2/1.2
120000700050000000080030100000360090091000840000008000700590460030620000005000030   25   4 7.1/1.2/1.2
120000700050000000080030100000360090091000840000008000710090400004620000005800030   25   4 6.6/1.2/1.2
120000700050000000080030100000360090091000840000008000710500400004620000005800030   25   4 6.6/2.0/2.0
120000700050000000080030100000360090091000840000008000710590400004620000005000030   25   4 6.6/1.2/1.2
120000700050000000080030100000360090091000840000900000710000400004620000005800030   24   4 6.6/1.5/1.5
120400700050000000080030100000360090001000840000008000700093060004020000065800030   25   4 6.6/2.3/2.3
120400700050000000080030100000360090001000840000008000700503400004020000065800030   25   4 6.6/6.6/2.6
120400700050000000080030100000360090001000840000008000700590060034020000065000030   25   4 6.6/1.2/1.2
120400700050000000080030100000360090001000840000008000700590400034020000065000030   25   4 6.6/1.2/1.2
120400700050000000080030100000360090001000840000008000710500400004020000065800030   25   4 8.2/2.3/2.3
120400700050000000080030100000360090001000840000900000700000460034020000005800030   24   4 6.6/1.2/1.2
120400700050000000080030100000360090001000840000900000700003460004020000005800030   24   4 6.6/6.6/2.6
120400700050000000080030100000360090001000840000900000700090060034020000005800030   24   4 6.6/1.2/1.2
120400700050000000080030100000360090001000840000900000700093060004020000005800030   24   4 6.6/2.3/2.3
120400700050000000080030100000360090001000840000900000700503400004020000065800030   25   4 6.6/6.6/2.6
120400700050000000080030100000360090001000840000900000700590060004020000005800030   24   4 7.1/7.1/2.6
120400700050000000080030100000360090001000840000908000700590060004020000065000030   25   4 7.1/7.1/2.6
120400700050000000080030100000360090001000840000908000700593400004020000065000030   26   4 6.6/2.3/2.3
120400700050000000080030100000360090091000840000008000700090060034020000005800030   25   4 6.6/1.2/1.2
120400700050000000080030100000360090091000840000008000700093060004020000005800030   25   4 6.6/1.2/1.2
120400700050000000080030100000360090091000840000008000700500460034020000005800030   26   4 6.6/1.2/1.2
120400700050000000080030100000360090091000840000008000700503460004020000005800030   26   4 6.6/2.0/2.0
120400700050000000080030100000360090091000840000008000700590060004020000065000030   25   4 6.6/1.2/1.2
120400700050000000080030100000360090091000840000008000700593060004020000005000030   25   4 6.6/1.2/1.2
120400700050000000080030100000360090091000840000008000700593400004020000065000030   26   4 6.6/1.2/1.2
120400700050000000080030100000360090091000840000008000710500400004020000005800030   25   4 6.6/2.0/2.0
120400700050000000080030100000360090091000840000008000710590060004020000005000030   25   4 6.6/1.2/1.2
120400700050000000080030100000360090091000840000008000710590400004020000005000030   25   4 6.6/1.2/1.2
120400700050000000080030100000360090091000840000900000710500400004020000005800030   25   4 6.6/2.0/2.0
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

bd4 in singles+locked candidates

Postby dobrichev » Mon Apr 15, 2013 7:21 pm

eleven wrote:I could prove now, that the puzzles also have backdoor size 4 for basics (locked candidates + subsets), but it was not that elegant i wanted.
...
If someone is interested, i can post the grids later.

I am interested. Please do it.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: One flew over the backdoors

Postby dobrichev » Mon Apr 15, 2013 9:10 pm

Hi Denis,
Thank you for the overview of the problem and for the good words addressed to my work.
I have some remarks to your observations which I will present below.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: One flew over the backdoors

Postby dobrichev » Mon Apr 15, 2013 9:52 pm

denis_berthier wrote:... the backdoor size of a puzzle is unrelated to its difficulty wrt to any known solving method not accepting guessing.

This is not quite true.
Firstly, in order to be "not simple", the puzzle needs to have at least backdoor of size 1 in singles, which itself is a relationship.
Next, see this picture (wide screen).
Image
The source puzzles are this release of champagne's collection of hardest which follows Sudoku Explainer's rating. The raw data is
Hidden Text: Show
Code: Select all
   #puz  SR   bd
    631 10.30 1
  46794 10.30 2
    140 10.30 3
    517 10.40 1
  43264 10.40 2
    112 10.40 3
   3863 10.50 1
 252671 10.50 2
    971 10.50 3
   1231 10.60 1
 129679 10.60 2
    863 10.60 3
    238 10.70 1
  32986 10.70 2
    346 10.70 3
    927 10.80 1
  84461 10.80 2
    809 10.80 3
   1381 10.90 1
 100664 10.90 2
    952 10.90 3
    549 11.00 1
  51428 11.00 2
    724 11.00 3
    213 11.10 1
  39994 11.10 2
    769 11.10 3
     75 11.20 1
  13451 11.20 2
    375 11.20 3
     21 11.30 1
   4751 11.30 2
    206 11.30 3
      4 11.40 1
    886 11.40 2
     65 11.40 3
    345 11.50 2
     22 11.50 3
    135 11.60 2
     10 11.60 3
     94 11.70 2
      6 11.70 3
     46 11.80 2
      4 11.80 3
      8 11.90 2

The same counts in more readable tabular form
Code: Select all
      bd1    bd2 bd3
10.3  631  46794 140
10.4  517  43264 112
10.5 3863 252671 971
10.6 1231 129679 863
10.7  238  32986 346
10.8  927  84461 809
10.9 1381 100664 952
11.0  549  51428 724
11.1  213  39994 769
11.2   75  13451 375
11.3   21   4751 206
11.4    4    886  65
11.5    0    345  22
11.6    0    135  10
11.7    0     94   6
11.8    0     46   4
11.9    0      8   0

Excluding the only 8 puzzles with rating 11.9, the samples look sufficiently representative.

denis_berthier wrote:Another vaguely related topic is the depth of T&E necessary to solve any puzzle. Contrary to the backdoor size 2 conjecture, the T&E(2) conjecture has resisted all the newly found hard 9x9 puzzles.
Backdoor size and T&E depth correspond to opposite views of solving:
- backdoor size is the minimum number of values that must be guessed in order to solve a puzzle with Singles only,
- T&E-depth is the minimum depth of T&E that must be used in order to be able to solve a puzzle with Singles only without accepting any guessing (a candidate is accepted as a value iff all the other candidates for the same CSP variable have been proven to be impossible).

Although to me guessing and trial are the same, i.e. choosing one of the (reduced) possibilities, do you mean that choosing the "wrong" candidate leads to shorter or equal (contradiction) path?
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: One flew over the backdoors

Postby denis_berthier » Tue Apr 16, 2013 5:17 am

dobrichev wrote:
denis_berthier wrote:... the backdoor size of a puzzle is unrelated to its difficulty wrt to any known solving method not accepting guessing.
This is not quite true.
Firstly, in order to be "not simple", the puzzle needs to have at least backdoor of size 1 in singles, which itself is a relationship.

Yes, backdoor size 0 is equivalent to solvable by Singles. So, I implicitly excluded this trivial case. You're right to recall it.
One could also mention that having B-backdoor size 0 is equivalent to being solvable by braids, i.e. to be in T&E(1). In my view, hard means not in T&E(1). This is a broader view than usual, but it includes a whole set of puzzles that have never been studied in systematic ways - a large set, but still small in proportion (estimated less than 1 in 30,000,000 minimals)


dobrichev wrote:Next, see this picture (wide screen).

... the illusory power of images.
If you wanted to show a relation (that could only be statistical) between SER and backdoor size, you should first choose a random sample (even if restricted to puzzles with some well defined property). But:
- champagne's collection is assembled from different sources, some of which have many repetitions of the same patterns (and for which we don't even know if backdoors have played any role). It is filtered according to largely undefined criteria. It completely ignores puzzles not in T&E(1) but with medium SER (i.e. between 9.3 and 10.x). In short, it is very interesting to have it, but it has no statistical validity - and I don't think he or anyone else ever claimed the contrary.
- SER includes lots of different kinds of chains and nets with arbitrary jumps in their lengths when SER increases by 0.1; this creates artificial results (I don't know if it plays a role in the present case, but in my last book I showed it has a clear impact on the BpB classification results).

dobrichev wrote:Excluding the only 8 puzzles with rating 11.9, the samples look sufficiently representative.
And excluding all the backdoor size 4 puzzles! If there is any relation between backdoor size and SER, why do no bd4 appear in the collection and why do all the known bd4 have small SER (much smaller than the lower bound of the collection)?


dobrichev wrote:
denis_berthier wrote:Another vaguely related topic is the depth of T&E necessary to solve any puzzle. Contrary to the backdoor size 2 conjecture, the T&E(2) conjecture has resisted all the newly found hard 9x9 puzzles.
Backdoor size and T&E depth correspond to opposite views of solving:
- backdoor size is the minimum number of values that must be guessed in order to solve a puzzle with Singles only,
- T&E-depth is the minimum depth of T&E that must be used in order to be able to solve a puzzle with Singles only without accepting any guessing (a candidate is accepted as a value iff all the other candidates for the same CSP variable have been proven to be impossible
Although to me guessing and trial are the same, i.e. choosing one of the (reduced) possibilities,

Well, what's your definition of T&E ?
I'm referring to my definition of T&E (which you can also find in my books).
People have fought for years about T&E without ever giving a definition of it.
For me, T&E is a well defined procedure, the result of which is totally independent of the order in which you try the candidates (because the Basic Resolution Theory consisting of Singles and Elementary Constraints has the confluence property).


dobrichev wrote:do you mean that choosing the "wrong" candidate leads to shorter or equal (contradiction) path?

No.
In T&E, trying (not choosing) a candidate that leads to a contradiction (via Singles and elementary constraints only) results in its elimination; trying a candidate that leads to no contradiction (even if it leads to a solution) results in nothing (i.e. you keep it as a candidate and you keep trying other candidates).
In guessing, trying the right candidate (i.e. one that leads to a solution) leads to accepting it.
Last edited by denis_berthier on Tue Apr 16, 2013 6:52 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: bd4 in singles

Postby denis_berthier » Tue Apr 16, 2013 6:52 am

dobrichev wrote:All puzzles have these givens ("1"-"9"), non-givens (".") where the backdoor lies, and "optional givens" ("*") which make them unique but don't participate in the backdoor.
Code: Select all
**.*..7...5.*......8..3.1.....36..9..*1...84....*.*...7*.*****..***2.....*5*...3.

Minimizing this puzzle resulted in total 279 puzzles with 22-26 givens and as expected all they have backdoor 4.


Updating the W ratings, 265 of these 279 puzzles are in W3 and the 14 remaining ones are in W4 (which entails that they are relatively easy):
# 14 17 41 42 47 60 63 76 111 185 187 190 196 260, i.e.
Hidden Text: Show
000400700050000000080030100000360090001000840000900000710090060004620000005800030 23 4 7.2/1.5/1.5
000400700050000000080030100000360090001000840000908000710590060004620000005000030 24 4 7.2/7.1/2.6
000400700050100000080030100000360090001000840000900000710090060004020000005800030 23 4 7.2/1.2/1.2
000400700050100000080030100000360090001000840000900000710500400004020000065000030 23 4 8.3/1.2/1.2
000400700050100000080030100000360090001000840000900000710590060004620000005000030 24 4 7.2/1.2/1.2
000400700050100000080030100000360090091000840000008000710590060004020000005000030 24 4 7.1/1.2/1.2
000400700050100000080030100000360090091000840000900000710590060004020000005000030 24 4 7.1/1.2/1.2
020000700050100000080030100000360090001000840000900000700590400004620000065000030 24 4 7.1/1.2/1.2
020400700050000000080030100000360090001000840000908000700590060004620000005000030 24 4 7.1/7.1/2.6
100400700050000000080030100000360090001000840000900000710090060004020000005800030 23 4 7.2/2.3/2.3
100400700050000000080030100000360090001000840000908000700590060034020000005000030 24 4 7.2/1.2/1.2
100400700050000000080030100000360090001000840000908000710590400004020000065000030 25 4 8.3/3.4/2.6
100400700050000000080030100000360090091000840000008000700590060034020000005000030 24 4 7.2/1.2/1.2
120400700050000000080030100000360090001000840000008000710500400004020000065800030 25 4 8.2/2.3/2.3
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

T&E

Postby dobrichev » Tue Apr 16, 2013 8:10 am

Hi,
denis_berthier wrote:- T&E-depth is the minimum depth of T&E that must be used in order to be able to solve a puzzle with Singles only without accepting any guessing (a candidate is accepted as a value iff all the other candidates for the same CSP variable have been proven to be impossible

denis_berthier wrote:In T&E, trying (not choosing) a candidate that leads to a contradiction (via Singles and elementary constraints only) results in its elimination; trying a candidate that leads to no contradiction (even if it leads to a solution) results in nothing (i.e. you keep it as a candidate and you keep trying other candidates).

In this context, what is the method you use to check whether some set of givens is a valid subgrid i.e. can be completed to one or more valid solution grids? Everything but T&E?

denis_berthier wrote:
dobrichev wrote:do you mean that choosing the "wrong" candidate leads to shorter or equal (contradiction) path?

No.

Could you provide an example where T&E depth is less than the backdoor size, and that is not due to the fact that all contradicting paths have less depth (are shorter) than the right path?
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: T&E

Postby denis_berthier » Tue Apr 16, 2013 8:38 am

dobrichev wrote:
denis_berthier wrote:- T&E-depth is the minimum depth of T&E that must be used in order to be able to solve a puzzle with Singles only without accepting any guessing (a candidate is accepted as a value iff all the other candidates for the same CSP variable have been proven to be impossible

denis_berthier wrote:In T&E, trying (not choosing) a candidate that leads to a contradiction (via Singles and elementary constraints only) results in its elimination; trying a candidate that leads to no contradiction (even if it leads to a solution) results in nothing (i.e. you keep it as a candidate and you keep trying other candidates).

In this context, what is the method you use to check whether some set of givens is a valid subgrid i.e. can be completed to one or more valid solution grids? Everything but T&E?

I think you may be confusing T&E and DFS (depth-first search).
DFS is a different procedure; it accepts guessing; it is guaranteed to find all the solutions (if any and if you don't stop it when you have found enough). DFS can obviously do what you want here.
All the fast solvers use DFS.


dobrichev wrote:
denis_berthier wrote:
dobrichev wrote:do you mean that choosing the "wrong" candidate leads to shorter or equal (contradiction) path?
No.
Could you provide an example where T&E depth is less than the backdoor size

There are lots of such examples, starting from the old ones by gsf. Moreover, all your bd4 puzzles can be solved by whips and have therefore T&E-depth 1, much smaller than 4.


dobrichev wrote:... and that is not due to the fact that all contradicting paths have less depth (are shorter) than the right path

Not sure what you mean. So, my answer may be completely unrelated to what you had in mind.
For all your bd4 puzzles, the "right path" is guessing the 4 right values at the start. If it can be granted any "length", I guess you'd say it is 4 - but for me this is meaningless.
Anyway, if you don't accept guessing, the solution paths are in either W3 or W4. For the 14 in W4, there are eliminations not "shorter than the right path".
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: One flew over the backdoors

Postby eleven » Tue Apr 16, 2013 12:59 pm

Here is my proof, that this 33 clue puzzle (and all it's minimals) has backdoor size 4.
12.4..7...5.1......8..3.1.....36..9..91...84....9.8...71.59346..3462.....658...3.

Hidden Text: Show
Code: Select all
Puzzle and solution
 +-------+-------+-------+   *--------------------------------*
 | 1 2 . | 4 . . | 7 . . |   | 1  2  3  | 4  5  6  | 7  8  9  |
 | . 5 . | 1 . . | . . . |   | 4  5  7  | 1  8  9  | 6  2  3  |
 | . 8 . | . 3 2 | 1 . . |   | 6  8  9  | 7  3  2  | 1  5  4  |
 +-------+-------+-------+   |----------+----------+----------|
 | . . . | 3 6 . | . 9 . |   | 2  7  8  | 3  6  4  | 5  9  1  |
 | . 9 1 | . . . | 8 4 . |   | 3  9  1  | 2  7  5  | 8  4  6  |
 | . . . | 9 . 8 | . . . |   | 5  4  6  | 9  1  8  | 3  7  2  |
 +-------+-------+-------+   |----------+----------+----------|
 | 7 1 . | 5 9 3 | 4 6 . |   | 7  1  2  | 5  9  3  | 4  6  8  |
 | . 3 4 | 6 2 . | . . . |   | 8  3  4  | 6  2  7  | 9  1  5  |
 | . 6 5 | 8 . 1 | . 3 . |   | 9  6  5  | 8  4  1  | 2  3  7  |
 +-------+-------+-------+   *--------------------------------*
Puzzle after basics:
 *------------------------------------------------*
 | 1    2   369   | 4   58  69    | 7   58  369   |
 | 346  5   3679  | 1   78  269   | 36  28  3469  |
 | 46   8   679   | 27  3   2569  | 1   25  469   |
 |----------------+---------------+---------------|
 | 258  47  28    | 3   6   14    | 25  9   17    |
 | 36   9   1     | 27  57  25    | 8   4   36    |
 | 25   47  36    | 9   14  8     | 36  17  25    |
 |----------------+---------------+---------------|
 | 7    1   28    | 5   9   3     | 4   6   28    |
 | 89   3   4     | 6   2   17    | 59  17  58    |
 | 29   6   5     | 8   14  147   | 29  3   17    |
 *------------------------------------------------*
These 3 subpatterns cannot be solved with basics:
Pattern 1, digits 147                           
 *--------------------------------------*       
 | 1  2   3  | 4  5   6    | 7  8   9   |       
 | 4  5   7  | 1  8   9    | 6  2   3   |       
 | 6  8   9  | 7  3   2    | 1  5   4   |       
 |-----------+-------------+------------|       
 | 2  47  8  | 3  6   14   | 5  9   17  |       
 | 3  9   1  | 2  7   5    | 8  4   6   |       
 | 5  47  6  | 9  14  8    | 3  17  2   |       
 |-----------+-------------+------------|       
 | 7  1   2  | 5  9   3    | 4  6   8   |       
 | 8  3   4  | 6  2   17   | 9  17  5   |       
 | 9  6   5  | 8  14  147  | 2  3   17  |       
 *--------------------------------------*       
Pattern 2, digits 2589                        
 *-------------------------------------*
 | 1    2  3   | 4  5  6  | 7   8  9   |
 | 4    5  7   | 1  8  9  | 6   2  3   |
 | 6    8  9   | 7  3  2  | 1   5  4   |
 |-------------+----------+------------|
 | 258  7  28  | 3  6  4  | 25  9  1   |
 | 3    9  1   | 2  7  5  | 8   4  6   |
 | 25   4  6   | 9  1  8  | 3   7  25  |
 |-------------+----------+------------|
 | 7    1  28  | 5  9  3  | 4   6  28  |
 | 89   3  4   | 6  2  7  | 59  1  58  |
 | 29   6  5   | 8  4  1  | 29  3  7   |
 *-------------------------------------*
Pattern 3, digits 25789             
 *----------------------------------------*
 | 1  2  3   | 4   58  6    | 7   58  9   |
 | 4  5  79  | 1   78  29   | 6   28  3   |
 | 6  8  79  | 27  3   259  | 1   25  4   |
 |-----------+--------------+-------------|
 | 2  7  8   | 3   6   4    | 5   9   1   |
 | 3  9  1   | 27  57  25   | 8   4   6   |
 | 5  4  6   | 9   1   8    | 3   7   2   |
 |-----------+--------------+-------------|
 | 7  1  2   | 5   9   3    | 4   6   8   |
 | 8  3  4   | 6   2   7    | 9   1   5   |
 | 9  6  5   | 8   4   1    | 2   3   7   |
 *----------------------------------------*
Note that pattern 1 and 23 have different digits, and no cell in pattern 2 has a common unit with a cell in pattern 3.
So no pattern can be resolved by solving the others. I.e. for each one a backdoor is needed.

Now suppose, 2 backboors could resolve all of the cells in pattern 1 and 2:
Then this grid remains:
 *------------------------------------------------*
 | 1    2   369   | 4   58  69    | 7   58  369   |
 | 346  5   3679  | 1   78  269   | 36  28  3469  |
 | 46   8   679   | 27  3   2569  | 1   25  469   |
 |----------------+---------------+---------------|
 | 2    7   8     | 3   6   4     | 5   9   1     |
 | 36   9   1     | 27  57  25    | 8   4   36    |
 | 5    4   36    | 9   1   8     | 36  7   2     |
 |----------------+---------------+---------------|
 | 7    1   2     | 5   9   3     | 4   6   8     |
 | 8    3   4     | 6   2   7     | 9   1   5     |
 | 9    6   5     | 8   4   1     | 2   3   7     |
 *------------------------------------------------*
Now, when setting a backdoor cell of pattern 3, we end up with one of these patterns, depending on, if the backdoor solves r3c3 or r2c6 - both is not possible, when using basics only.
Pattern 4a
 *----------------------------------------*
 | 1    2  36  | 4  5  69  | 7   8  369   |
 | 346  5  7   | 1  8 *69  | 36  2  3469  |
 | 46   8  9   | 7  3  2   | 1   5  46    |
 |-------------+-----------+--------------|
 | 2    7  8   | 3  6  4   | 5   9  1     |
 | 36   9  1   | 2  7  5   | 8   4  36    |
 | 5    4  36  | 9  1  8   | 36  7  2     |
 |-------------+-----------+--------------|
 | 7    1  2   | 5  9  3   | 4   6  8     |
 | 8    3  4   | 6  2  7   | 9   1  5     |
 | 9    6  5   | 8  4  1   | 2   3  7     |
 *----------------------------------------*
Pattern 4b
 *--------------------------------------*
 | 1    2  39  | 4  5  6  | 7   8  39   |
 | 346  5  7   | 1  8  9  | 36  2  346  |
 | 46   8 *69  | 7  3  2  | 1   5  469  |
 |-------------+----------+-------------|
 | 2    7  8   | 3  6  4  | 5   9  1    |
 | 36   9  1   | 2  7  5  | 8   4  36   |
 | 5    4  36  | 9  1  8  | 36  7  2    |
 |-------------+----------+-------------|
 | 7    1  2   | 5  9  3  | 4   6  8    |
 | 8    3  4   | 6  2  7  | 9   1  5    |
 | 9    6  5   | 8  4  1  | 2   3  7    |
 *--------------------------------------*

Since this is the best we can achieve (additional candidates only could make it worse), 4 backdoors are needed.


Backdoors and T&E are indeed very different.
As i understood it (without having checked it with Denis' definitions), T&E(1) corresponds to solving with singles chains, i.e. you can try each candidate - put it in - then solve all singles, and eliminate the candidate, if a contradiction arises (e.g. empty cell, missing digit for a unit). A puzzle is not solvable with singles chains, if you arrive at a grid, where no candidate can be eliminated that way.
T&E(2) then corresponds to nested singles chains (of depth 2), i.e. when you are stuck with the singles chain for a candidate, you can copy the grid, try to eliminate each candidate with singles chains - if so, eliminate it from the original grid (with the candidate tried), and then look if it leads to a contradiction there now. If so, you can eliminate the original candidate. If no progress can be achieved any more this way in the original puzzle, the candidate cannot be eliminated. Of course this is a very strong, but also elaborate method.
If a puzzle is not unique, this cannot be found with T&E - when no candidate can be eliminated, you don't know, if it has multiple solutions or the method is too weak.

If a solution is accepted, when it "happens" from trying a candidate, is a matter of taste. A solution is a solution. So it sounds strange, when in using T&E the solution is an Error :) But of course then T&E and pure guessing would be mixed.
I think that gsf's opinion, that (otherwise) extremely hard puzzles should be rated easier, if they have a single backdoor, has to be accepted (though i think different).
On the other side many solvers don't want to allow any T&E based solutions, only "pattern based" ones, where "pattern" refers to a predefined set of more or less easy-to-spot situations. What this set contains, differs between players, but those who allow chains too, are in a minority.

Denis, since you are the only one, who has a larger set of unbiased generated random puzzles, you could check there, if there is any relevant correlation between number of backdoors and difficulty. So far we only can say that extremely hard puzzles tend to have more backdoors, but on the other hand there are many relatively easy puzzles with 2 or more backdoors.
eleven
 
Posts: 1537
Joined: 10 February 2008

Re: One flew over the backdoors

Postby denis_berthier » Tue Apr 16, 2013 2:08 pm

eleven wrote:Denis, since you are the only one, who has a larger set of unbiased generated random puzzles, you could check there, if there is any relevant correlation between number of backdoors and difficulty.

Not unbiased, only with controlled-bias, but as they are uncorrelated, it's as good for most purposes.
I can do the computations, but is there any available program for computing backdoor size?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: One flew over the backdoors

Postby eleven » Tue Apr 16, 2013 2:37 pm

I remember, you had troubles running gsf's program ?

If you can run it, the command line for singles backdoors is
sudoku -qFN inputfile [> outputfile]
(-q1 should do the same)
The number after 'M' in each line is the backdoor size.
But it's rather slow, you have to try, if it can do it in reasonable time.
eleven
 
Posts: 1537
Joined: 10 February 2008

Re: One flew over the backdoors

Postby denis_berthier » Tue Apr 16, 2013 3:20 pm

eleven wrote:I remember, you had troubles running gsf's program ?

If you can run it, the command line for singles backdoors is
sudoku -qFN inputfile [> outputfile]
(-q1 should do the same)
The number after 'M' in each line is the backdoor size.
But it's rather slow, you have to try, if it can do it in reasonable time.


I'm not familiar with gsf's program, but I think I've already used it.
I found on my Mac an old version "sudoku-darwin.i386". Not sure it can work with the 64 bit OS.

A line in my input file of puzzles looks like this (puzzle extra_info):
...456..9..6.......891..45.2.........7..9.....35......397...5.......4.72.....5361 126732

Running ./sudoku-darwin.i386 -qFN all-puzzles.txt >all-backdoor-sizes.txt gives an error message per line:
sudoku: all-puzzles:1: invalid cell [16]=2
sudoku: all-puzzles:2: invalid cell [19]=3
sudoku: all-puzzles:2: invalid cell [42]=2
sudoku: all-puzzles:2: invalid cell [75]=3
sudoku: all-puzzles:2: invalid cell [97]=9
...
As far as I can remember, the extra info should not be a problem (or is it one?)

Instead of the expected result, it outputs:
...456..9..6.......891..45.2.........7..9.....35......397...5.......4.72.....5361 # 14 FN C26.m

Are you sure of the command line ?

If I can make it work, I'll first try on a subset of the 5,926,343 puzzles. Depending on computation time and results, I'll see if it's worth using the whole collection.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: One flew over the backdoors

Postby eleven » Tue Apr 16, 2013 3:41 pm

Hm, i get a similar result for your line. It seems that extra information in the line is only accepted here, when it is seperated with a '#'.
For puzzles with backdoor size 0 this is not reported with an 'M'.
I use "cut -b-82 file > newfile" to get rid of the extra information under linux.
eleven
 
Posts: 1537
Joined: 10 February 2008

Re: One flew over the backdoors

Postby denis_berthier » Tue Apr 16, 2013 3:57 pm

eleven wrote:Hm, i get a similar result for your line. It seems that extra information in the line is only accepted here, when it is seperated with a '#'.
For puzzles with backdoor size 0 this is not reported with an 'M'.
I use "cut -b-82 file > newfile" to get rid of the extra information under linux.


cut works, I get no more error message. But still not the expected results in the output file:

...456..9..6.......891..45.2.........7..9.....35......397...5.......4.72.....5361 # 14 FN C26.m
..34......5...912.7...2.....1.5.7..86...9...7.......34..2.............9.9...61.75 # 90139 FNG C24.m/M1.28.1
.23..6.8......91...8.1..4..2.......7...8.....678.1......7.3.2...3...4.7....5.1.6. # 90061 FNG C25.m/M1.17.6
..3.........78.1....9.234..2.4..5..83..6...14.6.....7.5....7..66...4...........37 # 12 FN C25.m


It seems backdoor size is not computed.
Ideally, I'd like to have no information other than backdoor size.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: One flew over the backdoors

Postby eleven » Tue Apr 16, 2013 4:32 pm

Lines 2 and 3 have backdoor size 1 ("M1").
I needed some time to find in gsf's manual, how to output the backdoor size alone:
-qFN -f'%v %#bM'
If you want it in another format, you can add printing characters:
-qFN -f'%v backdoor size:%#bM'
[Added:] You maybe don't need the puzzle: -qFN -f'%#bM'
eleven
 
Posts: 1537
Joined: 10 February 2008

PreviousNext

Return to General