The New Sudoku Players' Forum

[Mathimagics]

Code: Select all

   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   | 1 |   | 7 |   |   | 9 |   |   |   | C | D |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   | 2 |   |   |   |   |   |   |   |   | D |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   | A |   | 8 |   |   | 5 |   |   | C | 9 |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   |   |   |   |   | 2 |   |   |   |   | 4 |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   | A | B |   |   | 6 |   |   | 1 |   |   |   | 9 |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   |   |   |   |   |   |   | 3 |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   | C |   |   | 4 |   | A |   |   |   |   |   |   | 1 |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   | A |   |   |   |   |   |   | C | D |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   | 3 | 5 |   |   | 9 | 7 |   |   |   |   |   | 2 | C |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   | B |   | D |   |   |   | 2 |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   | 6 |   |   |   |   | 3 |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   | A |   | 6 | 2 |   | 5 |   |   | 8 |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   |   |   |   | B |   |   | 5 | 7 |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+


Fill the 13x13 grid so that each row, column, left diagonal and right diagonal has values {1-9ABCD}. The definitions of "left/right diagonals" are explained (hopefully quite clearly) here. I also explain there that this is essentially a simple Sudoku variant, with each cell belonging to 4 houses (rows, cols, left diags, right diags).

This introductory puzzle is solvable with naked singles only. For P&P solvers, I recommend drawing up a grid in which the diagonals to which each cell belongs are marked in the left and right corners. For example, with a 5x5 grid, something like this:

Code: Select all

   +----+----+----+----+----+
   |a  z|b  y|c  x|d  w|e  v|
   |    |    |    |    |    |
   +----+----+----+----+----+
   |b  v|c  z|d  y|e  x|a  w|
   |    |    |    |    |    |
   +----+----+----+----+----+
   |c  w|d  v|e  z|a  y|b  x|
   |    |    |    |    |    |
   +----+----+----+----+----+
   |d  x|e  w|a  v|b  z|c  y|
   |    |    |    |    |    |
   +----+----+----+----+----+
   |e  y|a  x|b  w|c  v|d  z|
   |    |    |    |    |    |
   +----+----+----+----+----+


One line puzzle for B&B solvers:

Code: Select all

1.7..9...CD.....2........DA.8..5..C9..........2....4.AB..6..1...9.........3...C..4.A......1...A......CD.35..97.....2CB.D...2.......6....3........A.62.5..8........B..57..

[1to9only]

SE Rating: ED=1.5/1.5/1.5

Solution Path (Notation:1-13): Show

Code: Select all

