Wow, so they do exist ! At least gsf's program confims the singles backdoor size.
Congratulations, it was an old conjecture, that 3 is the maximum.
The puzzles are interesting, full of subsets, that seems to be the trick.
One flew over the backdoors
64 posts
• Page 2 of 5 • 1, 2, 3, 4, 5
Re: The hardest sudokus (new thread)
by eleven » Thu Apr 11, 2013 5:13 pm
- eleven
- Posts: 3173
- Joined: 10 February 2008
Re: backdoors 4 in singles
by denis_berthier » Fri Apr 12, 2013 4:52 am
dobrichev wrote:backdoor of size 4
- Code: Select all
..............1.23.45.2..6............17....852..9.3.1....4.......2.9.5.976.5..3. ED=6.6/1.2/1.2
..............1.23.45.2..6............17....852..96..1....4.......2.9.5.9.6.58.3. ED=6.6/1.2/1.2
..............1.23.45.2..6............17....852..96..1....4.......2.9.5.976.5..3. ED=6.6/1.2/1.2
..............1.23.45.2..6.......6....17....852..9...1....4.......2.9.5.9.6.58.3. ED=6.6/1.2/1.2
..............1.23.45.2..6.......6....17....852..9...1....4.......2.9.5.976.5..3. ED=6.6/1.2/1.2
Very interesting result.
Based on gsf's old list, we already knew that the backdoor size of a puzzle was not related to its difficulty (measured by any of the known ratings excluding guessing). Which is easily understandable, as backdoor size is basically a measure of the difficulty of guessing (e.g. the minimum depth of BFS).
This knowledge is re-inforced by your new findings.
All these puzzles can be solved in the simplest ways:
- either by whips[1] (basic interactions), naked and hidden Pairs, and bivalue-chains (nrc-chains) of length <= 3
- or by whips[1] (basic interactions) and bivalue-chains of length <= 3 (no Subset necessary)
Eleven, I don't understand why having many Subsets could lead to higher backdoor size.
- denis_berthier
- 2010 Supporter
- Posts: 4235
- Joined: 19 June 2007
- Location: Paris
Re: The hardest sudokus (new thread)
by eleven » Fri Apr 12, 2013 5:02 pm
After having given it some thought, this turned out to be a minor observation ...
What is puzzling me, is that gsf's program also reports M4 for -qFNB (singles/boxline), -qFNBTHW (single/boxline/subsets), and -q2 !
So a 3rd party confirmation for that would be appreciated (i for me stopped sudoku programming).
What is puzzling me, is that gsf's program also reports M4 for -qFNB (singles/boxline), -qFNBTHW (single/boxline/subsets), and -q2 !
So a 3rd party confirmation for that would be appreciated (i for me stopped sudoku programming).
- eleven
- Posts: 3173
- Joined: 10 February 2008
Re: The hardest sudokus (new thread)
by tarek » Fri Apr 12, 2013 6:23 pm
I confirm that my program shows a singles backdoor size of 4 in all the puzzles.
I can't confirm the non-singles backdoor size myself but gsf's program is fairly reliable.
Well done
- Code: Select all
..............1.23.45.2..6............17....852..9.3.1....4.......2.9.5.976.5..3.
4
132964785769581423845327169387415692691732548524896371258643917413279856976158234
..............1.23.45.2..6............17....852..96..1....4.......2.9.5.9.6.58.3.
4
132964785769581423845327169387415692691732548524896371258643917413279856976158234
..............1.23.45.2..6............17....852..96..1....4.......2.9.5.976.5..3.
4
132964785769581423845327169387415692691732548524896371258643917413279856976158234
..............1.23.45.2..6.......6....17....852..9...1....4.......2.9.5.9.6.58.3.
4
132964785769581423845327169387415692691732548524896371258643917413279856976158234
..............1.23.45.2..6.......6....17....852..9...1....4.......2.9.5.976.5..3.
4
132964785769581423845327169387415692691732548524896371258643917413279856976158234
I can't confirm the non-singles backdoor size myself but gsf's program is fairly reliable.
Well done
-
tarek - Posts: 3762
- Joined: 05 January 2006
Re: The hardest sudokus (new thread)
by dobrichev » Fri Apr 12, 2013 7:29 pm
Thank you Eleven, Denis, Tarek.
BTW, after 3 {-2+(1,2)} generations the list reached 166 puzzles
One SE=8.3/1.2/1.2 appeared, and one with 22 clues.
Are the puzzles pattern-related? No. There are no repeating patterns.
Are the puzzles' solution grids related? Yes. All 166 puzzles share the same solution grid and this is not in consequence of the searching method.
Google returns no results for this string. Is this grid well-known for some other characteristic?
I have no tool to examine backdoor size adding more techniques.
Cheers,
MD
BTW, after 3 {-2+(1,2)} generations the list reached 166 puzzles
Hidden Text: Show
One SE=8.3/1.2/1.2 appeared, and one with 22 clues.
Are the puzzles pattern-related? No. There are no repeating patterns.
Are the puzzles' solution grids related? Yes. All 166 puzzles share the same solution grid and this is not in consequence of the searching method.
- Code: Select all
123456789457189623689732154278364591391275846546918372712593468834627915965841237
Google returns no results for this string. Is this grid well-known for some other characteristic?
I have no tool to examine backdoor size adding more techniques.
Cheers,
MD
- dobrichev
- 2016 Supporter
- Posts: 1863
- Joined: 24 May 2010
Re: The hardest sudokus (new thread)
by eleven » Fri Apr 12, 2013 7:52 pm
tarek wrote:I can't confirm the non-singles backdoor size myself but gsf's program is fairly reliable.
Hard to believe, but at least manually i don't manage to find less than 4 backdoor cells (while i had no problem to find 3 backdoor cells for Golden Nugget in 10 minutes). The reason is, that after placing a first number (e.g. r1c1=1), in best case i end up with a BUG+3, then BUG+2, then BUG+1. No number, that resolves one BUG, seems to be able to kill another one.
[Added:]This grid needs 3 backdoors. Any number you place, can't solve more cells than A, B or C.
- Code: Select all
+----------------+----------------+----------------+
| 1 3 2 |A69 A67 B45 |A79 8 B45 |
|C67 C69 C79 |B45 8 1 |B45 2 3 |
| 8 4 5 |A39 2 A37 | 1 6 79 |
+----------------+----------------+----------------+
| 37 8 C379 |B45 1 B245 | 6 C79 B25 |
|C46 C69 1 | 7 3 B25 |B25 C49 8 |
| 5 2 C47 | 8 9 6 | 3 C47 1 |
+----------------+----------------+----------------+
| 2 5 8 |A36 4 A37 |A79 1 A679 |
|C34 1 C34 | 2 A67 9 | 8 5 A67 |
| 9 7 6 | 1 5 8 |B24 3 B24 |
+----------------+----------------+----------------+
- eleven
- Posts: 3173
- Joined: 10 February 2008
Re: The hardest sudokus (new thread)
by denis_berthier » Sat Apr 13, 2013 4:04 am
154 of these 166 puzzles are in W3. The remaining 12 (including the SER 8.3) are in W4 (and adding Subsets doesn't improve their W classification, i.e. none of them is in S3+W3):
As I understand it, after extended search starting from ALL the solution grids (or from a large RANDOM sample), you found only 1 solution grid having minimals with backdoor size 4. Can you confirm?
In addition to the backdoor size, do you get (at least) one set of 4-backdoors? That'd make it easier to check, not that there is no other backdoor set, but at least that no proper subset of this set is a 3-backdoor for a larger set of rules.
If you have the sets of 4-backdoors, this is one thing I can do with SudoRules.
Even before doing these calculations, considering that many eliminations are done by whips[1] and Pairs, it seems very likely to me that adding whips[1] and Pairs in the rules would lead to a smaller backdoor size.
Hidden Text: Show
dobrichev wrote:Are the puzzles' solution grids related? Yes. All 166 puzzles share the same solution grid and this is not in consequence of the searching method.
- Code: Select all
123456789457189623689732154278364591391275846546918372712593468834627915965841237
As I understand it, after extended search starting from ALL the solution grids (or from a large RANDOM sample), you found only 1 solution grid having minimals with backdoor size 4. Can you confirm?
dobrichev wrote:I have no tool to examine backdoor size adding more techniques.
In addition to the backdoor size, do you get (at least) one set of 4-backdoors? That'd make it easier to check, not that there is no other backdoor set, but at least that no proper subset of this set is a 3-backdoor for a larger set of rules.
If you have the sets of 4-backdoors, this is one thing I can do with SudoRules.
Even before doing these calculations, considering that many eliminations are done by whips[1] and Pairs, it seems very likely to me that adding whips[1] and Pairs in the rules would lead to a smaller backdoor size.
- denis_berthier
- 2010 Supporter
- Posts: 4235
- Joined: 19 June 2007
- Location: Paris
Re: The hardest sudokus (new thread)
by dobrichev » Sat Apr 13, 2013 12:22 pm
denis_berthier wrote:dobrichev wrote:Are the puzzles' solution grids related? Yes. All 166 puzzles share the same solution grid and this is not in consequence of the searching method.
- Code: Select all
123456789457189623689732154278364591391275846546918372712593468834627915965841237
As I understand it, after extended search starting from ALL the solution grids (or from a large RANDOM sample), you found only 1 solution grid having minimals with backdoor size 4. Can you confirm?
I started from backdoors(3) in my cache of potential hardest according to Sudoku Explainer, the same collection that recently is managed by champagne. This is somehow biased start point.
After generation of 15-18 millions of bd3 puzzles the five bd4 puzzles appeared in one of the 65 batches so they could be related, including be {+-1} derivatives of a single bd3 puzzle.
Later I used only these 5 puzzles as a seed. I ran {-2,+(1,2)} transformation which means "remove 2 clues in all possible ways, then add up to 2 clues in all possible ways with all possible values and check for validity and minimality". New bd4 appeared and I repeated this 2 more times. The method is biased, but I added clues with all possible values, not only these from the solution grid of the parent puzzle.
denis_berthier wrote:dobrichev wrote:I have no tool to examine backdoor size adding more techniques.
In addition to the backdoor size, do you get (at least) one set of 4-backdoors? That'd make it easier to check, not that there is no other backdoor set, but at least that no proper subset of this set is a 3-backdoor for a larger set of rules.
If you have the sets of 4-backdoors, this is one thing I can do with SudoRules.
Even before doing these calculations, considering that many eliminations are done by whips[1] and Pairs, it seems very likely to me that adding whips[1] and Pairs in the rules would lead to a smaller backdoor size.
I dumped all backdoor sets. Surprise - 40MB file with 3 million backdoors. First few puzzles have 18752 backdoors each. Backdoors consist of several "favorite" clues combined in different ways.
Knowing that this stuff is coming from a single solution grid, I'll try to normalize the puzzles according to the grid and to see how the favorite cells are distributed between puzzles and within a puzzle.
I can upload the whole backdoors dump, or post here first backdoor for each of the puzzles, or all backdoors for a few selected puzzles, or some statistics on favorite cells which would be more useful when represented in the "global" coordinate system of the grid.
Surely in any system of ordered techniques there exist one which breaks this backdoor size. I am not familiar with your terminology and leave the others to comment on your observations.
I will try to transform the puzzles into uniform coordinate system. Next week I manage to continue the generation process, possibly by digging more deeply around these 166 knowns if the used method is exhausted.
- dobrichev
- 2016 Supporter
- Posts: 1863
- Joined: 24 May 2010
Re: The hardest sudokus (new thread)
by dobrichev » Sat Apr 13, 2013 12:46 pm
Below are the same 166 bd4 puzzles morphed to their minlexed only solution grid
Hidden Text: Show
- dobrichev
- 2016 Supporter
- Posts: 1863
- Joined: 24 May 2010
Re: The hardest sudokus (new thread)
by dobrichev » Sat Apr 13, 2013 1:03 pm
15 common clues, 96051898 solutions, at least one of them with 166 backdoor 4 puzzles 
- Code: Select all
......7...5........8..3.1.....36..9...1...84..........7............2......5....3.
- dobrichev
- 2016 Supporter
- Posts: 1863
- Joined: 24 May 2010
Re: The hardest sudokus (new thread)
by denis_berthier » Sat Apr 13, 2013 3:03 pm
dobrichev wrote:Surely in any system of ordered techniques there exist one which breaks this backdoor size.
Yes, of course. I hadn't thought of this. As all these puzzles are in W3 or W4 (i.e. solvable by whips of length <= 3 or 4), their W3 or W4 backdoor size is 0.
- denis_berthier
- 2010 Supporter
- Posts: 4235
- Joined: 19 June 2007
- Location: Paris
Re: The hardest sudokus (new thread)
by eleven » Sat Apr 13, 2013 7:24 pm
Mladen, if i saw it right, all your backdoor size 4 puzzles are minimals of this one (?)
[Added:] Ah, this should be the "maximum clue" - with more minimals.
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.
But interesting might be the base idea, namely that this puzzle has backdoor size 3 for basics (used the other equivalent here):
Then i had to show, that the "maximum" backdoor size 4 puzzle needs another backdoor. Finally i managed it with 3 case distinctions. If someone is interested, i can post the grids later.
btw, the first puzzle can be solved with basics + w-wing, which is a very common and easy-to-spot technique.
- Code: Select all
...4..7...5........8..3.1.....36..9..91...84......8...71.59346..3462.....658...3. # 98896 FNBTHG C29/M4.2047.259
[Added:] Ah, this should be the "maximum clue" - with more minimals.
- 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
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.
But interesting might be the base idea, namely that this puzzle has backdoor size 3 for basics (used the other equivalent here):
- Code: Select all
..2....8.....81.23845.2.16..8..1.6....173...852.8963.1258.4..1....2.985.976158.3. # 98852 FBTHG C42/M3.1716.309
Hidden Text: Show
Then i had to show, that the "maximum" backdoor size 4 puzzle needs another backdoor. Finally i managed it with 3 case distinctions. If someone is interested, i can post the grids later.
btw, the first puzzle can be solved with basics + w-wing, which is a very common and easy-to-spot technique.
- eleven
- Posts: 3173
- Joined: 10 February 2008
One flew over the backdoors
by dobrichev » Mon Apr 15, 2013 1:39 pm
Thanks to JasonLion who moved all previous post in this topic from tarek's The hardest sudokus (new thread) to here.
Last edited by dobrichev on Mon Apr 15, 2013 6:20 pm, edited 1 time in total.
- dobrichev
- 2016 Supporter
- Posts: 1863
- Joined: 24 May 2010
Re: One flew over the backdoors
by JasonLion-Admin » Mon Apr 15, 2013 2:23 pm
I believe I have moved everything related here. If you have a chance please double check my selection of posts. I included at least one earlier post.
-
JasonLion-Admin - Site Admin
- Posts: 89
- Joined: 17 April 2010
- Location: Silver Spring, MD, USA
Re: One flew over the backdoors
by denis_berthier » Mon Apr 15, 2013 3:15 pm
I think it is a very good idea to have separated this topic from the "hardest puzzles" thread, as the backdoor size of a puzzle is unrelated to its difficulty wrt to any known solving method not accepting guessing.
Mladen has reached really interesting results.
IMO, they are on the same level as the non existence of a minimal 16 (even though they don't involve as complex calculations).
In order to better appreciate them, they should be put in the proper historical perspective.
Here, as I don't have the exact dates, I write only a brief sketch of this perspective. Perhaps, someone can provide more precise information about the dates.
7 or 8 years ago, it was conjectured (by gsf?) that all the (standard, i.e. 9x9) Sudoku puzzles had backdoor size <= 2.
5 or 6 years ago, EasterMonter was the first puzzle to be shown to have backdoor size 3. Soon after, a few tens of puzzles were shown to have backdoor size 3.
What Mladen has done recently amounts to two great leaps in the knowledge of backdoors:
- he found 12+ million puzzles with backdoor size 3
- he found 166 puzzles with backdoor size 4.
This can also be related to what is known about the maximum backdoor size of larger puzzles. On the Programmer's forum, Tarek has exhibited 16x16 puzzles with backdoor size 4 and announced larger ones with backdoor size >=5 (see the discussion starting here: http://www.setbb.com/phpbb/viewtopic.php?mforum=sudoku&t=2117&postdays=0&postorder=asc&start=150&mforum=sudoku).
Mladen's results raise the question of how the maximum backdoor size varies with the size of puzzles - but for larger puzzles, this may be very difficult to tackle.
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).
Mladen has reached really interesting results.
IMO, they are on the same level as the non existence of a minimal 16 (even though they don't involve as complex calculations).
In order to better appreciate them, they should be put in the proper historical perspective.
Here, as I don't have the exact dates, I write only a brief sketch of this perspective. Perhaps, someone can provide more precise information about the dates.
7 or 8 years ago, it was conjectured (by gsf?) that all the (standard, i.e. 9x9) Sudoku puzzles had backdoor size <= 2.
5 or 6 years ago, EasterMonter was the first puzzle to be shown to have backdoor size 3. Soon after, a few tens of puzzles were shown to have backdoor size 3.
What Mladen has done recently amounts to two great leaps in the knowledge of backdoors:
- he found 12+ million puzzles with backdoor size 3
- he found 166 puzzles with backdoor size 4.
This can also be related to what is known about the maximum backdoor size of larger puzzles. On the Programmer's forum, Tarek has exhibited 16x16 puzzles with backdoor size 4 and announced larger ones with backdoor size >=5 (see the discussion starting here: http://www.setbb.com/phpbb/viewtopic.php?mforum=sudoku&t=2117&postdays=0&postorder=asc&start=150&mforum=sudoku).
Mladen's results raise the question of how the maximum backdoor size varies with the size of puzzles - but for larger puzzles, this may be very difficult to tackle.
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).
- denis_berthier
- 2010 Supporter
- Posts: 4235
- Joined: 19 June 2007
- Location: Paris
64 posts
• Page 2 of 5 • 1, 2, 3, 4, 5
