Has anyone tried solving these puzzles using templates?

Ruud · Site Admin

I've written a solver that uses the following technique:

Theory:

There are 46656 different configurations for any value in the grid.
With 1 position given, 5184 configurations are left.
(a chute is a line of 3 boxes)
With 2 positions given in 1 chute, 864 configurations are left.
With 2 positions given in 2 chutes, 576 configurations are left.
With 3 positions given in 1 chute, 288 are left.
With 3 positions given in 3 chutes, only 64 combinations are left.
Each given other value in a non-blocked position also slightly reduces the number of combinations.

In most Sudoku puzzles, there are 2 or 3 givens for each value.

Application:

My program keeps a library of all 46656 configuration templates, and maintains a list for each of the 9 values.

When a cell is filled, the list is filtered to the templates that contain that value at the cell's position.

When a cell is blocked for a value, all templates containing that value at the cell's position are removed from the list.

I have written logic in the program for detecting naked singles, hidden singles, naked subsets, hidden subsets, X-wings and coloring, but the template technique removes the same candidates (and more!) without knowing why it did that. Confused

Once the remaining templates for each value are known, they are compared to those of the other values. Overlapping combinations are filtered from the list, until only one combination remains, which then happens to be the solution to the puzzle. When the puzzle has multiple solutions, it is easily discovered with the template technique. When there is no valid solution, it is also detected.

My questions:

1. Has anyone tried this before?
2. How would one classify this method? BF? T&E? VMWOCT (very methodical waste of CPU time)?
3. I am currently using this technique in addition to known logic, but wonder if it could be used to detect new patterns and deductive rules.

Lummox JR · Posted: Sun Sep 18, 2005 12:11 am Post subject:

I'd call this a form of brute force, but an interesting one. It may well be a good way to deduce new patterns and deductive rules, which would be the main interest in maintaining such a thing.

I know just the other day an idea occurred to me that it could be possible to define forcing chains according to a strict set of logic rules in such a way as to form linked graphs, taking it out of the realm of T&E and into applied logic. However as I've found this is only a limited form of forcing chains, or perhaps should be named differently.

dukuso · Posted: Sun Sep 18, 2005 7:09 am Post subject:

I once wrote a program to count the 9 values for each digit.
I think I wanted to use it to estimate the number of
solutions of underconstrained puzzles, don't remember exactly.

It just picks a digit d, sets all other clues to "x" and counts the
number of templates from the 46656 which meet d and avoid x.

That gives 9 numbers, whose product might be an indication for
the number of solutions, I'm not sure.

You can also pick one template at random from the most
constrained digit and then iterate for the remaining digits.

-Guenter

Ocean · Posted: Sun Sep 18, 2005 8:33 pm Post subject:

angusj · Site Admin

Ocean · Posted: Sun Sep 18, 2005 11:33 pm Post subject:

If size is an issue, here are some loose and maybe wild ideas:

Is there any way of exploiting the fact, that a grid may be assumed to have a fixed first row 123456789 (and afterwords doing a permutation of the numbers)? This reduces the number of remaining configurations with a factor 9, to 5184. And the number of remaining cells is reduced from 81 to 72. In total the matrix size is reduced by about 90%.

The number of cells may even be further reduced (to 52) by the fact that last cell in a row/column is determined from the first 8, but this might complicate algorithms.

Ruud · Site Admin

Thanks for your interesting comments.

dukuso

Ocean

Ocean · Posted: Mon Sep 19, 2005 2:52 pm Post subject:

Ruud · Site Admin

Myth Jellies · Posted: Tue Sep 20, 2005 9:28 am Post subject:

This is similar to the Pattern Overlay Method that I use to solve SudoKu by hand. I describe the method in this post.

Personally, I consider my method logical because
1. There is no reason why you can't switch modes from creating a list of possible numbers to creating a list of possible solution patterns for each number. Simple rules of SudoKu suffice to compute either of these.
2. I use a simple algebraic logic equation derived from the content of one of the cells to eliminate possible patterns (I just don't have room for a master conflict list of 46,656 entries in my head Smile

)
3. Nowhere do I assume that 1 number or pattern is valid or not valid and then see what happens.

It would be interesting to see what the computer could do if it was restricted to the Pattern Overlay Method rules. The method is difficult when there are a large number of unique patterns associated with a digit.

Creating a list of unique patterns associated with a cell would be a useful tool/library to have as well.
_________________
Myth Jellies

Myth Jellies · Posted: Tue Sep 20, 2005 9:41 am Post subject:

46656 -- interesting number, that. 36 cubed. Each unique pattern could have its own unique 3 character alpha-numeric label....just thinking out loud here....
_________________
Myth Jellies

Ocean · Posted: Tue Sep 20, 2005 7:43 pm Post subject:

gaby · Posted: Fri Sep 23, 2005 12:19 pm Post subject:

I've added this to my PHP solver, and it seems that it is an effective brute force approach, but I can see it as a very straightforward way of generating puzzles. Interestingly, it finds multiple solutions to some puzzles that I thought only had single solutions. I'm going to run it against a few thousand puzzles and see what the outcome is, but I like this technique. It is quite an elegant approach.
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/