The New Sudoku Players' Forum

[m_b_metcalf]

The harder ones should contain corners that have as much solutions as possible when filling the shared box from the middle puzzle.

Thanks for your comment. Note that I'm assuming the puzzle is solved using only the 9x9 sub-puzzles, and not a 21x21 technique. Could you perhaps provide a harder example for me to test?

Mike

[creint]

I used the '21x21' global technique.
No I don't have a database of rated puzzles, so I can't provide one.

[Mathimagics]

That's a good point, Mike, about minimality testing, specifically the testing of overlapped corner box clues for redundancy.

But perhaps it's not an obstacle, if we use "0/1" redundancy checking, rather than "1/2". If we remove the clue AND eliminate it as a candidate for that cell, the method should still be usable, I think.

If the clue is redundant there should be no solution found. The "0/1" method is usually more efficient in any case.

Cheers
MM

[m_b_metcalf]

That's a good point, Mike, about minimality testing, specifically the testing of overlapped corner box clues for redundancy.

But perhaps it's not an obstacle, if we use "0/1" redundancy checking, rather than "1/2". If we remove the clue AND eliminate it as a candidate for that cell, the method should still be usable, I think.

If the clue is redundant there should be no solution found. The "0/1" method is usually more efficient in any case.

Cheers
MM

True, but even better is to empty the overlapping regions before starting the process. That anyway makes for a more interesting puzzle, regardless of level of difficulty.

MM (too)

[Mathimagics]

Ok, I think I see what you mean: you can avoid the need for redundancy checks on clues for overlapped cells completely by not having any!

But one would still prefer a solver that supports redundancy checking for any clue … not just the "interesting" cases.

[Mathimagics]

.
OK, time for a performance review!

I have run some benchmark tests with a variety of Samurai puzzles, conventional and exotic (mixed-modes). The bottom line is that 4CS, despite my best efforts, is much, much slower than MSAT (MiniSAT), when used as a minimality checker. The benchmark test was to take a minimal puzzle and verify it by testing each clue for redundancy.

The only puzzle type where 4CS was as fast as SAT, was for conventional Samurai puzzles (standard Sudoku in all grids).

Also, there is a flaw in the algorithm description given above. When testing a corner box setting, we can't use "Corner Puzzle has US" as the condition for inclusion/exclusion. I found one example where a multi-solution setting for the first corner eventually led to a case of multiple solutions for the complete puzzle (thus proving the clue being tested was NOT redundant). Excluding that first corner setting fooled the method into thinking the whole puzzle had only one solution, so it falsely claimed that the clue was redundant.

We have to test all corner-box settings that are valid, ie produce 1 or more corner puzzle solution(s). This increases the iteration / recursion counts considerably …

[m_b_metcalf]

'Bruce',
Thanks for the update. Do you have any puzzles that you regard as being particularly difficult that you could post here, in 5-line format (samurai, X-samurai, windmill, windmill X)? I'd like to use them for testing my own code.

Mike

P.S. If there's a flaw in your original post, will you correct it there too, so that a future reader has all the information in one place?

[Mathimagics]

Cheers, Bruce!

I have added a suitably humble note in the algorithm explanation above.

Cheers,
Bruce

PS: I presume you mean "hard for brute-force solvers"? I can probably knock up some examples that are particularly heavy going for a DLX solver - using standard Samurai/SamuraiX format. I don't do windmills … I fell off one once and hit my head on the sheep dip. Ever since then my brain hurts …

[Mathimagics]

Hi Mike,

Here are 10 minimal puzzles each for Samurai / SamuraiX. Using a DLX solver, the Samurai's take from 0 to 4s to solve, the SamuraiX's take up to 80s.

You will most likely find "harder" examples by doing individual clue removal tests, most puzzles in either set seem to produce examples where the solve time (on my syste,) is 100 to 120s.

Hope this helps …

Samurai: Show

Code: Select all

.92......4...81........9.7..4..3.....65....9.8....7..5..6......2..6.8...5........
...597.3..5.........2.6..........8....94...6..4..19........4.59...6...8........13
.....1......8........9.........7...37..61...4.....8.1...............3............
.........5..2.1....9.......7.6....43..........8.725......592.......3.4..9.317....
.....2..4......379.....8.......6........97..1..8..47...1....2.36...39....9....8..

..8.5..........721...7..4......17.....9...8...2...6.3..9.......8....2....16......
.5..29..76..5.........6.5..2.78...3.......9.4..4..2.1.....3.1.....61.......2.8...
......................5.......79.....4...6...9.6.82..............................
1.6........5.......3.7......421........37.9..6.3...1.5....42..........8.9.7....2.
....9.4.7...6..2.3...8...5...813..2.3....5....1.4........2......47...3..8..97...5

