The New Sudoku Players' Forum

[denis_berthier]

denis_berthier (and anyone else watching this thread), here is mathimagics's other thread on this topic, which is in the sudoku variants section, that goes into some more detail which you may have missed. only a few puzzles have been posted and the hardest ones seem to take more than a day to test for minimality or validity which i find amazing

Yes, I had missed it, thanks.

I remember a guy who published in a scientific journal a super extra intelligent rating based on super extra new chaos concepts - and the hardest Sudoku he found was solvable by Singles.

Difficult Sudokus Created by Replica Exchange Monte Carlo Method is your reference

I had forgotten the reference of this wonderful result.

[Mathimagics]

I expected a larger collection, with intermediate levels of difficulty. If I start spending time on coding the additional constraints, I'd like to be sure there's enough material to exploit them.

I gave you two puzzles on the same grid, one which is a subset of the other. That gives you some thousands of puzzles in between that are easily iterated.

We have (collectively) only been working on this for a few days, so valid puzzles are still somewhat scarce ...

[Mathimagics]

DLX was used to enumerate all sets of 13 mutually disjoint templates, and this process identified 12,386 cases.

I overlooked an important implication of this result.

Enumerating solution grids using this method (disjoint templates) in most cases does NOT enumerate the essentially different grids. It enumerates all the different possible solution grids (up to relabelling).

To obtain a catalog of the ED grids, we would typically have to apply all of the VPT's to each solution grid, obtain a canonical form in each case, then sort the results so we can remove duplicates (grid automorphisms) ...

I went through this process for SudokuP.

So, I was embarrassed not to realise, before now, that the pandiagonal solution space is quite unique: the possible grids and the ED grids are the same set ...

[coloin]

Relieved i wouid say ...but thats ok !! And with so few solution grids the min no of clues must be approaching 12 ...

[Mathimagics]

And with so few solution grids the min no of clues must be approaching 12 ...

Indeed!

creint and I have both found 14-clue puzzles, but the cost of minimality testing available using available solvers (SAT, DLX) solvers is preventing us from going down further.

It is easy to show that (N-1) clue puzzles exist for N = 5, N = 7 and N = 11 (see examples below). So it is probably true for N = 13.

I am working on an alternative method to try and find a 12-clue example ...

Code: Select all

1..............5.2..3....
1....4......5.......3....
......5.2.....1...3......


Code: Select all

.........7...............5.4.2................13.
..........1.....2..7..............3.....4...6....
.............23...6......5.................4.7...


Code: Select all

...8...........B...............................7............5...............A...3....2........6.........4..........1.....
....9..A.........1...........4....3...B...68..........5...............7..................................................
.....3...........1..............................68..4...................................A5...7..............2..........9.


[1to9only]

Easy: (Singles only)

Code: Select all

1..............5.2..3.... ED=1.5/1.5/1.5
1....4......5.......3.... ED=1.5/1.5/1.5
......5.2.....1...3...... ED=1.5/1.5/1.5


Medium:

Code: Select all

.........7...............5.4.2................13. ED=2.9/2.9/2.9
..........1.....2..7..............3.....4...6.... ED=2.9/2.9/2.9
.............23...6......5.................4.7... ED=2.9/2.3/2.3


Diabolical:

Code: Select all

...8...........B...............................7............5...............A...3....2........6.........4..........1.... ED=9.8/9.8/9.7
....9..A.........1...........4....3...B...68..........5...............7................................................. ED=10.4/10.4/8.2
.....3...........1..............................68..4...................................A5...7..............2..........9 ED=11.0/11.0/9.7


[Mathimagics]

Fascinating!

Ok, then. We know that for N=11 that all solutions are known (8 ED grids) and that they are all cyclic. So the rating will probably be lower, if the program can exploit this (a human certainly would!).

Specifically, every solution row R(k) is R(k-1) shifted by a constant A (A = 2 to 9), and every column is shifted by a constant B (B = 2 to 9).

There are only 8 ED grids, so there can be only 8 (A, B) pairs.

ED grids (N=11): Show

Code: Select all

