Samurai Solving

Programs which generate, solve, and analyze Sudoku puzzles

Re: Samurai Solving

Postby m_b_metcalf » Sat Mar 16, 2019 11:00 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10012
Joined: 15 May 2006
Location: Berlin

Re: Samurai Solving

Postby creint » Sat Mar 16, 2019 12:39 pm

I used the '21x21' global technique.
No I don't have a database of rated puzzles, so I can't provide one.
creint
 
Posts: 92
Joined: 20 January 2018

Re: Samurai Solving

Postby Mathimagics » Sat Mar 16, 2019 2:16 pm

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Samurai Solving

Postby m_b_metcalf » Sat Mar 16, 2019 2:28 pm

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)
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10012
Joined: 15 May 2006
Location: Berlin

Re: Samurai Solving

Postby Mathimagics » Sat Mar 16, 2019 4:34 pm

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. 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

4CS Algorithm

Postby Mathimagics » Wed Mar 20, 2019 4:03 am

.
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 … :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Samurai Solving

Postby m_b_metcalf » Wed Mar 20, 2019 4:59 pm

'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?
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10012
Joined: 15 May 2006
Location: Berlin

Re: Samurai Solving

Postby Mathimagics » Wed Mar 20, 2019 5:24 pm

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 …
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Samurai Solving

Postby Mathimagics » Wed Mar 20, 2019 8:12 pm

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.......
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Samurai Solving

Postby m_b_metcalf » Thu Mar 21, 2019 11:42 am

'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.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10012
Joined: 15 May 2006
Location: Berlin

Re: Samurai Solving

Postby Mathimagics » Thu Mar 21, 2019 2:25 pm

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)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Samurai Solving

Postby m_b_metcalf » Thu Mar 21, 2019 2:32 pm

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10012
Joined: 15 May 2006
Location: Berlin

Re: Samurai Solving

Postby Mathimagics » Thu Mar 21, 2019 2:45 pm

Struth, Bruce!! 8-)

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

MMB
Dipso ergo sum
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: Samurai Solving

Postby m_b_metcalf » Fri Mar 22, 2019 8:19 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10012
Joined: 15 May 2006
Location: Berlin

Re: Samurai Solving

Postby Mathimagics » Fri Mar 22, 2019 10:02 am

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"? 8-)

Cheers
MM (B)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Previous

Return to Software