The New Sudoku Players' Forum

by **tarek** » Thu Jun 20, 2019 6:48 pm

Mathimagics wrote:A challenge therefore suggests itself - making puzzles that are even worse! How far can we go, making valid puzzles that take even more time for software solvers?

That is awful because of how time consuming it would be :evil:

I will try to dig up the worst case I posted to see how it compares

by **tarek** » Thu Jun 20, 2019 8:15 pm

This was posted almost 11 years ago so don't hate me if turns out to be easy according to your standards.

It was from an "unsolvable list" designed as machine defeating - at the time -
http://rcbroughton.co.uk/sudoku/forum/viewtopic.php?f=3&t=434
this is the one that took the longest

Unsolvable 41

code: Show

tarek

by **Mathimagics** » Fri Jun 21, 2019 2:51 am

Tarek's example is definitely harder for both SumoCue and JSudoku:

Code: Select all: Case JSudoku SumoCue --------------------------------------------- Wecoc Sample puzzle 330s 280s Tarek "Unsolvable #41" 611s 825s

SumoCue is a pain to test because it doesn't report any information on the solving process. It needs an observer with a stopwatch to get the time.

I don't expect to be able to find any harder examples until I have a suitably efficient and capable solver, which can then explore sum/cage perturbations, looking for harder puzzles.

by **tarek** » Fri Jun 21, 2019 5:37 pm

From memory: I tried to explore those difficult puzzles by constructing the the busiest starting position (Number of candidates out of 729). This was achieved using cages with number of cells having the most possibilities then going further with perturbations that result in cages with a cell number / sum with the most possibilities. Unsolvable #41 is an example towards that. If you find a way to rate them faster, you will find more difficult puzzles no doubt.

tarek

by **creint** » Fri Jun 21, 2019 5:48 pm

Weccoc, you a made mistake with your last 4 hidden cages, sum values 36, 42, 42, 48 don't match with the solution from Mathimatics.

by **Wecoc** » Fri Jun 21, 2019 6:31 pm

creint wrote:Weccoc, you a made mistake with your last 4 hidden cages, sum values 36, 42, 42, 48 don't match with the solution from Mathimatics.

Fixed. Sum values were ok but I forgot to paint one cell in each, sorry. Well spotted!

tarek wrote:I had a play with creating “the most difficult killer” before.

Very nice one tarek

Curious how SumoCue wins with mine, but JSudoku wins with yours.

Mathimagics wrote:Curiously, JSudoku reports "Unique solution found with 35 guesses" ??

Maybe that would be a better way to rate them?

Or the number the of nodes traversed...
Processing time is computer-dependent, that's why I would avoid using that.

I have a few other "very hard" ones like that one, I'll be testing them later.

by **Mathimagics** » Sat Jun 22, 2019 3:50 am

Wecoc wrote:Maybe [guesses] would be a better way to rate them? Or the number the of nodes traversed...
Processing time is computer-dependent, that's why I would avoid using that.

Adding a few more samples from Tarek's collection demonstrates that "guesses" reported by JSudoku is poorly correlated with time, and that the "number of nodes" is much better:

Code: Select all: Case JS: Guess Nodes Time -------------------------------------------------------- Tarek "Unsolvable #1" 28 227086 6s Tarek "Unsolvable #40" 27 4416433 9s Tarek "Unsolvable #42" 38 110450415 240s Wecoc Sample puzzle #1 35 182765067 409s Tarek "Unsolvable #41" 36 337230898 762s

Relative times on same machine, using same software are still a useful indicator …. note also that the times I first reported for our two best cases - 330s and 611s - turned into 409s and 762s when I retested them to get the node counts!

by **tarek** » Sat Jun 22, 2019 4:13 pm

Rating involves Resolution rules and how to apply them: (breadth 1st or depth 1st). There is an issue with how the solver/rater responds when encountering several isomorphic versions of the same puzzle. If the solver / rater varies wildly then it’s bad news I’m afraid.

If we get to the guessing phase (recursion in one way or another) then again the solver / rater has to stay consistent with isomorphic versions or it could fall foul of the worst case scenario.

tarek

[Added:] Just Checked on JS 3 versions of Unsolvable #40:

