SudokuSolver Forum

Glyn Samurai #1A (Chief Wizard)

Rating based on required solving techniques:  Hellish Nightmare   Solvable using logic only?

020701003090030000500000001000400000903000600200500900000008000401090000000000000
500003002000000900001500004309007000005800600000004098000100000000020000000000306
000400000000210000000000000001050090078900003000060000000178000000000000000000000
000087000030500000050000000000006903040002060200013000700000000506700008000060005
000300000000000000000208030050001406000030009006070080000100000000080000407609001

0 Logical Solve
1 Recursively Solve: Unique solution found with 13 guesses, 118762 nodes traversed

OR

4 Naked Singles
33 Hidden Singles
29 Intersections
1 Naked Pair
1 Naked Triplet
1 Naked Quad
1 Uniqueness Test 4
1 Grouped XY-Chain up to 3 links
1 Grouped XY-Chain
5 ALS-XZ up to 5 cells
1 ALS-XZ
1 Recursively Solve: Unique solution found with 7 guesses, 22989 nodes traversed



ADDED:
Glyn Samurai #1B (Chief Wizard)

Rating based on required solving techniques:  Hellish Nightmare   Solvable using logic only?

020701003000230000500000000070420000903000600000500900700008000001000000000000000
500073012000000900001500004300007000005800600000004098000100000000000050000400306
000400000000200000000000000001050006078000003000060000000178000000000000000000000
000087000030500000050000000000006903040002060200013000700005000006700008000060005
000300000000000090000208030050001406000030009006070083090100000000000000400609801

0 Logical Solve
1 Recursively Solve: Unique solution found with 13 guesses, 43165 nodes traversed

OR

11 Naked Singles
43 Hidden Singles
33 Intersections
3 Naked Triplets
1 Naked Quads
1 X-Wing
1 Skyscrapers
1 Two String Kites
1 Empty Rectangles
2 Finned X-Wing
1 Finned Swordfish
1 XY-Wings
1 Y-Wings
2 Uniqueness Test 4
1 Uniqueness Test 6
3 XY-X-Chains up to 3 links
5 XY-X-Chains
1 Grouped XY-Chains up to 3 links
4 Grouped XY-Chains
1 Hidden Unique Rectangle
2 ALS-XZ up to 5 cells
5 ALS-XZ
1 Sue de Coq
1 Recursively Solve: Unique solution found with 2 guesses, 670 nodes traversed

_________________
Quis custodiet ipsos custodes?

Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]

Børge Your Hardest Samurai yet. This one appears not yield to single path chains (including inter-grid) augmented with advanced single grid methods.

I've compared it with JSudoku's performance on Ruud's X-Samurai 'Ronin'. For that the currently programmed logic surrenders earlier so the recursive cycle is longer. (23 Guesses ~148,000 nodes traversed).

We have a potential new player in Tarek, who I believe is implementing a puzzle wide structure from the start and hopefully Richard will eventually permit inter-grid chains. I have requested inter-grid colour markups to help the manual solver.

My own solver is almost printing 'Hello World'.

_________________
I have 81 brain cells left, I think.

I wonder if there is a solid correlation between number of nodes traversed and difficulty?
@JC: Can you provide any insight?

Using Bowman's Bingo SudokuSolver is able to find one more solution than JSudoku, namely that g1:r2c3 = 7. With this information JSudoku uses an ALS-XZ to prove that g1:r7c8 <> 2. But that is all the advancement.

Here a forced chain that proves that g1:r2c3 = 7:
(g1:r2c3=8) => (r2c4 = 2) => (r2c8 = 7) => (r5c4 = 8) => (r6c3 = 6) => (r4c5 = 6) => (r8c6 = 2) => (r5c6 = 7) => (r5c5 = 2) => (r6c5 = 1) => (r5c9 = 4) => (r6c8 = ?) => (g1:r2c3=7)

_________________
Quis custodiet ipsos custodes?

Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]

Børge The number of nodes is likely to increase with the difficulty of the puzzle as the programmed logical moves stall earlier. Have you tried recursion on the puzzles that are solvable? The amount of backtracking on those should go down as the number of singles increases. The more grids the greater the number of backdoors to 'discover' in the grid and the greater the chance of simultaneous backdoors being required. I think this is where the order of magnitude change in nodes occurs. Clueless could be very nasty.