1.5, Hidden Single: R2C1: 5 in column
1.5, Hidden Single: R11C3: 5 in column
1.5, Hidden Single: R4C4: 5 in column
1.5, Hidden Single: R6C7: 12 in column
1.5, Hidden Single: R4C3: 12 in column
1.5, Hidden Single: R8C3: 3 in column
1.5, Hidden Single: R7C3: 2 in column
1.5, Hidden Single: R1C2: 2 in column
1.5, Hidden Single: R12C4: 12 in column
1.5, Hidden Single: R5C4: 13 in column
1.5, Hidden Single: R13C1: 13 in column
1.5, Hidden Single: R6C2: 13 in column
1.5, Hidden Single: R6C5: 2 in column
1.5, Hidden Single: R8C1: 2 in column
1.5, Hidden Single: R11C1: 9 in column
1.5, Hidden Single: R6C3: 9 in column
1.5, Hidden Single: R13C4: 9 in column
1.5, Hidden Single: R4C2: 9 in column
1.5, Hidden Single: R11C5: 13 in column
1.5, Hidden Single: R13C6: 3 in column
1.5, Hidden Single: R11C6: 12 in column
1.5, Hidden Single: R13C2: 12 in column
1.5, Hidden Single: R5C5: 12 in column
1.5, Hidden Single: R4C6: 13 in column
1.5, Hidden Single: R10C6: 1 in column
1.5, Hidden Single: R6C6: 11 in column
1.5, Hidden Single: R5C7: 5 in column
1.5, Hidden Single: R8C7: 9 in column
1.5, Hidden Single: R12C7: 13 in column
1.5, Hidden Single: R2C8: 9 in column
1.5, Hidden Single: R10C8: 12 in column
1.5, Hidden Single: R3C8: 13 in column
1.5, Hidden Single: R11C9: 2 in column
1.5, Hidden Single: R12C9: 3 in column
1.5, Hidden Single: R2C2: 3 in column
1.5, Hidden Single: R8C9: 5 in column
1.5, Hidden Single: R7C9: 9 in column
1.5, Hidden Single: R9C9: 13 in column
1.5, Hidden Single: R5C10: 2 in column
1.5, Hidden Single: R7C10: 13 in column
1.5, Hidden Single: R6C11: 1 in column
1.5, Hidden Single: R9C4: 1 in column
1.5, Hidden Single: R2C3: 1 in column
1.5, Hidden Single: R8C2: 1 in column
1.5, Hidden Single: R3C5: 1 in column
1.5, Hidden Single: R4C7: 1 in column
1.5, Hidden Single: R11C8: 1 in column
1.5, Hidden Single: R12C10: 1 in column
1.5, Hidden Single: R3C11: 2 in column
1.5, Hidden Single: R4C11: 3 in column
1.5, Hidden Single: R3C4: 3 in column
1.5, Hidden Single: R10C4: 7 in column
1.5, Hidden Single: R7C5: 3 in column
1.5, Hidden Single: R5C8: 3 in column
1.5, Hidden Single: R8C8: 7 in column
1.5, Hidden Single: R4C9: 7 in column
1.5, Hidden Single: R2C5: 7 in column
1.5, Hidden Single: R5C1: 7 in column
1.5, Hidden Single: R3C7: 7 in column
1.5, Hidden Single: R7C2: 7 in column
1.5, Hidden Single: R10C2: 8 in column
1.5, Hidden Single: R1C9: 11 in column
1.5, Hidden Single: R11C4: 11 in column
1.5, Hidden Single: R1C4: 8 in column
1.0, Hidden Single: R6C4: 6 in column
1.5, Hidden Single: R4C1: 6 in column
1.5, Hidden Single: R6C1: 8 in column
1.0, Hidden Single: R12C1: 4 in column
1.5, Hidden Single: R3C2: 4 in column
1.0, Hidden Single: R12C2: 11 in column
1.5, Hidden Single: R9C7: 8 in column
1.5, Hidden Single: R2C6: 8 in column
1.0, Hidden Single: R8C6: 4 in column
1.0, Hidden Single: R1C12: 5 in antidiagonal(\)
1.5, Hidden Single: R10C5: 5 in column
1.5, Hidden Single: R1C5: 4 in column
1.0, Hidden Single: R7C11: 5 in antidiagonal(\)
1.5, Hidden Single: R2C7: 4 in column
1.5, Hidden Single: R7C7: 6 in column
1.0, Hidden Single: R1C7: 10 in column
1.5, Hidden Single: R13C8: 4 in column
1.5, Hidden Single: R9C3: 4 in column
1.0, Hidden Single: R13C3: 6 in column
1.5, Hidden Single: R1C8: 6 in column
1.0, Hidden Single: R1C13: 3 in row
1.5, Hidden Single: R7C8: 8 in column
1.0, Hidden Single: R7C12: 11 in row
1.5, Hidden Single: R8C5: 8 in column
1.5, Hidden Single: R4C5: 11 in column
1.0, Hidden Single: R13C5: 10 in column
1.0, Hidden Single: R8C13: 6 in antidiagonal(\)
1.0, Hidden Single: R8C10: 11 in row
1.0, Hidden Single: R6C12: 7 in diagonal(/)
1.5, Hidden Single: R6C8: 10 in column
1.0, Hidden Single: R9C8: 11 in column
1.0, Hidden Single: R5C12: 8 in diagonal(/)
1.0, Hidden Single: R5C11: 4 in row
1.0, Hidden Single: R4C10: 8 in antidiagonal(\)
1.0, Hidden Single: R4C12: 10 in row
1.0, Hidden Single: R2C12: 12 in diagonal(/)
1.0, Hidden Single: R3C13: 11 in diagonal(/)
1.0, Hidden Single: R3C12: 6 in row
1.0, Hidden Single: R6C9: 4 in diagonal(/)
1.0, Hidden Single: R6C13: 5 in row
1.0, Hidden Single: R10C13: 10 in antidiagonal(\)
1.0, Hidden Single: R11C12: 4 in diagonal(/)
1.0, Hidden Single: R2C9: 10 in antidiagonal(\)
1.0, Hidden Single: R2C10: 6 in antidiagonal(\)
1.0, Hidden Single: R2C11: 11 in row
1.0, Hidden Single: R13C13: 2 in diagonal(/)
1.0, Hidden Single: R13C9: 8 in antidiagonal(\)
1.0, Hidden Single: R10C9: 6 in column
1.0, Hidden Single: R13C12: 1 in row
1.0, Hidden Single: R12C13: 7 in diagonal(/)
1.0, Hidden Single: R11C13: 8 in column
1.0, Hidden Single: R12C12: 9 in row
1.0, Hidden Single: R10C12: 3 in column
1.0, Hidden Single: R11C11: 10 in diagonal(/)
1.0, Hidden Single: R11C10: 7 in row
1.0, Hidden Single: R10C11: 9 in diagonal(/)
1.0, Hidden Single: R9C11: 6 in column
1.0, Hidden Single: R9C10: 10 in row
1.0, Hidden Single: R10C10: 4 in column
ED=1.5/1.5/1.5



