## Samurai Solving

Programs which generate, solve, and analyze Sudoku puzzles

### Re: Samurai Solving

creint wrote: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

m_b_metcalf
2017 Supporter

Posts: 12440
Joined: 15 May 2006
Location: Berlin

### Re: Samurai Solving

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

Posts: 324
Joined: 20 January 2018

### Re: Samurai Solving

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

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: Samurai Solving

Mathimagics wrote: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)

m_b_metcalf
2017 Supporter

Posts: 12440
Joined: 15 May 2006
Location: Berlin

### Re: Samurai Solving

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
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### 4CS Algorithm

.
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 …

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: Samurai Solving

'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?

m_b_metcalf
2017 Supporter

Posts: 12440
Joined: 15 May 2006
Location: Berlin

### Re: Samurai Solving

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
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: Samurai Solving

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.......`

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: Samurai Solving

'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.

m_b_metcalf
2017 Supporter

Posts: 12440
Joined: 15 May 2006
Location: Berlin

### Re: Samurai Solving

m_b_metcalf wrote: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)

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: Samurai Solving

m_b_metcalf wrote:* It is.

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

m

m_b_metcalf
2017 Supporter

Posts: 12440
Joined: 15 May 2006
Location: Berlin

### Re: Samurai Solving

Struth, Bruce!!

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

MMB
Dipso ergo sum

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: Samurai Solving

m_b_metcalf wrote: 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

m_b_metcalf
2017 Supporter

Posts: 12440
Joined: 15 May 2006
Location: Berlin

### Re: Samurai Solving

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)

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

Previous