Here are some results on Samurai #15, this puzzle and Ronin using recursion from the start.

#15A needs 7 guesses 3455 nodes
#15B needs 13 guesses 788 nodes
#15C needs 16 guesses 8116 nodes
#15D needs 15 guesses 12599 nodes
Glyn Samurai#1 13 guesses 118856 nodes
Ronin 26 guesses 636583 nodes

Note on this puzzle DLX uses less guesses and and nodes when starting right from the start than after the logical moves.

_________________
I have 81 brain cells left, I think.

NO!

Tell me about it.
I am working on a really nasty variant of Regular Clueless Special #13.
Last recursive solve (after logical solve) traversed almost 15 BILLION nodes (in 3 days) before finding the first solution. Unfortunately the grid had more than one solution:

Starting to Recursively Solve.
Be patient this may take several minutes  for hard grids...
Recursively Solve done in 248112563 milliseconds
14761577123 nodes traversed
At least 10 solutions found. This grid is invalid

In a PM Jean-Christophe mentioned that, (at that time: JSudoku 1.2b1) the recursive logic was not ideal:
Below variant 1B of Glyn Samurai #1 that solves further using logic and and where the Recursively Solve only requires 2 guesses and traverses 670 nodes. So with it you can test your theory.

Later I will post Glyn Samurai #2. By trying different "dispensable clues" sets for each grid, I will try to make it even harder.
0 Logical Solve + 1 Recursively Solve: Unique solution found with 22 guesses, 299796 nodes traversed
OR
1 Logical Solve + 1 Recursively Solve: Unique solution found with 15 guesses, 94792 nodes traversed



Glyn Samurai #1B (Chief Wizard)

Rating based on required solving techniques:  Hellish Nightmare   Solvable using logic only?

020701003000230000500000000070420000903000600000500900700008000001000000000000000
500073012000000900001500004300007000005800600000004098000100000000000050000400306
000400000000200000000000000001050006078000003000060000000178000000000000000000000
000087000030500000050000000000006903040002060200013000700005000006700008000060005
000300000000000090000208030050001406000030009006070083090100000000000000400609801

11 Naked Singles
43 Hidden Singles
33 Intersections
3 Naked Triplets
1 Naked Quads
1 X-Wing
1 Skyscrapers
1 Two String Kites
1 Empty Rectangles
2 Finned X-Wing
1 Finned Swordfish
1 XY-Wings
1 Y-Wings
2 Uniqueness Test 4
1 Uniqueness Test 6
3 XY-X-Chains up to 3 links
5 XY-X-Chains
1 Grouped XY-Chains up to 3 links
4 Grouped XY-Chains
1 Hidden Unique Rectangle
2 ALS-XZ up to 5 cells
5 ALS-XZ
1 Sue de Coq
1 Recursively Solve: Unique solution found with 2 guesses, 670 nodes traversed

_________________
Quis custodiet ipsos custodes?

Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]

At each step, it tries to follow the simplest path with fewest number of alternatives: a cell with fewest number of candidates or a house with fewest number of cells for some candidate. Both are considered equally "good": a naked single is as good as a hidden single; a bi-value cell is as good as a bi-location strong link; a tri-value cell is as good as a house with three locations for some candidate... (this is known as "first-fail" principle).

So it first solves all singles which ordering does not matter. But when several paths are possible with multiple alternatives, it takes the first one found. This is usually a good path, but not the optimal path. Some path may lead to a contradiction which will exhibit very soon after, whereas another path with same number of alternatives may require very long routes before it hit the contradictions (deep search tree). It does not consider any future implications when choosing which path to take among those with same number of alternatives (there is just simple forward checking, but no look ahead, and of couse no cycle-cutset...).

Further readings:
http://kti.ms.mff.cuni.cz/~bartak/constraints/
http://en.wikipedia.org/wiki/Constraint ... on_problem

PS: this explains why solving the very same grid several times does not always traverse the same number of nodes. Reason: internal ordering of houses in JSudoku could differ.

_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.