[Mathimagics]

Hi 1to9only!

Did you have a PD solver/rater handy already? Or did you knock one up overnight?

What does it say about this 19-clue reduction of the same puzzle:

Code: Select all

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

[1to9only]

Did you have a PD solver/rater handy already? Or did you knock one up overnight?

It is worked on as a side project! I have a generic SudokuExplainer (with Latin Square and X support) which can be turned into a NxN Sudoku solver. This bit is relatively quick! For this Pandiagonal, I had to define the 13 right and left diagonals. Some hand coding/fixing was needed to make the program work correctly.

What does it say about this 19-clue reduction of the same puzzle:

It will be another side project! I have a few other (life) things to do, but I'll have the answer in the next few days.

Code: Select all

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

I think a dot is missing on the end!!

[Mathimagics]

Ok, nice!!

[1to9only]

Code: Select all

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


This is ED=11.9/11.9/7.9.

[Mathimagics]

Interesting!

If you want an easier test, here is a 29-clue version which you might try:

Code: Select all

.....9...CD.....2.........A.8..5...9..........2......A......1.............3......4........1..........CD.3...9..........D...........6.............A.6..............B..57..

The 29-clue puzzle has fairly low T&E complexity (DLX iteration count of 2400), so perhaps is more to your program's liking.

The original 19-clue case I gave before takes 30 minutes with DLX, a real brute. I lost the iteration count, but probably O(100 million)?

Meanwhile, I have found valid 16-clue reductions of this puzzle, but these take hours to solve with DLX. And the possibility of a 15-clue puzzle can't be ruled out yet ...

[creint]

The 19 clue variant:
Starting pencilmarks: 1545
1131 at around 4500 seconds
Then it finds 2 r8c1
+1800
904 at 11000 seconds
9 r4c2 and 9 r9c5
And quickly after that all other 9 then A then 3 then solved.
Solved using a single thread

Because it takes the first exclusion that it finds when > SE 10 there could be a faster solve path. But this is probably < SE 12.

29 clue < SE 10 very fast.

WinSat is very fast at solving the 19 clue.
Probably is using a template method like pattern overlay.

Reducing it is for the first gives is fast but then it slows down.
Given up reducing this 13 given grid after 10500 seconds, only 6 cells left to be checked for minimal. Probably minimal.

Code: Select all

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

[1to9only]

29 clue < SE 10

SE rates this as ED=7.9/7.8/2.9.

ED=2.9 is my implementation of Generalized Intersections, the 1st three eliminations are:

Code: Select all

2.9, Generalized Intersection: Cells R3C2,R3C5,R3C8: 13 in row: -13r13c5, -13r6c5
2.9, Generalized Intersection: Cells R4C6,R5C5,R6C4: 13 in diagonal(/): -13r4c4
2.9, Generalized Intersection: Cells R5C4,R6C4,R12C4: 13 in column: -13r12c10