.4.8......9..7.......6.9...2...4...8.19.6..3........57...58....76........2..9....
..1.6..9.6..4.1.8.2....5...8.2.7.................9.315.....2.4................1..
............8.2............7...36..4462..8.....35....9.....3................9....
2.3.......4.9.......9......4...6.......2.1...57....1...6...2.....5.78...9.8..4.5.
.....2......5..1.........9........1.....183...8...75....367.....6......3.2.......

...9...8.4....8....5236....39...4...6..2...4...459.1.............7..5............
.5...6.7......4.......2.531.239...........91.1.............1......8..4......3..8.
.....................76......1.....6....7.8.49....8..5...8.2.................1...
.9.52.........4..............4.8..5.8.19....473....8......4.....1.6.......73.9..1
.......21.............5..3..8..4......9.6.4.2.......5..9..3.5...162..9..5..4.1...

.1.....92...42....39....8........3.8..46....173.....4.....14...2.........5.......
4....9..1.2.73.8..3..1.........6.58........39......7......7.........8.......1....
.....8.......7.............1...3..5.....84.37......6.....4..................2....
..6......28........1.23.......4....8.9..5..4.......9.3..4......7.....68...5.7..1.
.....64................2.7..6..5.1....1...7.....3.79....8.2....29...8.3...74....1

..8......41..9.7..7.5..8.6....2....9....6.....8..1..3.5...71............67.......
.7..1.2...5...3..9..1.............32.4...8..7.6....9.....3..47.....615..........6
...9...................1......6.....7..2.3...3...8........15.....................
...8.......97.....3..........3.7...5617.5..8..8........4.........1....72...2....3
.......5.....3.17.....984....4.29....3....6...1...7....8.4..3.....2.3..5..5.6....

..7..8....5...7.4.32.5....71.9..........7...3.3..2........5.......91....7.53.....
..6.5849.8...963......7......8....4.2.......3.3...5.1........81...7..6......8....
............9.2............1....7....3....94....8....1............5.6............
..61.......9.5....4...7......5.....2.2.....1..6..2.375...4.....37..6...4....92...
.............961.........52.6.1............1..8.2..973.5...3.....9.7......3...59.

4.....19...215..3..36.....4............48..7.3.52..6..7..51....2....7....9.6.....
7...6..3....8.7.1..8.....42...98...4..7....6326....................91.......4....
....5.........2......3..........6...7..83.........7.29...18......................
....3......3..8......421......61293..2.....6....5......1.........4.7...95.9..6.1.
.....1..9...2...........3....85.76.2.....349.6..........1....3.7.2435....6.9..2..

4...1357.........46...5.......3.9..........36..9.85.4.74...........9.............
1.9..5.........49....3....8........9....2...3.73.9..56.....6..2....57.8..........
...2.........7.......9..........23....1....977....85......4......................
738.26....9.................2......4....5..8.........75...936....9.1.....6...2.1.
...9.7...............5..36...76..1.......579.8..1..6..91.....5...2..4......75....

..7.4...93.....4..6...753...8......5.....2..7...8..96..1........3.5......7.......
.....4.58...5...16..9.8...31......4..7.........48....9.....37..........2....7..6.
....9.......1.5............9.2......3.497..8..17.6..........................2....
.3........86......1...7......7..9......85..1..2.....4...5..3.....36....1....153..
........6...8........49..........75..12.4.......28.4.1...1..6...4..3.2..835.....4


SamuraiX: Show

Code: Select all

..9..1.......47...1...5....2.............9..7...56.............6.1..2.....8......
.6......8...1........8...5782......9........4............9.13........4...........
............1......................17...2.6...............9.......73.............
.....8......................5..7.....3..29..5.......6.....6.........423....913.8.
......5....................2.74....6....6...2..4...3..............89.....4.1...5.

...8........9..4.......4.........68.46..79....2................1........69.......
1.....3....3187.5.......7............6...5....9.8....................63.........9
...6........3..............................9.....3.4.5.....7......2..............
....................172.....5.8...7..1.........3...6.437.4.......................
...2...6.....3.7.....6.......4...........8...6......37....1..........34...8......

.6.....2........4.1...4..766.............8.....5..4.................7......6.....
..5...6.....9..3.......3..8.97.2......6.......2..........19.........74...........
....8.........3............3.58.....................3...............6.......14...
....58...7..6.1.......97........936......5.............8...............5.9.....74
.............6...........6.....4..1.851...9..............8.1.3...7...2.....73....

..........3............6.....4...6..59.......7.......8....38.......1.....29.57...
...3.........4..6.47.6..1.3.......1.......6.4..8...2......5..2...................
............8..........5.........4.......63..........8....3................29....
3....5.....................6..7......5.......1......9..2.9......1..4......98.....
......7.....35.......8.............258...1.............6..3...1.....2..7........6

