The New Sudoku Players' Forum

[m_b_metcalf]

the NC+ condition must hold for the diagonals of an X-sudoku.

He also introduced a Sudoku-X variation of the NC puzzle, which did NOT require that the diagonals be non-consecutive.

It is not possible to have adjacent cells AND diagonals to be non-consecutive. The middle cell r5c5 has 8 neighbors which should not have non-consecutive values, but at the same time the middle box needs all digits.

This is true only for N=3. I now present an XNC+sudokuNC+ for N=4. If someone could kindly verify it, I'll post one for N=5 (it involved a lot of tricky new code). I can also post a printable version if requested (it's humanly solvable).

Thanks,

Mike

[Edit: I have been able to remove 8 clues from the original post - I neglected to apply the X constraint during the final reduction step. Sorry.]

Code: Select all

   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  8 11  .  .  .  .  .  .  .
  .  .  .  . 14  7  . 16 13  . 12  1  .  .  .  .
 11  1  .  .  .  2  4  9 16  7 15  .  .  . 12 14
  .  . 14  .  .  . 15  .  . 13  .  .  .  6  .  .
  .  .  .  .  .  .  .  4  8  .  .  .  .  .  .  .
  .  .  .  . 10  .  .  .  .  .  . 14  .  .  .  .
  .  7  5  .  .  1  8  .  .  9 11  .  . 14  2  .
  . 12 16  .  .  3  6  .  .  4  2  .  . 10 13  .
  .  .  .  . 16  .  .  .  .  .  . 12  .  .  .  .
  .  .  .  .  .  .  . 14  6  .  .  .  .  .  .  .
  .  . 11  .  .  .  7  .  .  3  .  .  .  8  .  .
  9  4  .  .  .  8  3  7  2 14 16  .  .  .  1 13
  .  .  .  .  4 12  .  1  7  .  8 10  .  .  .  .  Forbidden pairs: 1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9, …, 16-1, also on the diagonals.
  .  .  .  .  .  .  . 13  4  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  XNC+sudokuNC+; easy; 68 givens, symmetric, probably not minimal.


For tarek

Code: Select all

................
.......8B.......
....E7.GD.C1....
B1...249G7F...CE
..E...F..D...6..
.......48.......
....A......E....
.75..18..9B..E2.
.CG..36..42..AD.
....G......C....
.......E6.......
..B...7..3...8..
94...8372EG...1D
....4C.17.8A....
.......D4.......
................

[hkociemba1]

I now present an XNC+sudokuNC+ for N=4. If someone could kindly verify it,

Yes, I can verify it. But it has an unique solution even if you ignore the fact that NC+ should also hold on the diagonals.

[m_b_metcalf]

I now present an XNC+sudokuNC+ for N=4. If someone could kindly verify it,

Yes, I can verify it. But it has an unique solution even if you ignore the fact that NC+ should also hold on the diagonals.

Thanks. I'll work on it more tomorrow.

Mike

[tarek]

I now present an XNC+sudokuNC+ for N=4. If someone could kindly verify it,

Yes, I can verify it. But it has an unique solution even if you ignore the fact that NC+ should also hold on the diagonals.

Thanks. I'll work on it more tomorrow.

Just to confirm that it ported perfectly. As I haven't yet implemented the XNC or XNC+ but still got a unique solution in their absence I can confirm what hkociemba1 mentioned. This means that it can be solved without them but knowing would make solving easier.

tarek

[hkociemba1]

I ran my reduce routine (preserving the given symmetry) on Mike's 68 givens puzzle for the night in the hope that the reduction process will produce a true XNC+, not just an NC+ which has XNC+ property. And indeed the reduction to 56 givens was a success. It is a very hard puzzle now for me. As NC+ X-Sudoku my SAT solver takes 80 s to find the first solution, but there are other solutions (I stopped after finding 6 solutions). As XNC+ it takes 390 s, with a single solution.