Code: Select all: Unsolvable #40 Original: Starting to Check Grid Validity. Be patient this may take several minutes for hard grids... Check Grid Validity done in 8592 milliseconds 4415293 nodes traversed Unique solution found with 27 guesses 90 degrees clockwise rotation: Starting to Check Grid Validity. Be patient this may take several minutes for hard grids... Check Grid Validity done in 7953 milliseconds 3787459 nodes traversed Unique solution found with 31 guesses 180 degrees rotation: Starting to Check Grid Validity. Be patient this may take several minutes for hard grids... Check Grid Validity done in 11031 milliseconds 5429720 nodes traversed Unique solution found with 32 guesses

One way to normalise this is to average the result over a certain number of random transformations (well in this case all the transformations are 8

) which is similar to what Suxratt does! the problem is that this will again prolong an already time-consuming process :cry:

by **Wecoc** » Sat Jun 22, 2019 8:37 pm

tarek wrote:Rating involves Resolution rules and how to apply them: (breadth 1st or depth 1st). There is an issue with how the solver/rater responds when encountering several isomorphic versions of the same puzzle. If the solver / rater varies wildly then it’s bad news I’m afraid.

This is because the solver starts the guessing from the first cell and continues until it finds the next useful cell, right?

On the Ruby-based solver I made a few ago for default sudoku , I kind of solved this by defining which ones should be looked first.
It sorts the cells by the number of candidates they have, starting with the lowest. That also accelerates the process a bit.
Many cells will have the same number of possible candidates: in that case those are still ordered by coordinate so it's not totally fixing the problem, but it may considerably reduce the variability between isomorphs.

Piece of code: Show

Sorry if I'm talking nonsense, there might be better ways to approach this.

--

Good news! I found a harder flower, but it's still easier than tarek's Unsolvable #41.
Even if it's computally harder to process than first one, houses, pseudo-houses and similar tricks might be a bit more useful in this one.

Flower #2

Code: Select all: .--.-----.-----------.-----. |10|20 |25 |11 | | | | .--------+-----: | | | |20 |20 | :--+--.--'--'--. .--: | |25|20|25 | |25| | | | '--. .--'--' :-----: | | | | |25 | | | .--: :--.--. :--. | | | |25| |2 |25| |20| | | '--: '--'--: :--' | | | | | | | | :-----: .--.--' '--. | | |21 | |20| | | | | :--' '--.--.--'--+--: | | |25|20 |11| :-----+--------' | | | |10 | | | | '-----'-----------'-----'--'

Code: Select all: 3x3::k:2561:5122:5122:6403:6403:6403:6403:2820:2820:2561:5122:5122:6403:5125:5125:5125:5126:5126:6410:5129:6408:6408:6408:5125:6407:5126:5126:6410:5129:5129:6408:6407:6407:6407:6415:6415:6410:5129:6411:6408:524:6413:6407:5134:6415:6410:6410:6411:6411:6411:6413:5134:5134:6415:5397:5397:6411:5139:6413:6413:6413:5134:6415:5397:5397:5139:5139:5139:6418:5137:5137:2832:2580:2580:6418:6418:6418:6418:5137:5137:2832:

Code: Select all: 724524 ms (463173 ms on Flower #1) 254362226 nodes traversed Unique solution found with 39 guesses

by **Mathimagics** » Sun Jun 23, 2019 2:05 am

Code: Select all: Case JS: Guess Nodes Time -------------------------------------------------------- Tarek "Unsolvable #42" 38 110450415 240s Wecoc Sample puzzle #1 35 182765067 409s Wecoc Sample puzzle #2 39 254326421 455s Tarek "Unsolvable #41" 36 337230898 762s

Puzzle rating is a notoriously complex and inexact science. Puzzle ranking using a particular solver is the best we can do with these puzzles, I think.

Wecoc wrote:On the Ruby-based solver I made a few ago for default sudoku , I kind of solved this by defining which ones should be looked first.
It sorts the cells by the number of candidates they have, starting with the lowest. That also accelerates the process a bit.
Many cells will have the same number of possible candidates: in that case those are still ordered by coordinate so it's not totally fixing the problem, but it may considerably reduce the variability between isomorphs.

Most DFS (depth-first search) use some form of this. The problem of "which cell next?" (the next cell selection strategy) is itself an area of complexity, even for standard Sudoku. What to do when you have many cells with the least NPV (number of possible values)?

Your puzzles start with one given, which eliminates a single value in row and column. Some other single eliminations can be made from the 2-cell cages, but we still wind up with 29 choices for "best cell" candidate, each with NPV = 8.

With Killers, much like Kakuro, we need to look beyond single cell candidates. Tarek's #41 puzzle offers more candidate eliminations, but it has no small cages. A cage of size 2 will always be better because you know any guess will immediately force 2 values, so the next cell strategy needs to be more subtle.

The isomorphic variations Tarek mentioned above will always occur when there is more than one cell with minimum NPV. Most solvers will simply take the first cell in the list, there being no other way to distinguish between them. Rotating/reflecting the original puzzle will result in an essentially-different cell being chosen, and this might be a better choice, or a worse one.

by **Mathimagics** » Sun Jun 23, 2019 3:07 am

We have a new leader! 8-)