1326879AB54541326879ABAB54132687979AB54132686879AB54132326879AB54141326879AB5B541326879A9AB54132687879AB54132626879AB5413
183296475AB5AB183296476475AB183293296475AB18B183296475A75AB183296496475AB183283296475AB1AB183296475475AB183296296475AB183
185369AB742B742185369A369AB7421852185369AB74AB7421853695369AB7421842185369AB79AB7421853685369AB7421742185369AB69AB7421853
17564389AB289AB21756437564389AB219AB21756438564389AB217AB21756438964389AB2175B217564389A4389AB21756217564389AB389AB217564
1768934A5B234A5B21768921768934A5B934A5B21768B21768934A58934A5B21765B21768934A68934A5B217A5B21768934768934A5B214A5B2176893
14789A635B29A635B214785B214789A634789A635B21A635B214789B214789A635789A635B214635B214789A214789A635B89A635B214735B214789A6
14789A635B29A635B214785B214789A634789A635B21A635B214789B214789A635789A635B214635B214789A214789A635B89A635B214735B214789A6
156879AB4236879AB4231579AB4231568AB423156879423156879AB3156879AB4256879AB4231879AB4231569AB42315687B423156879A23156879AB4


[1to9only]

For the 5x5 PanDiagonal, the 'visible cells' count is 16 (from 25 cells!) - this makes it quite hard to generate a non-'Singles only' sudoku.

For the 7x7 PanDiagonal, I've been able to generate a few non-'Basics only' sudokus:

Code: Select all

.........5...3....2....4......1.........7........ ED=3.0/3.0/2.9 <- Naked Pair
...2....3..45...........................1....7... ED=3.4/3.4/2.9 <- Hidden Pair
.1.....4.........3..5..........6......2.......... ED=3.6/3.6/2.9 <- Naked Triplet
....41....6......3.......................5.....7. ED=6.5/6.5/2.9
...............1......4.................6.....372 ED=7.1/7.1/2.9
...1.6.......3....................4.....7.....2.. ED=7.5/7.5/2.9
......................5.....6.2.4.1...........3.. ED=7.7/7.7/2.9


[Mathimagics]

For the 5x5 PanDiagonal, the 'visible cells' count is 16 (from 25 cells!) - this makes it quite hard to generate a non-'Singles only' sudoku.

And it is probably impossible to do so ...

BTW, I have confirmed the existence of 12-clue PD13's - see here.

I have a fairly radical new solver, which does in milliseconds what was taking us (creint and I) days to do using SAT and/or DLX (ie conventional solver models)

I will post a writeup here shortly, there are still some minor details/issues that I need to tidy up. Because the validity of these puzzles will be so hard to verify independently, I have to make a strong case that my alternative solver really does what it says on the label.

Code: Select all

.........C......2.........A.8..5...9......................................3......4........1...........D............................6..................................7..
.....9...C......2.........A.8..5..........................................3......4........1...........D............................6..................................7..


[denis_berthier]

For the 5x5 PanDiagonal, the 'visible cells' count is 16 (from 25 cells!) - this makes it quite hard to generate a non-'Singles only' sudoku.
For the 7x7 PanDiagonal, I've been able to generate a few non-'Basics only' sudokus:

Code: Select all

.........5...3....2....4......1.........7........ ED=3.0/3.0/2.9 <- Naked Pair
...2....3..45...........................1....7... ED=3.4/3.4/2.9 <- Hidden Pair
.1.....4.........3..5..........6......2.......... ED=3.6/3.6/2.9 <- Naked Triplet
....41....6......3.......................5.....7. ED=6.5/6.5/2.9
...............1......4.................6.....372 ED=7.1/7.1/2.9
...1.6.......3....................4.....7.....2.. ED=7.5/7.5/2.9
......................5.....6.2.4.1...........3.. ED=7.7/7.7/2.9


By sudoku, you lean LS?
I'm curious about your Subsets. Are they LS Subsets (based only on rows and columns) or do you have Subsets based on diagonals? In particular could you give some details about the Naked Triplet?

All these examples can be solved by bivalue-chains[2] or z-chains[2], except the 3rd, which requires z-chains[3]. Such z-chains might be there in the absence in my rules of Subsets involving diagonals.

(solve ".1.....4.........3..5..........6......2..........")
First, a series of whips[1]. I think it's important to identify all the ways the general whip[1] pattern can appear in this game and this is a very good example for this purpose:

Code: Select all