Code: Select all

 +-------------+-------------+-------------+-------------+
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . | 14  7  . 16 | 13  . 12  1 |  .  .  .  . |
 | 11  1  .  . |  .  .  4  9 | 16  7  .  . |  .  . 12 14 |
 +-------------+-------------+-------------+-------------+
 |  .  . 14  . |  .  . 15  . |  . 13  .  . |  .  6  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . | 10  .  .  . |  .  .  . 14 |  .  .  .  . |
 |  .  7  5  . |  .  1  8  . |  .  9 11  . |  . 14  2  . |
 +-------------+-------------+-------------+-------------+
 |  . 12 16  . |  .  3  6  . |  .  4  2  . |  . 10 13  . |
 |  .  .  .  . | 16  .  .  . |  .  .  . 12 |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  . 11  . |  .  .  7  . |  .  3  .  . |  .  8  .  . |
 +-------------+-------------+-------------+-------------+
 |  9  4  .  . |  .  .  3  7 |  2 14  .  . |  .  .  1 13 |
 |  .  .  .  . |  4 12  .  1 |  7  .  8 10 |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 +-------------+-------------+-------------+-------------+

I would be interested how hard this puzzle is for a different solving approach. Here also a single character format

Hidden Text: Show

Code: Select all

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

[m_b_metcalf]

I ran my reduce routine (preserving the given symmetry) on Mike's 68 givens puzzle for the night in the hope that the reduction process will produce a true XNC+, not just an NC+ which has XNC+ property.
[snip]
I would be interested how hard this puzzle is for a different solving approach.

Well, it was purely fortuitous that this puzzle worked at all. It was produced by code that contained a bug (exceeding array bounds, with unforeseeable consequences) but it was nevertheless valid. It could even be used to test XsudokuNC+ as well as XNC+sudokuNC+ and could be further reduced to a level where my solver grinds for an hour before I put it out of its misery (thanks Herbert).

I now have the temerity to post another attempt using what I hope is now correct code.

Regards,

Mike

Code: Select all

  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  . 16 13  .  .  .  .  .  .  .
 11  1  .  .  .  2  .  9 16  . 15  .  .  . 12 14
  4  . 14  .  .  9 15  .  . 13  7  .  .  6  .  1
  .  .  .  .  .  .  .  4  8  .  .  .  .  .  .  .
  .  .  . 15 10  .  . 11  3  .  . 14  7  .  .  .
  .  7  5  .  .  1  8  .  .  9 11  .  . 14  2  .
  . 12 16  .  .  3  6  .  .  4  2  .  . 10 13  .
  .  .  .  2 16  .  . 10 15  .  . 12  4  .  .  .
  .  .  .  .  .  .  . 14  6  .  .  .  .  .  .  .
 15  . 11  .  .  4  7  .  .  3  9  .  .  8  . 16
  9  4  .  .  .  8  .  7  2  . 16  .  .  .  1 13
  .  .  .  .  .  .  .  1  7  .  .  .  .  .  .  .   Forbidden pairs: 1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9, …, 16-1, also on the diagonals.
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .   XNC+sudokuNC+, 68 givens, easy, symmetric, empty diagonals, probably not minimal.

For tarek:

Code: Select all

................
................
.......GD.......
B1...2.9G.F...CE
4.E..9F..D7..6.1
.......48.......
...FA..B3..E7...
.75..18..9B..E2.
.CG..36..42..AD.
...2G..AF..C4...
.......E6.......
F.B..47..39..8.G
94...8.72.G...1D
.......17.......
................
................

[hkociemba1]

This puzzle too has a single solution without assuming XNC+ but just NC+ sudokuX.

[tarek]

I would be interested how hard this puzzle is for a different solving approach. Here also a single character format

Hidden Text: Show

Code: Select all

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

Well I modified the solver to solve XNC & XNC+ additional constraints ... I stopped the solver after 1 hour (No output & No invalidity)

[m_b_metcalf]

This puzzle too has a single solution without assuming XNC+ but just NC+ sudokuX.

This is true if you use techniques beyond basic ones. If you restrict the solver to techniques up to naked quads (SE = 5.0, for human solvers) you need to take account of the XNC+ constraint.