[Mathimagics]

Great work, guys! I'm impressed ...

For 1to9only: good to know the rater has the capacity to deal with puzzles that are likely to be humanly solvable, which is of course its main function.

That rating works at all is an unexpected bonus!


For creint: I was kind of hoping you might be working on a SAT solver option, while I pursued the DLX approach. You've done well ...

WinSat is very fast at solving the 19 clue.
Reducing it is for the first gives is fast but then it slows down.
Given up reducing this 13 given grid after 10500 seconds, only 6 cells left to be checked for minimal. Probably minimal.

My DLX solver is getting that sort of time (10000s+) at around the 16-17 clue mark, so clearly SAT is better for extreme reduction!

I have produced a bunch of 15-clue puzzles, and am waiting (patiently) for the first attempt at 14-clues to finish. Many many hours involved!

Congratulations for being the first to produce a 13-clue puzzle !!

It's clear that the ultimate limit on minimum givens (12) might be possible too, but we won't easily find them with current solver technology.

But I do have an idea for a radical new approach to the problem ... I need a few days to test its viability ... watch this space ...

Cheers
MM

[Mathimagics]

My 14-clue test has finally finished ...

I began with this 15-clue puzzle, which has only 1 solution:

Code: Select all

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


I chose the "9" in row 3 as the removal candidate, and tested each alternative value, so that I could run parallel jobs:

Code: Select all

   . test (3,10) = 9, alt values {12347ABD}

   . v = 1  no soln     21832s
   . v = 2  no soln      2874s
   . v = 3  no soln      4560s
   . v = 4  no soln      3868s
   . v = 7  no soln      3819s
   . v = A  no soln     21375s
   . v = B  no soln     19402s
   . v = D  no soln     21779s


This constitutes proof that (3,10) is removable, and also that I won't be looking for any further clue removals in this puzzle using DLX ...

[denis_berthier]

Is there any standard notation for the diagonals?
rows are r1, r2, ...
columns are c1, c2, ...

So, should the diagonals be:
d1, d2, ... (d1 going through cell r1c1)
a1, a2, ... (a1 also going through cell r1c1)
with "d" for diagonal and "a" for anti-diagonal.
(with the unfortunate problem that d is ascending and a is descending.)

[denis_berthier]

ED=2.9 is my implementation of Generalized Intersections, the 1st three eliminations are:

Code: Select all

2.9, Generalized Intersection: Cells R3C2,R3C5,R3C8: 13 in row: -13r13c5, -13r6c5
2.9, Generalized Intersection: Cells R4C6,R5C5,R6C4: 13 in diagonal(/): -13r4c4
2.9, Generalized Intersection: Cells R5C4,R6C4,R12C4: 13 in column: -13r12c10


These are whips[1].

[Edit] It's interesting to notice that they are the same whips[1] as in N-Queens, as I identified them in [PBCS].

[Mathimagics]

Is there any standard notation for the diagonals?

Perhaps something like xN and yN for the left and right diagonals through r1cN.

Thus x31 = r1c3, x32 = r2c2 etc, y32 = r2c4, etc ...

[denis_berthier]

Is there any standard notation for the diagonals?

Perhaps something like xN and yN for the left and right diagonals through r1cN.

Yes, numbering seems ok.
I'd avoid x and y, already widely used as horizontal and vertical coordinates.
I thought of u and d, for up and down, but it's not very good either.

I think the best way is to consider there are two systems of coordinates: (r, c) and (d, a) (or other letters).

Thus x31 = r1c3, x32 = r2c2 etc, y32 = r2c4, etc ...

I don't understand your x31.
Diagonals should be numbered from left to right, say d1, ... d13
Anti-diagonals should also be numbered from left to right, say a1, ... a13
Each time, the number is where the line crosses row 1
I thought that's what you meant in the first part.
r1c3 would then be d3a3 and r3c1 would be d3a11


On second thoughts, a better possibility may be to take the centre of the square as the origin of the diagonals r7c7 = d1a1. As grid size must be odd, this would raise no problem.


[Edit] When you propose a puzzle in grid form, could you put a dot in the white cells, as is standard in the Sudoku case?