whip[1]: d1n5{r7c2 .} ==> r7c1 ≠ 5
whip[1]: r7n5{c6 .} ==> r4c2 ≠ 5
whip[1]: d2n6{r4c6 .} ==> r4c7 ≠ 6, r1c3 ≠ 6
whip[1]: r1n6{c6 .} ==> r2c6 ≠ 6, r4c2 ≠ 6, r7c5 ≠ 6, r2c5 ≠ 6
whip[1]: c5n6{r3 .} ==> r3c3 ≠ 6
whip[1]: r3n6{c5 .} ==> r6c1 ≠ 6, r7c1 ≠ 6
whip[1]: a2n6{r6c7 .} ==> r6c6 ≠ 6
whip[1]: a2n4{r4c5 .} ==> r4c7 ≠ 4
whip[1]: c7n4{r7 .} ==> r6c6 ≠ 4
whip[1]: d1n1{r2c7 .} ==> r2c6 ≠ 1
whip[1]: c6n1{r7 .} ==> r3c3 ≠ 1
whip[1]: a7n3{r1c7 .} ==> r1c5 ≠ 3
whip[1]: c5n3{r7 .} ==> r6c6 ≠ 3

Code: Select all

Resolution state after Singles and whips[1]:
2357  1     23457 457   2467  4567  237   
4     23567 2567  157   1257  237   137   
167   27    247   3     12467 1247  5     
12367 347   1257  1457  2457  367   1237 
12357 247   13457 6     37    2457  12347
157   34567 1347  2     1357  157   467   
27    23457 367   147   13457 12357 12467

Code: Select all

z-chain[2]: r1n3{c3 c7} - r6n3{c5 .} ==> r7c2 ≠ 3
whip[1]: c2n3{r6 .} ==> r4c7 ≠ 3
whip[1]: c7n3{r5 .} ==> r5c3 ≠ 3
z-chain[2]: c2n5{r2 r6} - d6n5{r2c5 .} ==> r1c3 ≠ 5
whip[1]: r1n5{c6 .} ==> r6c6 ≠ 5
whip[1]: d4n5{r7c5 .} ==> r2c5 ≠ 5
z-chain[2]: d2n7{r4c6 r5c5} - c4n7{r4 .} ==> r1c3 ≠ 7
z-chain[2]: r3n4{c3 c6} - a2n4{r5c6 .} ==> r1c5 ≠ 4
whip[1]: c5n4{r7 .} ==> r7c2 ≠ 4
whip[1]: c2n4{r6 .} ==> r5c3 ≠ 4
z-chain[2]: r2n1{c5 c7} - c3n1{r5 .} ==> r6c1 ≠ 1
whip[1]: d6n1{r7c7 .} ==> r4c7 ≠ 1
whip[1]: c7n1{r7 .} ==> r7c5 ≠ 1
whip[2]: d2n7{r4c6 r7c3} - a7n7{r4c3 .} ==> r3c5 ≠ 7
z-chain[2]: r3n7{c3 c6} - c4n7{r1 .} ==> r2c2 ≠ 7
whip[2]: d2n7{r7c3 r4c6} - r2n7{c6 .} ==> r7c5 ≠ 7
z-chain[3]: r3n7{c6 c2} - r1n7{c7 c6} - d2n7{r4c6 .} ==> r5c1 ≠ 7
z-chain[3]: r3n7{c6 c1} - a3n7{r6c1 r5c7} - d2n7{r5c5 .} ==> r7c6 ≠ 7
z-chain[3]: r6c1{n7 n5} - r7c2{n5 n2} - r3c2{n2 .} ==> r6c2 ≠ 7
z-chain[2]: c2n7{r5 r7} - c4n7{r2 .} ==> r4c1 ≠ 7
whip[2]: c1n7{r7 r3} - c2n7{r4 .} ==> r7c7 ≠ 7
z-chain[3]: c2n7{r7 r4} - a2n7{r4c5 r7c1} - d2n7{r7c3 .} ==> r5c7 ≠ 7
z-chain[3]: r6c1{n7 n5} - r7c2{n5 n2} - r3c2{n2 .} ==> r5c2 ≠ 7
z-chain[2]: c2n7{r4 r7} - d2n7{r4c6 .} ==> r3c3 ≠ 7
z-chain[2]: r3n7{c2 c6} - d6n7{r1c6 .} ==> r6c5 ≠ 7
z-chain[2]: a1n7{r5c5 r6c6} - c2n7{r3 .} ==> r4c5 ≠ 7
z-chain[2]: a2n7{r6c7 r7c1} - r3n7{c1 .} ==> r6c6 ≠ 7
stte

