Samurai and Dancing links

kranser · Posted: Tue Nov 22, 2005 3:04 pm Post subject: Samurai and Dancing links

If a Samurai puzzle is valid (i.e. one solution), does that mean that each of the 5 9X9-Grids would produce one solution via Dancing links, or does dancing links need to work with the whole puzzle to determine if it can be solved of not?

Kranser.

dukuso · Posted: Wed Nov 23, 2005 5:50 am Post subject:

there can be more than one solution for some of the 9*9s.
You could generate them all and then try to find the compatible ones

but I guess, it's easier and not much slower to solve the puzzle as a whole. You'll get 3321 rows and 1620 columns if I made no mistake.

I would order columns by subpuzzle and
on ties just choose the column with smallest index.
Or even better prefer subpuzzles with fewest rows.

Ruud · Site Admin

I wonder whether you could do it like this:

1. Find all possible solutions for the 4 corner puzzles.

2. Configure DLX for the center puzzle with the rows in the 4 corner boxes limited to the remaining candidates found in step 1.

3. Solve the center puzzle. Should now have only 1 solution.

Ruud.

frisch · Posted: Sat Nov 26, 2005 6:23 pm Post subject:

I doubt this kind of technique is very adapted.

I counted the number of solutions to the upper-left 9x9 grid of this
overlapping puzzle:

http://www.djape.net/sudoku/wp/index.php?dl=overlap/xwing20051126_2.png

There are 2916320 of them...