Regards,

Mike

[Mathimagics]

Well I modified the solver to solve XNC & XNC+ additional constraints ...

Et tu, tarek?

BTW: Diagonal constraints tend to severely limit the grid pool, and so do NC constraints. So for the 9x9 case the ED pool for SudokuX-NC is just 1081 (of the 330,845 NC grids, only 1081 have X-property).

This drops to just 56 (of 12,263) for NC+.

As far as I can tell, and you chaps might be able to confirm this with your solvers, there is NO 9x9 SudokuNC grid which has both the X-property and the XNC property.

[hkociemba1]

This is true if you use techniques beyond basic ones. If you restrict the solver to techniques up to naked quads (SE = 5.0, for human solvers) you need to take account of the XNC+ constraint.

OK, I understand. The support for basic methods is very rudimentary in my solver for X, NC+ etc. So I cannot distinguish between hard and easy puzzles for these variations in the moment.

[m_b_metcalf]

Now I dare to enter the vast 25x25 territory. The first puzzle is an easy one:

Code: Select all

  .  2  .  5  . 20  .  . 24  . 17  .  .  .  6  .  1  .  . 14  .  4  .  8  .
  .  .  .  .  8  .  .  5  .  .  . 23  1 20  .  .  . 18  .  . 11  .  .  .  .
  4 10  . 11  .  . 19  3  7 22 14  9  .  8 21 25 12  2 17  .  . 13  . 24  5
 14  7 15  .  . 12  .  .  .  8 24  .  .  . 10  3  .  .  .  9  .  .  6  2 17
 20  .  . 12  .  .  .  . 13 23  . 16  2 11  . 10  4  .  .  .  .  1  .  . 14
  . 25  .  . 12  .  .  1  .  .  4  .  .  . 11  .  . 20  .  . 18  .  . 22  .
  .  .  .  .  .  .  .  .  .  .  .  .  6  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  . 18  .  .  .  .  .  .  .  .  .  .  .  .
  6  . 17 15  1 18 12  .  .  . 22  . 21  . 23  .  .  . 16 11 20  2 10  . 13
  .  .  . 21  .  .  .  .  .  .  .  .  9  .  .  .  .  .  .  .  .  6  .  .  .
  .  . 11 13 23  . 17  . 12  .  . 19  . 24  .  . 21  . 20  .  6 15  1  .  .
  . 21  1 19  .  . 13  9 15  .  .  .  5  .  .  . 16 22 25  .  . 11  8 14  .
  . 16  .  .  .  . 24 19  1  .  9 20  .  2 22  .  5 12  6  .  .  .  .  3  .
  . 18  2  7  .  . 16 14  8  .  .  . 25  .  .  . 19  1 13  .  . 24 17 12  .
  .  . 12 22 25  . 20  .  2  .  . 21  . 18  .  . 14  .  3  . 19  9  5  .  .
  .  .  .  9  .  .  .  .  .  .  .  . 11  .  .  .  .  .  .  .  . 19  .  .  .
 12  . 14  6 10 19  9  .  .  . 13  .  3  .  2  .  .  . 21  8  4  7 20  . 15
  .  .  .  .  .  .  .  .  .  .  .  . 22  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  7  .  .  .  .  .  .  .  .  .  .  .  .
  . 15  .  . 16  .  .  7  .  . 12  .  .  . 14  .  .  4  .  .  8  .  . 18  .
  8  .  . 17  .  .  .  .  4 16  .  2 13 25  .  1 20  .  .  .  .  5  .  . 23
 18 12  5  .  .  6  .  .  . 10  7  .  .  .  9 14  .  .  .  3  .  . 16 13  2
 21  9  .  2  .  .  5 18 25 19 11  3  . 12 20  7 17  8 10  .  . 14  . 15  4     Forbidden pairs: 1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9, …, 25-1, also on the diagonals.
  .  .  .  . 24  .  . 12  .  .  . 14 23 15  .  .  . 21  .  .  9  .  .  .  .
  .  1  . 20  . 11  .  .  3  .  8  .  .  . 19  .  2  .  . 16  . 12  .  7  .     XNC+sudokuNC+, 234 givens, easy, symmetric, empty diagonals, not minimal.

