The New Sudoku Players' Forum

[999_Springs]

this thread was inspired by the hard 5x5 and latin phrasebook threads, which try to enumerate all the 5x5 and 6x6 latin squares that are not solvable with all singles. of course latin squares differ from sudoku in that they don't have boxes.

inspired by those i was wondering what the hardest 6x6 sudoku puzzles would be? i did a search on hard 6x6s and found examples of a few puzzles in this forum that require forcing chains, such as in this thread

i don't know if there's any good software out there to efficiently rate 6x6 sudokus by difficulty so i'm using this haphazard method of cramming 7,8,9's into the unused cells in sudoku explainer's GUI and pressing solve step and ignoring all the times when SE keeps angrily yelling at you repeatedly that the puzzle is invalid, by clicking get all hints -> get next hint. maybe someone knows something better?

the hardest puzzle i found was the puzzle that Pat first posted in the above thread. for all puzzles in this post, assume a 2x3 box size of 2 rows by 3 columns.

Code: Select all

....4.
.1.3.5
...2..
..3...
6.2.5.
.5....  SE 7.3

i also found this puzzle in an old text file of mine, with a note that it was #36350 from menneske.org, i don't remember how i found it whether it was by chance on that website or from this forum

Code: Select all

.31..4
2.....
....3.
.6....
.....1
1..56.  SE 7.3

i also got really bored the other day and manually rated with SE 100 6x6 puzzles from simon tatham's site and 50 from menneske.org with the puzzle generator set to the highest difficulty level to see what i could find. for the simon tatham puzzles i set symmetry to none; the menneske puzzles must have rotational symmetry which limits the puzzle space, since with 6x6s that means they must have an even number of clues, and i suspect that the 9-clue area should have a lot of hard puzzles. this was the distribution by SE rating

Code: Select all

SE   ST   menneske
4.2       21
4.5    5
4.6   25
5.7        1
6.5    1
6.6   42  23
6.7    1
6.8        1
7.1   20   3
7.2    6   1
------------------
     100  50

the differences in difficulty at the lower levels are almost certainly due to technique hierarchy used in determining puzzle difficulty between both sites. almost every 4.6 was isomorphic at the sticking point to the 4.6/68 (not 69) in the maximum clues per se rating thread which is really weird.

no 7.3 was found. here are the 6 7.2's from simon tatham's site. i thought i'd saved the 7.2 from menneske but apparently i didn't

Code: Select all

3......52.3.....25.......4...3..14..
14..5.....2.....6....1..3.......5..2
2.......6.254...6....1...3...6....3.
...1..1.4.5....5.6....3..4..2.5.....
..1.46.4..3....1.......3.6....2.4...
3..6....6...1...2..2...4..1..5.5....

anyone want to have a look at what the hardest 6x6 sudokus may be, using any measure of difficulty of their choice?

for reference, if you're measuring difficulty by what N is needed to solve the puzzle using N-link chains (without grouping, branching or als's) here is a rough correspondence
SE 7.0 = 6 (m-ring only)
7.1 = 7 or 8 (not xy-wing, xy-loops or x-chains)
7.2 = 9 or 10 (not xy-loops or x-chains)
7.3 = 11 to 14 (ditto)
7.4 = more
7.5+ = not possible, need other methods

[Mathimagics]

.
I'm not sure about SE ratings, but I can at least tell you about 6 x 6 Sudoku puzzles that are minimal and "totally weak" (TW), by which I mean they have NO singles (hidden or naked).

There are, from my results, 14154 distinct TW puzzles across the 49 ED grids. I haven't posted these results yet as I just did the enumeration today.

I have ranked these roughly by the number of guesses required by my solver (a modified dobrichev-fsss2 solver). The 4 highest guess-count puzzles are:

Code: Select all

  13: ........61..2.......4.2..4.61.6.1..5
  12: .234..4....2..5...3..5.....6..6...4.
  11: 1.......61..........452...2..5.6.24.
  10: 12..5..561.........4...3...2...12.6.
  10: 1...5.45...221..4......1......6..3..


So by one measure they would appear to be "hard".

I can post the entire TW puzzle set here if anybody is in a position to rank them by other means …

[Mathimagics]

.
A correction to my list of "hardest" puzzles is in order. The guess counts I used to rank the TW puzzles were the total guesses required to prove uniqueness of solution. I should have used the number of guesses required to get the FIRST solution only.


