The New Sudoku Players' Forum

[m_b_metcalf]

The basic idea of my program is: Symplifiy with basic methods and if not solved, use SAT to do the rest.

The basic methods imply uniqueness. I assume that your SAT set-up also somehow assures uniqueness (I'm not at all familiar with this technique).

Regards,

Mike Metcalf

[hkociemba]

The basic idea of my program is: Symplifiy with basic methods and if not solved, use SAT to do the rest.

The basic methods imply uniqueness. I assume that your SAT set-up also somehow assures uniqueness (I'm not at all familiar with this technique).

SAT solving is really cool and easy to set up. To ensure uniqueness you add the negation of the solution found to the SAT clauses and then solving again with SAT must give back UNSATISFIABLE.
Btw. I gave your 81x81 symmetric soduko with 3958 clues a try and tried to reduce it from scratch using the fully filled grid. But I do not get below 3400. Reducing your 3958 clue puzzle with SAT is possible but removing more than 8 entries makes the SAT-solver grind endlessly. If I find still find something substantial under 3958 I can post it if you want.

[m_b_metcalf]

To know better for which NxN my approach is most effective to reduce given puzzles maybe you can give me some hard puzzle examples of different sizes and I let program work on them and look if and how many entries I still can remove. Up to now I made this quite unsystematically just grabbing some examples from this forum. I also took a look at blues ultimate 16x16. Those I tried are optimal in the sense that no further given can be removed.

I have posted pretty well everything I ever produced. However, I attach a recent 100x100 that, notwithstanding the fact I still have to implement hidden triples, appears quite hard, even though it has relatively many givens. Let me know how long it takes to solve and whether you can reduce it more.

Yes, blue's ulimate puzzles are, indeed, minimal (as it's called).

Regards,

Mike Metcalf

[hkociemba]

I attach a recent 100x100 that, notwithstanding the fact I still have to implement hidden triples, appears quite hard, even though it has relatively many givens. Let me know how long it takes to solve and whether you can reduce it more.

The SAT solves it within less than a second. I then removed random cells one by one and "resolved" the puzzle, looking for uniqueness. What is interesting that from the 88 cells I removed only two had to be reinserted because the solution was not unique any more. Thas is the reason why I believe that in prinziple many more cells can be removed. But have a look at the solving times (givens/time in s):
6584/0.4
6568/0.5
6555/0.7
6544/1
6532/2
6524/6
6517/10
6508/25
6505/34
6503/72
6502/45
6501/40
6500/35
6499/53
On average the times increase, but not necessarily monotone. I stopped with 6499 givens, the result is attached.
Another statistics: With your original puzzle, applying the standard methods inclusive quadruples 2803 cells cannot be filled, after removing the 86 givens 3107 cells cannot be filled with the standard methods.

[hkociemba]

Reducing from the solution with 10000 givens without SAT only with standard methods including triples I get the following puzzle with 5848 givens which is optimal in the sense that removing any entry makes it invalid or unsolvable using the standard methods including triples.
Edit: To make the puzzle optimal including quadruples only 8 additional entries had to be removed.

[m_b_metcalf]

Reducing from the solution with 10000 givens without SAT only with standard methods including triples I get the following puzzle with 5848 givens which is optimal in the sense that removing any entry makes it invalid or unsolvable using the standard methods including triples.

Thanks for looking at this puzzle. Here we agree that it requires methods beyond basics. In fact, it is the first puzzle of this type that I have generated that is so hard. Based on experience with 9x9s, I estimate that it would have an SE rating of ~9.0.

However, your new, triplet-minimal version presents me with the same problem as the 144x144s. Although I don't (yet) have hidden triplets in the solution chain, the back-up technique also fails to find a solution, presenting symptoms of the puzzle having multiple solutions, which you assure me it doesn't. This I must investigate further. At least this puzzle is easier to handle than its bigger144x144 brothers. In fact, it would perhaps help with my diagnostics if you could make a few 9x9 and 16x16 puzzles available.

Thanks,

Mike Metcalf

[Pat]

I must investigate further.

it would perhaps help with my diagnostics
if you could make a few 9x9 and 16x16 puzzles available.

for diagnostics, try

1....23...4..5..6...53....7..84.5...............1.68..6....41...3..8..2...97....4
m_b_metcalf # 289 # 22
(24 givens in 9-squared cells)

and hkociemba, i'm curious as to the # of iterations for this puzzle
( allowing as before: singles,intersections,pairs,triples )

[m_b_metcalf]

for diagnostics, try
1....23...4..5..6...53....7..84.5...............1.68..6....41...3..8..2...97....4

No, that's not the point. For testing hidden triplets I will use all the puzzles with a 4.0 in the rating that I ever submitted to the Patterns Game (one is not enough).

What I'm getting at is that hkociemba has solved all the massive standard and X puzzles that I have posted, but I cannot solve any of his. So I need some smaller ones from his generator to look for some clue as to what's up.

Regards,

Mike Metcalf

[hkociemba]

and hkociemba, i'm curious as to the # of iterations for this puzzle
( allowing as before: singles,intersections,pairs,triples )

Regards,
Herbert Kociemba

[Pat]

thanks!
how many iterations ?

i was trying to decipher your code snippet,
apparently i mis-interpreted n_cand_set

[hkociemba]

thanks!
how many iterations ?

i was trying to decipher your code snippet,
apparently i mis-interpreted n_cand_set

4 iterations. n_cand_set=DIM3 just asks if the cells are completely filled.

[hkociemba]

In fact, it would perhaps help with my diagnostics if you could make a few 9x9 and 16x16 puzzles available.

It is more difficult than I thought to find 9x9 or 16x16 with the properties I want. I want to have puzzles which are pair-optimal but not triple-optimal and the triple-optimal should not be overall optimal. In most oft the times when the puzzle is pair-optimal it is also triple-optimal or the triple_optimal is also overall optimal. But here is one whith the desired properties:

Code: Select all

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

Number of givens: 93

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

Number of givens: 92, 8 in first row removed

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

Number of givens: 91, 12 in 6. row removed


In the first puzzle any removal makes the puzzle unsolvable with standard methods including pairs.
In the second puzzle any removal makes the puzzle unsolvable with standard methods including triples.
In the third puzzle any removal makes the puzzle ambiguous.
Tell me if that helps, else I construct some other puzzles.

[hkociemba]

And here is the same for a 25x25, again pair-optimal, triple-optimal and overall optimal. Up to 25x25 it takes only a few minutes to generate the optimal grids and it is much easier to find working examples with 25x25.

Code: Select all

  .  . 21  .  .  5  .  .  . 12 18  .  . 16  .  .  4 14  .  1 20  .  .  . 17
  4  .  .  . 10  9  . 21 23 24 19  .  . 25  . 15  .  . 20  .  3  .  8  . 16
  . 18  .  7  3  .  .  6  . 15  .  . 13  .  .  .  . 11  .  .  .  .  . 24  .
  . 19  . 12  5  . 18  8  .  . 22  . 15 17 20  .  .  .  9  .  .  .  .  .  4
 17 22  6 15  .  .  .  .  .  .  . 21  .  .  .  7  .  8  3  .  . 19  . 12  .
  .  .  .  .  7  .  .  .  .  . 14  .  . 22  .  .  2  9 12 11 24  .  .  .  .
  .  .  . 17  .  .  .  .  .  . 21  .  .  1 24  . 19  5  .  8  .  .  9  .  2
  .  .  9  . 12  .  8  . 19 16  .  3  .  .  .  .  .  .  . 21 13 14 20  .  .
  .  . 20  4  . 24 21  .  1 23  .  9 25  2  .  .  .  3  .  .  7  .  . 16  .
  . 21 10  .  .  .  .  .  .  .  8  . 16  .  .  4 22  . 13 14  .  .  . 17  .
  . 24 23 21  .  . 12  .  9 11  .  .  .  . 18  .  .  .  .  . 22  .  .  .  3
  5  . 16  .  . 22 15  .  .  . 13  .  .  .  .  .  9  .  . 12  2  . 23 21  .
  3  . 17  .  .  1  .  . 20 14 24  .  .  .  2  .  .  .  .  .  . 12  .  .  .
  .  .  . 14  .  .  .  .  .  .  . 25 11  . 19  .  . 17  . 15 18  7  .  8  5
  9  .  .  . 19  .  7 16  .  8  . 17  6  .  .  . 10  .  2 24  .  .  . 14  .
 14 10 13  . 23 25  .  . 21  2  .  .  . 11  . 22  6  .  . 20 17  .  .  .  .
  8  .  .  .  .  .  . 15  .  .  . 13  1  . 23  .  . 12  .  .  .  .  .  .  .
  6 20  .  .  4 23  . 13 14  .  .  .  .  .  .  .  .  .  .  .  .  5 12 19  .
  .  .  .  2 25 16  5  . 11 19  .  7 18  8  .  1  .  . 23 10  .  . 15 22  .
 11  . 12  .  . 17  3  .  .  . 20 15 22  6  4  .  .  . 25  9  .  .  .  1  .
  . 17  .  .  6 14  . 22 15  . 23  .  .  . 21  5 12 19  8  . 11 25  2  9  .
 13  .  1 10  .  .  .  .  .  . 16 19  5 12  8 20 15  .  .  4  .  . 18  .  .
  .  .  .  9 11  .  .  .  .  .  . 18  3  .  6  .  .  .  .  . 14  4  .  .  .
  .  . 22 20  .  .  .  . 13 10  .  .  .  . 11  .  7  .  6 17  .  .  .  .  .
  . 16  .  .  8  . 17 18  7  3  4  .  . 15  .  . 24  2  .  .  . 23  .  . 13

Number of givens: 255

  .  . 21  .  .  5  .  .  . 12 18  .  . 16  .  .  4 14  .  1 20  .  .  . 17
  4  .  .  . 10  9  . 21 23 24 19  .  . 25  . 15  .  . 20  .  3  .  8  . 16
  . 18  .  7  3  .  .  6  . 15  .  . 13  .  .  .  . 11  .  .  .  .  . 24  .
  . 19  . 12  5  . 18  8  .  . 22  . 15 17 20  .  .  .  9  .  .  .  .  .  4
 17 22  6 15  .  .  .  .  .  .  . 21  .  .  .  7  .  8  3  .  . 19  . 12  .
  .  .  .  .  7  .  .  .  .  . 14  .  . 22  .  .  2  9 12 11 24  .  .  .  .
  .  .  . 17  .  .  .  .  .  . 21  .  .  1 24  . 19  5  .  8  .  .  9  .  2
  .  .  9  . 12  .  8  . 19 16  .  3  .  .  .  .  .  .  . 21 13 14 20  .  .
  .  . 20  4  . 24 21  .  1 23  .  9 25  2  .  .  .  3  .  .  7  .  . 16  .
  . 21 10  .  .  .  .  .  .  .  8  . 16  .  .  4 22  . 13 14  .  .  . 17  .
  . 24 23 21  .  . 12  .  9 11  .  .  .  . 18  .  .  .  .  . 22  .  .  .  3
  5  . 16  .  . 22 15  .  .  . 13  .  .  .  .  .  9  .  . 12  2  . 23 21  .
  3  . 17  .  .  1  .  . 20 14 24  .  .  .  2  .  .  .  .  .  . 12  .  .  .
  .  .  . 14  .  .  .  .  .  .  . 25 11  . 19  .  . 17  . 15 18  7  .  8  5
  9  .  .  . 19  .  7 16  .  8  . 17  6  .  .  . 10  .  2 24  .  .  .  .  .
 14 10 13  . 23 25  .  . 21  2  .  .  . 11  . 22  6  .  . 20 17  .  .  .  .
  8  .  .  .  .  .  . 15  .  .  . 13  1  . 23  .  . 12  .  .  .  .  .  .  .
  6 20  .  .  4 23  . 13 14  .  .  .  .  .  .  .  .  .  .  .  .  5 12 19  .
  .  .  .  2 25 16  5  . 11 19  .  7 18  8  .  1  .  . 23 10  .  . 15 22  .
 11  . 12  .  . 17  3  .  .  . 20 15 22  6  4  .  .  . 25  9  .  .  .  1  .
  . 17  .  .  6 14  . 22 15  . 23  .  .  . 21  5 12 19  8  . 11 25  2  9  .
 13  .  1 10  .  .  .  .  .  . 16 19  5 12  8 20 15  .  .  4  .  . 18  .  .
  .  .  .  9 11  .  .  .  .  .  . 18  3  .  6  .  .  .  .  . 14  4  .  .  .
  .  . 22 20  .  .  .  . 13 10  .  .  .  . 11  .  7  .  6 17  .  .  .  .  .
  . 16  .  .  8  . 17 18  7  3  4  .  . 15  .  . 24  2  .  .  . 23  .  . 13

Number of givens: 254

  .  . 21  .  .  5  .  .  . 12 18  .  . 16  .  .  4 14  .  1 20  .  .  . 17
  4  .  .  . 10  .  . 21 23 24 19  .  . 25  . 15  .  . 20  .  3  .  8  . 16
  . 18  .  7  3  .  .  6  . 15  .  . 13  .  .  .  . 11  .  .  .  .  . 24  .
  . 19  . 12  5  . 18  8  .  . 22  . 15 17 20  .  .  .  9  .  .  .  .  .  4
 17 22  6 15  .  .  .  .  .  .  . 21  .  .  .  7  .  8  3  .  . 19  . 12  .
  .  .  .  .  7  .  .  .  .  . 14  .  . 22  .  .  2  9 12 11 24  .  .  .  .
  .  .  . 17  .  .  .  .  .  . 21  .  .  1 24  . 19  5  .  8  .  .  9  .  2
  .  .  9  . 12  .  8  . 19 16  .  3  .  .  .  .  .  .  . 21 13 14 20  .  .
  .  . 20  4  . 24 21  .  1 23  .  9 25  2  .  .  .  3  .  .  7  .  . 16  .
  . 21 10  .  .  .  .  .  .  .  8  . 16  .  .  4 22  . 13 14  .  .  . 17  .
  . 24 23 21  .  . 12  .  9 11  .  .  .  . 18  .  .  .  .  . 22  .  .  .  3
  5  . 16  .  . 22 15  .  .  . 13  .  .  .  .  .  9  .  . 12  2  . 23 21  .
  3  . 17  .  .  1  .  . 20 14 24  .  .  .  2  .  .  .  .  .  . 12  .  .  .
  .  .  . 14  .  .  .  .  .  .  . 25 11  . 19  .  . 17  . 15 18  7  .  8  5
  9  .  .  . 19  .  7  .  .  8  . 17  6  .  .  . 10  .  2 24  .  .  .  .  .
 14 10 13  . 23 25  .  . 21  2  .  .  . 11  . 22  6  .  . 20 17  .  .  .  .
  8  .  .  .  .  .  . 15  .  .  . 13  1  . 23  .  . 12  .  .  .  .  .  .  .
  6 20  .  .  4 23  .  . 14  .  .  .  .  .  .  .  .  .  .  .  .  5 12 19  .
  .  .  .  2 25 16  5  . 11 19  .  7 18  8  .  1  .  . 23 10  .  . 15 22  .
 11  . 12  .  . 17  3  .  .  . 20 15 22  6  4  .  .  . 25  9  .  .  .  1  .
  . 17  .  .  6 14  . 22 15  . 23  .  .  . 21  5 12 19  8  . 11 25  2  9  .
 13  .  1 10  .  .  .  .  .  . 16 19  5 12  8 20 15  .  .  4  .  . 18  .  .
  .  .  .  9 11  .  .  .  .  .  . 18  3  .  6  .  .  .  .  . 14  4  .  .  .
  .  . 22 20  .  .  .  .  . 10  .  .  .  . 11  .  7  .  6 17  .  .  .  .  .
  . 16  .  .  8  . 17 18  7  3  4  .  . 15  .  . 24  2  .  .  . 23  .  . 13

Number of givens: 250


[m_b_metcalf]

Many thanks for posting these puzzles. That's quite useful. I could solve all the puzzles, but my impression is that they are harder (require more elaborate techniques) than you state in your comments. Thus, would it be possible for you the generate also a few 9x9 puzzles and compare your solution path with the one used by the ultimate arbiter, Sudoku Explainer? I can do that if you prefer.

I note that in the first 16x16

1 12 is redundant
5 3 is redundant
6 15 is redundant
individually, and so it is possible to have
6 15 removed
1 12 removed

In each of the first two 25x25s, at least 1 10 is redundant.

Is that what you find too?

Regards,

Mike Metcalf

[hkociemba]

I do not agree. If I remove e.g. 1 12 (I suppose you mean the 8 in row 1 column 12 by this) the puzzle cannot be solved with only pairs any more. It still can be solved using triples and I checked that in this case it is triple-optimal and you cannot remove any other entry if the puzzle should still be solvable with triples.
With the 25x25 if you remove the 12 in 1/10 you cannot solve it neither with pairs nor with triples any more. I wonder what causes these differences between our opinions.

Ok I will try some 9x9 - hope I can find something interesting.