I took Wecoc's first example, and tested the 4 ways that the central cell can be combined with a neighbouring cage. Only one of these produced a valid puzzle (modification A), which is a leader in its own right. Modification B, while it has multiple solutions, is even "better", taking the longest time of all to find the first 2 solutions.

Modification A: 1(1) + 5(2) => 6(3)

Wecoc 1a: Show

Modification B: 1(1) + 17(2) => 18(3)

Wecoc 1b: Show

Code: Select all: Case JS: Guess Nodes Time -------------------------------------------------------- Tarek "Unsolvable #42" 38 110450415 240s Wecoc Sample puzzle #1 35 182765067 409s Wecoc Sample puzzle #2 39 254326421 455s Tarek "Unsolvable #41" 36 337230898 762s Wecoc #1 mod A 37 535023523 967s Wecoc #1 mod B ? 1557326455 2825s (MS)

The guess count for mod B is missing because I was using "Check Grid Validity" (rather than "Recursively Solve") to ensure that no more than 2 solutions would be searched for. With this option JSudoku does not report the guess count.

by **Wecoc** » Mon Jul 01, 2019 7:13 pm

Mathimagics wrote:Your puzzles start with one given, which eliminates a single value in row and column.

That surely has effect on the difficulty. Also using the same cage distribution I used there may be harder unique puzzles, we are talking about a "human versus machine" situation here, so a better programming process on setting those puzzles would make this cleaner.

For now all I did was applying some rules:
- Multi-box cages
- Rotational symmetry
- Cages with sum near to 5N (N being the number of cells)
- Cages with N near to 5*

Maybe the symmetry rule is less obvious, but in the other ones it's easy to see why they increase the puzzle difficulty.

*Note: In terms of combinations of numbers that add up to 5N (midpoint), it's higher when N is 5. In the other hand, the permutations of the numbers inside the cage increase when the cage is higher, so the optimal N that has more "ambiguity of the clue" (or difficulty) would be around 7 or 8. Sadly it's not as obvious as that, because bigger cages often have more useful hidden houses that decrease the difficulty, that's why I stick with 5 as optimal cage size. Very weird-shaped big cages would be an exception to that.

Mathimagics wrote:I took Wecoc's first example, and tested the 4 ways that the central cell can be combined with a neighbouring cage.

I tried the same on Flower #2 but they all have multiple solutions (luckly this one was faster to test)

by **sigh** » Thu Oct 07, 2021 9:27 am

I've made a browser-based brute-force solver (at https://sigh.github.io/Interactive-Sudoku-Solver/) which can handle the puzzles in this thread reasonably quickly. I'd be keen to know if these are still considered the hardest killers for solving programs?

I've given Chrome and Firefox timings on my computer since the browser type seems to make a big difference:

Code: Select all: Case Chrome Firefox ------------------------------------ Wecoc #1 1.6s 2.3s Wecoc #1 mod A 4.1s 6.1s Wecoc #1 mod B * 10.4s 15.9s Wecoc #2 .7s 1.1s tarek unsolvable #41 .1s 0.2s

* Wecoc #1 mod B has 6 solutions, the time given is time taken to disprove uniqueness. My solver takes 18s to find all 6.

Links to the puzzles in my solver: Wecoc #1 Wecoc #1 mod A Wecoc #1 mod B Wecoc #2 tarek unsolvable #41

I also ran it on tarek's set of 42 (from http://rcbroughton.co.uk/sudoku/forum/v ... ?f=3&t=434) and it took ~2s to finish them all (on Chrome):

Solve times: Show

The "Load from text" box on the solver understands the input formats used in this thread, so it should be easy to try other puzzles if you have them.

I would love to know about any harder puzzles.

The New Sudoku Players' Forum

Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]

Re: Killing with flowers [Killer Sudoku]