The maximum using this measure was 10, which is still quite high. The top 6 are shown here (nfm = # of forced moves, ie singles)

Code: Select all

1...5.45...221..4......1......6..3..: nfm =  0, nguess = 10
.2..5....1..2...4..64..5.42.6.......: nfm =  0, nguess =  9
....5.45...221..4...4..1......6..3..: nfm =  0, nguess =  9
1...5..5...221..4...4..1......6..3..: nfm =  0, nguess =  8
.2..5....1..2.5.4..64....42.6.......: nfm =  0, nguess =  8
...4....6.3.2.1..4...2...12..55.....: nfm =  0, nguess =  8


The same test applied to the 2 x puzzles rated "SE 7.3" in the OP gives:

Code: Select all

....4..1.3.5...2....3...6.2.5..5....: nfm =  1, nguess =  2 
.31..42.........3..6.........11..56.: nfm =  1, nguess =  2


[qiuyanzhe]

Among the first 5 puzzles with most number of guesses, none has a difficulty rating over 6.6. Seems that the number of guesses strongly depends on where to start guessing..?

[Mathimagics]

Good point, qiuyanzhe!

It's not clear to me how dobrichev's solver makes guesses. I could report the optimal # of guesses by checking which candidate cells lead to the shortest resolution?

But meanwhile, I have attached the full TW list, which you might simply check for the highest rating puzzles.

AllTW.zip

(79.34 KiB) Downloaded 249 times

[1to9only]

i don't know if there's any good software out there to efficiently rate 6x6 sudokus by difficulty ...

having looked at the SE rating code quite a bit in the past months, i think SE can be modified to rate 6x6 grids with blocks of V=2 and H=3, but the work to change all '9's to '6's (about a 100 of these!) would be non-trivial, and then there is testing... i'm not sure about the GUI bits.

[tarek]

For your solver Mathimagics, the number of guesses will have no correlation with the difficulty according to a different technique set. It can however show how difficult it is for somebody solving using singles only by counting the “minimum” number of guesses required to solve a certain puzzle with singles and how many of these guesses are possible to give is an idea of the possibility of a lucky guess. The terms which I’m sure you are all familiar with are Backdoor Size and number of backdoors.

For a vanilla 9x9 sudoku Easter monster was shown to be of a singles backdoor size 3, there many much easier puzzles with that backdoor size though.

I experimented using gsf’s Sudoku FNNTHXYKO technique sets in the Sukaku thread but even then a puzzle difficulty is measured against the guesses required for the technique set used so no idea how difficult on the SE scale

Tarek

[Mathimagics]

Ok, I failed to spot that 999_Springs was using essentially a 9x9 hack to estimate the SE rating, I just carelessly assumed that his 7.3 examples were verified. But as he says himself, no software exists … (memo to self: read the post!)

But also we have :

Among the first 5 puzzles with most number of guesses, none has a difficulty rating over 6.6. Seems that the number of guesses strongly depends on where to start guessing..?

How are you doing this SE rating?

I will attempt to produce a pseudo-rating ranking based on "best-guessing", as tarek suggests …

[999_Springs]

i confirm that all 5 puzzles in your first post have SE 6.6 (again using the method of "sticking 7,8,9 into SE's GUI and clicking solve step while ignoring it yelling at you") and are all solvable using one or two turbot fish, plus basics. this is done by hand, if we actually had software to do this, it would be nice

the puzzles in your second post have SE 6.6, 6.6, 7.2, 7.2, 6.6, 7.2 respectively

i'm thinking about how to whip up a quick solver program to estimate SE ratings. at each step SE finds what it considers to be the "simplest" move that leads to a contradiction and plays it, so a solver based on the same principles would be nice. so i'm thinking after all singles have been played:

for each candidate
- assume it's true and see if it leads to a contradiction, solution, or stuck
- if it leads to a contradiction, count how many steps you need to get to a contradiction
play the move that was the shortest path to a contradiction

at the end, the rating of a puzzle is the length of the longest one of these shortest contradiction paths.

i think such a method would make more sense than counting guesses, which seems very luck based

to determine "length" you could use any measure. for instance you look for all naked and hidden singles from a given puzzle state, and play them in one go, and count that as one step (like bob hanson's solver). this would mean that a turbot fish for instance would give you the required contradiction in one step

e.g. the 2nd puzzle in your 2nd post
.2..5....1..2...4..64..5.42.6.......
step 0: assume 1r3c6
step 1: singles 1r4c1, 6r3c4, 1r6c5, 1r6c2, 1r5c1, 3r5c6
step 2: contradiction there's two 1s in column 1. so this is a 1-step move

by this measure of difficulty, locked candidates are 0-step moves, any N-link chain for N=4 to 7 (4 = pairs and x-wings, 5 = turbot fish, 7 = se 7.1's) is a 1-step move, N=8 to 11-link chains are 2-step moves etc. but the converse isn't true, since this allows for grouping and branching whereas SE's AIC's do not (e.g. finned x-wing would be a 1)

i'm pretty sure i could write a quick solver to do something like this in a few hours but i've got a new years eve party to go to so that will have to wait.

1to9only: would it be faster to just cram 7,8,9's into the empty cells and deliberately bypass SE's validity check instead? like if you do this and click solve step, SE will find all methods up to 6.2 before it starts moaning at you that the puzzle is invalid, if you bypass that check you can get it to rate stuff harder than that

edit: tarek i'm pretty sure mathimagics isn't currently doing backdoor size or anything similar to it, just counting guesses until the puzzle solves, including wrong guesses. it's a 6x6, everything will be backdoor size 1 i'm sure

I could report the optimal # of guesses by checking which candidate cells lead to the shortest resolution?

this would give you the backdoor size, which i'm sure would be 1 on every puzzle. instead, what i'm suggesting is to use the longest length of all the shortest resolution paths by any length measure of your choice as a rating

[Mathimagics]

what i'm suggesting is to use the longest length of all the shortest resolution paths by any length measure of your choice as a rating

Ok, I'm not inclined to tinker with my solver, for various reasons. My suggestion is that you get somebody here (or elsewhere) to take the Java source code for SE (see here) and build a specific separate 6x6 version "SE6" (which I think would be less painful than adding 6x6 support to the existing one).

I used to know Java, but it's not really my cup of tea (yok, yok )

Then you will have a common SE rating system and all of the alternative methods become irrelevant.

The hardest puzzles may not necessarily be TW, I suppose, they could possibly be PW (with low forced-move counts). I have a complete catalog of all minimal puzzles, shown below with TW/PW(fm) counts by # of clues. Surely the hardest will come from FM = 0 to 3, which is about 150K puzzles.

These can be extracted and fed as a batch into the SE6 program, whenever that becomes available!

Code: Select all

Sudoku 6x6 (49 ED grids) MP table (total minimal puzzles = 72,425,047)

 +----+-----------+-----------+--------+---------+---------+---------+---------+---------+---------+---------+
 | NC |   Minimal |    Strong | TW(0fm)| PW(1fm) | PW(2fm) | PW(3fm) | PW(4fm) | PW(5fm) | PW(6fm) | PW(7+fm)|
 +----+-----------+-----------+--------+---------+---------+---------+---------+---------+---------+---------+
 |  8 |      2619 |      2447 |      0 |       1 |       0 |       1 |       1 |       0 |       0 |     169 |
 |  9 |    607072 |    576686 |     23 |      54 |     130 |     167 |     183 |     226 |     221 |   29382 |
 | 10 |  12884906 |  12256735 |    869 |    2703 |    4120 |    5376 |    6831 |    8219 |    9921 |  590132 |
 | 11 |  35853981 |  34019016 |   6785 |   15311 |   20028 |   27392 |   34573 |   39854 |   48089 | 1642933 |
 | 12 |  20408957 |  19330960 |   5675 |   11150 |   18264 |   26635 |   30424 |   36737 |   37206 |  911906 |
 | 13 |   2601185 |   2472427 |    747 |    1632 |    3272 |    4881 |    5692 |    5521 |    5632 |  101381 |
 | 14 |     65547 |     62403 |     55 |      76 |     112 |      85 |      96 |     117 |     363 |    2240 |
 | 15 |       780 |       780 |      0 |       0 |       0 |       0 |       0 |       0 |       0 |       0 |
 +----+-----------+-----------+--------+---------+---------+---------+---------+---------+---------+---------+
 |    |  72425047 |  68721454 |  14154 |   30927 |   45926 |   64537 |   77800 |   90674 |  101432 | 3278143 |
 +----+-----------+-----------+--------+---------+---------+---------+---------+---------+---------+---------+


[EDIT] This table is inaccurate. See the update below.

[Mathimagics]

.
Perhaps the 3 cases of NC=8 and FM = 1,2,4 are worth a look?

Code: Select all

..34...5.....3......1..2.....56.....
.....6.5.1..2..3.......1......6...4.
1.........3........34.2......5.6..4.


[999_Springs]

what i'm suggesting is to use the longest length of all the shortest resolution paths by any length measure of your choice as a rating

Ok, I'm not inclined to tinker with my solver, for various reasons. My suggestion is that you get somebody here (or elsewhere) to take the Java source code for SE (see here) and build a specific separate 6x6 version "SE6" (which I think would be less painful than adding 6x6 support to the existing one).

I used to know Java, but it's not really my cup of tea (yok, yok )

Then you will have a common SE rating system and all of the alternative methods become irrelevant.

sure, 1to9only has released a clone of sudoku explainer for tarek's pencilmark grid purposes, if he can do that I'm pretty sure modifying se for 6x6 stuff shouldn't be too hard, if he wants to do it of course

i guess what i forgot to mention in my other post is that the max(min(singles contradiction length) per pm grid) per puzzle approach was intended to be an approximation of good SE ratings at the 7 level that i could whip up in a few hours, so my intention was to filter all puzzles through this and get the best 100 and rate those with se by hand if nobody finds or makes a decent batch solver (doesn't have to be SE it could be anything really). any puzzle that goes to 3 on my suggested rating is guaranteed to be a 7.3+ (converse not true) (exception it won't find 123-123-123 naked triplets or some weird URs/APEs, which is more relevant in the 9x9 case but probably extremely rare here)

on a train so can't rate the fm=1,3,4 8's

[1to9only]

sure, 1to9only has released a clone of sudoku explainer for tarek's pencilmark grid purposes, if he can do that I'm pretty sure modifying se for 6x6 stuff shouldn't be too hard, if he wants to do it of course

i'll take a look, maybe i'll have something next year!!! b4 then, HNY.

[tarek]

1to9only did that kind modification on my request. It was mainly to read the 729 line code & suppress the error messages. I haven't managed to rate anything very difficult as it takes ages but I'm happy that I've got something to work on.

I haven't looked at the code to assess how much work it needs to shift from 9x9 vanilla to less than 9x9 and Latin square

The techniques arsenal are reduced in LS as there is no interaction between boxes and lines anymore, so the SE rating comparison is really questionable!!!

tarek

[1to9only]

HNY all. A quick hack of SE, and run against Mathimagics's AllTW list of 14154 6x6 grids shows:

- the highest rated grid is:

Code: Select all

..3...4.....2..3.5.....1.6.5.45...1. ED=8.3/8.3/6.6


- the breakdown by difficulty rating is:

Code: Select all

     35 ED=8.3          ED=8.3/8.3/6.6
     20 ED=8.2          ED=8.2/6.6/6.6
      2 ED=7.8          ED=7.8/7.8/7.1
      5 ED=7.7          ED=7.7/7.7/4.4
      5 ED=7.6          ED=7.6/7.6/7.6
     12 ED=7.3          ED=7.3/7.3/4.4
   1607 ED=7.2          ED=7.2/7.2/7.2
   3826 ED=7.1          ED=7.1/7.1/7.1
     25 ED=7.0          ED=7.0/7.0/7.0
     75 ED=6.9          ED=6.9/6.9/6.6
    203 ED=6.8          ED=6.8/6.8/6.8
    197 ED=6.7          ED=6.7/6.7/6.6
   3413 ED=6.6          ED=6.6/6.6/6.6
     12 ED=6.5          ED=6.5/6.5/6.5
     33 ED=6.2          ED=6.2/6.2/3.2
     21 ED=5.7          ED=5.7/4.5/2.6
    168 ED=5.6          ED=5.6/4.4/2.6
     18 ED=4.6          ED=4.6/4.4/2.6
    209 ED=4.5          ED=4.5/4.5/3.4
     89 ED=4.4          ED=4.4/4.4/4.4
   2675 ED=4.2          ED=4.2/4.2/4.2
     20 ED=3.4          ED=3.4/3.4/3.4
     41 ED=3.2          ED=3.2/3.2/3.2
    226 ED=3.0          ED=3.0/3.0/3.0
     67 ED=2.8          ED=2.8/2.8/2.8
    463 ED=2.6          ED=2.6/2.6/2.6
     34 ED=2.5          ED=2.5/2.5/2.5
    621 ED=2.0          ED=2.0/2.0/2.0
     32 ED=1.7          ED=1.7/1.7/1.7
 ------                 --------------
  14154                 highest rating


I'll have a Sudoku6(2Rx3C)Explainer.jar out soon...

The GUI is untouched (still 9x9), so will NOT work well with the 6x6 solver!!

PS. The first 2 grids in post #1 are indeed rated ED=7.3/1.2/1.2.