[Edit:]
- added explicitly the whips[1]
- added the resolution state after whips[1]
- corrected the output function for anti-diagonal csp-variables (missing n factor)

[1to9only]

By sudoku, you lean LS?
I'm curious about your Subsets. Are they LS Subsets (based only on rows and columns) or do you have Subsets based on diagonals?

Yes, they are Latin Squares, with the additional 7 right and 7 left diagonal constraints.

In particular could you give some details about the Naked Triplet?

After a bunch of Generalised Intersections:

General Intersections: Show

Code: Select all

2.9, Generalized Intersection: Cells R1C1,R4C1,R5C1: 3 in column: -3r1c5
2.9, Generalized Intersection: Cells R2C2,R4C2,R6C2: 6 in column: -6r4c7
2.9, Generalized Intersection: Cells R2C4,R4C4,R7C4: 1 in column: -1r2c6
2.9, Generalized Intersection: Cells R1C4,R4C4,R7C4: 4 in column: -4r4c7
2.9, Generalized Intersection: Cells R5C5,R6C5,R7C5: 3 in column: -3r6c6
2.9, Generalized Intersection: Cells R3C6,R6C6,R7C6: 1 in column: -1r3c3
2.9, Generalized Intersection: Cells R5C7,R6C7,R7C7: 4 in column: -4r6c6
2.9, Generalized Intersection: Cells R6C7,R7C7: 6 in column: -6r3c3, -6r6c1, -6r7c1, -6r6c6
2.9, Generalized Intersection: Cells R3C1,R4C1: 6 in column: -6r7c5, -6r4c2
2.9, Generalized Intersection: Cells R2C2,R6C2: 6 in column: -6r2c5, -6r2c6
2.9, Generalized Intersection: Cells R1C5,R3C5: 6 in column: -6r1c3
2.9, Generalized Intersection: Cells R5C1,R5C3,R5C6: 5 in row: -5r7c1
2.9, Generalized Intersection: Cells R7C2,R7C5,R7C6: 5 in row: -5r4c2


Comes this Naked Triplet:

Code: Select all

3.6, Naked Triplet: Cells R1C7,R2C6,R7C1: 2,3,7 in diagonal(/): -37r6c2, -27r3c5, -37r5c3, -7r4c4


Note: Only main diagonals shown, as I've not changed the code for X much.

The ED=3.0/3.0/2.9 puzzle: 3.0, Naked Pair: Cells R5C7,R7C5: 4,6 in diagonal(/): -46r1c4, -6r3c2, -6r4c1

[denis_berthier]

Comes this Naked Triplet:

Code: Select all

3.6, Naked Triplet: Cells R1C7,R2C6,R7C1: 2,3,7 in diagonal(/): -37r6c2, -27r3c5, -37r5c3, -7r4c4

OK, thanks. Thats what I thought and why I didn't find it: it relies on a diagonal.

[Hajime]

For a simple mathematical introduction to pandiagonal LS's, and how to go about proving there are no solutions if N is divisible by 3, have a look at this PDF

There is no solution for the 9x9 PanDiagonal? I can confirm that.

[denis_berthier]

Note: Only main diagonals shown, as I've not changed the code for X much.

Do you mean your Subsets are only those of X-LatinSquares?
I wouldn't be too much surprised, as the possibilities for Subsets in full Pandiags are almost unlimited.
As I didn't have X-LatinSquares previously, I don't even have the corresponding Subsets. I don't worry too much about Subsets, because most of their eliminations can be done by chains.

[creint]

Code: Select all

....41....6......3.......................5.....7.

X-wing

Code: Select all

...............1......4.................6.....372 ED=7.1/7.1/2.9

After locked singles only need x-wing to solve it:
4 in anti-diagonal 1 and 3 can be linked with column 1 and row 5, -4r5c6 -4r7c1
Same for 4a1 4a7 - r1 c5 => -4r1c4 -4r2c5
Same for 4a1 4a7 - r1 c5 => -4r1c4 -4r2c5
Same for 4a3 4a7 - r6 c7 => -4r6c3 -4r3c7

Code: Select all

...1.6.......3....................4.....7.....2.. ED=7.5/7.5/2.9

is harder then

Code: Select all

......................5.....6.2.4.1...........3.. ED=7.7/7.7/2.9