Since it is easy, a printable version is attached below. It can also be solved without the XNC+ property (just X), but is then hard (SE ~7 - 8).

The next is much harder:

Code: Select all

  .  2  .  5  . 20  .  . 24  .  .  .  .  .  .  .  1  .  . 14  .  4  .  8  .
  .  .  .  .  8  .  .  5  .  .  . 23  1 20  .  .  . 18  .  . 11  .  .  .  .
  4 10  . 11  .  . 19  3  7 22 14  9  .  8 21 25 12  2 17  .  . 13  . 24  5
 14  7 15  .  . 12  .  .  .  8 24  .  .  . 10  3  .  .  .  9  .  .  6  2 17
 20  .  . 12  .  .  .  . 13 23  . 16  . 11  . 10  4  .  .  .  .  1  .  . 14
  . 25  .  . 12  .  .  1  .  .  4  .  .  . 11  .  . 20  .  . 18  .  . 22  .
  .  .  .  .  .  .  .  .  .  .  .  .  6  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  . 18  .  .  .  .  .  .  .  .  .  .  .  .
  6  . 17 15  1 18 12  .  .  . 22  . 21  . 23  .  .  . 16 11 20  2 10  . 13
  .  .  . 21  .  .  .  .  .  .  .  .  9  .  .  .  .  .  .  .  .  6  .  .  .
  .  . 11 13 23  . 17  .  .  .  . 19  . 24  .  .  .  . 20  .  6 15  1  .  .
  . 21  1 19  .  . 13  9 15  .  .  .  5  .  .  . 16 22 25  .  . 11  8 14  .
  . 16  .  .  .  . 24 19  1  .  9 20  .  2 22  .  5 12  6  .  .  .  .  3  .
  . 18  2  7  .  . 16 14  8  .  .  . 25  .  .  . 19  1 13  .  . 24 17 12  .
  .  . 12 22 25  . 20  .  .  .  . 21  . 18  .  .  .  .  3  . 19  9  5  .  .
  .  .  .  9  .  .  .  .  .  .  .  . 11  .  .  .  .  .  .  .  . 19  .  .  .
 12  . 14  6 10 19  9  .  .  . 13  .  3  .  2  .  .  . 21  8  4  7 20  . 15
  .  .  .  .  .  .  .  .  .  .  .  . 22  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  7  .  .  .  .  .  .  .  .  .  .  .  .
  . 15  .  . 16  .  .  7  .  . 12  .  .  . 14  .  .  4  .  .  8  .  . 18  .
  8  .  . 17  .  .  .  .  4 16  .  2  . 25  .  1 20  .  .  .  .  5  .  . 23
 18 12  5  .  .  6  .  .  . 10  7  .  .  .  9 14  .  .  .  3  .  . 16 13  2
 21  9  .  2  .  .  5 18 25 19 11  3  . 12 20  7 17  8 10  .  . 14  . 15  4    Forbidden pairs: 1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9, …, 25-1, also on the diagonals.
  .  .  .  . 24  .  . 12  .  .  . 14 23 15  .  .  . 21  .  .  9  .  .  .  .
  .  1  . 20  . 11  .  .  3  .  .  .  .  .  .  .  2  .  . 16  . 12  .  7  .    XNC+sudokuNC+, 224 givens, SE ~9 (v. hard), symmetric, empty diagonals, probably not minimal.

with a version for tarek:

Code: Select all