...3.4....2..............6.4.....5....1..7................7................938...
3.....6...1...3.......6.....2......5..3.2.....7......4.......1.......4........73.
.............7.......8................7...9...56...................4.............
7..........15..........8....6..5...7...439.........81....91................2.....
..............8.67.................2...65.........7.93..1.........5........39...8

....5..74.........7..92....9.....8.......53..5.28.................64.............
.....9.7.....7........83..........52.7......9.....7........5..3.....8.9.......6..
...1........................1...9....................2.............9.........5...
.1........4..........7.3.....695.4...31........9..........6.......3..86..........
......2..............2..9..5...7.6.....8...5.4......8......5......39.5...........

..8.....45.1.2..7..7..8..........5....7..........46.1.......................3....
26...74.1...9........5.....7..........6..8..9....461......3....................1.
.....................9......7...8.........................2................3.....
9....1............7...6........4..8.8.....74...2..........9..1....3.6........8..4
....3..7......5..........1..26....8.....2.7...............6...7.3........9....6.4

...1..5...3.89.7..8...2........4...........3.7.......5...................8.......
.......13.5....4..8..6.......51...8.3..8......6...............6........4...9.6...
.............7...............5............4.7........5.............1.............
9...........6.....4.........5..74.6...3...8................9............816......
...4........8..6.....2.................7...6.....2...79.1......3...1..244......8.

..2....3..34.5.1......2..........7.3.98..5......9......4.......6..........9......
....5...4...2.9....47......4.....7...8.....3...9............6.....5.3.......6....
.......................2..............3.....2......9...............6........9....
7..4.........52...............5..8...5.3.7..........9...........3...........8.1..
...3...7..............9.5.2.6....32........917...........6.8..9...........6....3.

..5...91......62......2...8...8........3....7.2........4.......59.......3...9....
9......2...8.....5.7.......1....25.....1..9.........3....3.5.........1.6.....1...
.....................7.................8........25.7......8.................9....
...3..........4....8...........5.....2.9...............6.5......1.73..........8..
....2........3.7.......4.......58.1......2..98......7.......3............1.......


[m_b_metcalf]

'Bruce',

Many thanks for those puzzles; they are very taxing and I had to tweak my program to solve them all. Here's a summary of my findings.


Standard samurai:
puzzles 1 and 3 are nightmares, the hardest I've ever encountered ;
puzzles 2, 5, 8 and 10 are very hard;
the rest are easier.

Timings are from 0.14 to 1.14s.

I made redundancy checks only on puzzle 4, and I think clue 6r10c15 is redundant. Maybe you could check that; maybe it's a false positive.*

X-samurai
All the puzzles are very hard, and take a few seconds to solve.

Regards,

Mike


* It is. If we add 2r7c15 to the puzzle, we find that each of these two clues is, individually, redundant. Thus, when deleting 6r10c15 and guessing 2r7c15 (in an overlap box) it appears that the former is redundant.

[Mathimagics]

I made redundancy checks only on puzzle 4, and I think clue 6r10c15 is redundant. Maybe you could check that; maybe it's a false positive.

If we add 2r7c15 to the puzzle, we find that each of these two clues is, individually, redundant. Thus, when deleting 6r10c15 and guessing 2r7c15 (in an overlap box) it appears that the former is redundant.

Ok, it seems that at least one of us has a bug!

I will double-check that clue/puzzle ...

Cheers
MM (B)

[m_b_metcalf]

* It is.

'It is' referred to the fact that it was a false positive. The clue is not redundant. Sory for any ambiguity.

m

[Mathimagics]

Struth, Bruce!!

I was about to post 2 solutions for that clue removal …

MMB
Dipso ergo sum

[m_b_metcalf]

I have seen no puzzle that fails to yield to a successful guess in just one corner.

Just to point out that your puzzles 1 and 3 are the first exceptions. Well done!

M

[Mathimagics]

Hi Mike,

I assume that you are talking about "guessing" a complete corner-box (overlapped box) setting? Not just a single clue therein …

My generation process starts with a random complete 21x21 grid, then removes all the overlapped-box clues (to make the puzzle "interesting"!).

It can (and should) also test each corner-puzzle to ensure that it actually needs clues in the overlapped box to complete that puzzle.

And finally, it could also test the central puzzle to ensure that no single completed corner box is sufficient to complete the central puzzle, and thus the complete Samurai.

Perhaps this last condition might be replaced with a selectable GF rating (Gale Force) of 1 to 4, for the number of corner-boxes that are needed to complete the central puzzle. So GF3 would mean no pair of corner boxes is sufficient. And GF4 would presumably be "very interesting"?

Cheers
MM (B)