.2.5.K..P.......1..E.4.8.
....8..5...N1K...I..B....
4A.B..J37ME9.8LQC2H..D.P5
E7F..C...8P...A3...9..62H
K..C....DN.G.B.A4....1..E
.Q..C..1..4...B..K..I..M.
............6............
............I............
6.HF1IC...M.L.N...GBK2A.D
...L........9........6...
..BDN.H....J.P....K.6F1..
.L1J..D9F...5...GMQ..B8E.
.G....PJ1.9K.2M.5C6....3.
.I27..GE8...Q...J1D..PHC.
..CMQ.K....L.I....3.J95..
...9........B........J...
C.E6AJ9...D.3.2...L847K.F
............M............
............7............
.F..G..7..C...E..4..8..I.
8..H....4G.2.Q.1K....5..N
IC5..6...A7...9E...3..GD2
L9.2..5IQJB3.CK7H8A..E.F4
....P..C...ENF...L..9....
.1.K.B..3.......2..G.C.7.

Hope that's of some interest. I'm taking two long train journeys next week, so I've printed the 16x16 from a previous post to while away the time.

Regards,

Mike

[tarek]

In keeping with Easy & not minimal theme These 16x16 puzzles (subject to verification) need the X, XNC & NC+ to solve. If that is the case then they will be useful for testing constraints, minimization & even P&P solving

Code: Select all

.3....8.......C.468..FB.CE5...19.9....E..G.........F5......A.......D2......CA....2....7..F....3...4..C.D..A...F.......A..B....4..C.......2....9.5F7..D36B4.....2.........1....A....8E.......F......63......4..........4..5......2.E..A.F9C.......4....C..8....7.
.3....8.......C.468..FB.CE5...19.9....E..G.........F5......A.......D2......CA....2....7..F....3...4..C.D..A...F.......A..B....4..C.......2....9.5F7..D36B4.....2.........1....A....8E......7F......63.................4..5......2.E..A.F9C.......4....C..8....7.


[tarek]

As far as I can tell, and you chaps might be able to confirm this with your solvers, there is NO 9x9 SudokuNC grid which has both the X-property and the XNC property.

You just need to look at r5c5 to get your answer

[m_b_metcalf]

In keeping with Easy & not minimal theme These 16x16 puzzles (subject to verification) need the X, XNC & NC+ to solve. If that is the case then they will be useful for testing constraints, minimization & even P&P solving

Code: Select all

.3....8.......C.468..FB.CE5...19.9....E..G.........F5......A.......D2......CA....2....7..F....3...4..C.D..A...F.......A..B....4..C.......2....9.5F7..D36B4.....2.........1....A....8E.......F......63......4..........4..5......2.E..A.F9C.......4....C..8....7.
.3....8.......C.468..FB.CE5...19.9....E..G.........F5......A.......D2......CA....2....7..F....3...4..C.D..A...F.......A..B....4..C.......2....9.5F7..D36B4.....2.........1....A....8E......7F......63.................4..5......2.E..A.F9C.......4....C..8....7.


Here's a reduced version of the first one, which is very easy, with 62 clues, SE ~ 9 and close to minimal:

Code: Select all

  .  3  .  .  .  .  8  .  .  .  .  .  .  . 12  .
  4  6  8  .  . 15 11  .  . 14  5  .  .  .  1  9
  .  9  .  .  .  . 14  .  . 16  .  .  .  .  .  .
  .  .  . 15  5  .  .  .  .  .  . 10  .  .  .  .
  .  .  . 13  2  .  .  .  .  .  . 12 10  .  .  .
  .  2  .  .  .  .  7  .  . 15  .  .  .  .  3  .
  .  .  4  .  . 12  . 13  .  . 10  .  .  . 15  .
  .  .  .  .  .  . 10  .  . 11  .  .  .  .  4  .
  . 12  .  .  .  .  .  .  .  .  .  .  .  .  9  .
  5 15  7  .  . 13  3  . 11  .  .  .  .  .  .  2
  .  .  .  .  .  .  .  .  .  1  .  .  .  . 10  .
  .  .  .  8 14  .  .  .  .  .  .  . 15  .  .  .
  .  .  .  6  3  .  .  .  .  .  .  4  .  .  .  .
  .  .  .  .  .  .  4  .  .  5  .  .  .  .  .  .
  2  . 14  .  . 10  . 15  9  .  .  .  .  .  .  .
  .  4  .  .  .  . 12  .  .  8  .  .  .  .  7  .

Regards,

Mike