Has anyone tried solving these puzzles using templates?

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

Interestingly, on a sample puzzle it generates 2204098 comparisons of templates and finds three unique solutions. It only makes use of hidden chains and templating to solve it, which it manages in 40 seconds:

Ruud · Site Admin

You might want to debug and optimize your code a little further.

My template solver found a single solution for this puzzle

gaby · Posted: Fri Sep 23, 2005 9:33 pm Post subject:

Nice. My solver is written in PHP, so it's hardly the most efficient of solvers Smile

I think you're right, I've had some other thoughts on how to optimise this analysis, so I'll give them a bash and see what the outcome is.
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

gaby · Posted: Sat Sep 24, 2005 12:22 pm Post subject:

Found out what the problem was. It was allowing templates that could place numbers in places where there was no candidate for that number (eg, it would select templates that said a 2 could go in r3,c4 when the candidates on the board said that it couldn't put a 2 in that cell).

It's still not particularly quick, but at least it works now Smile

_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

gaby · Posted: Sat Sep 24, 2005 12:40 pm Post subject:

In fact, I'm still getting three solutions for that puzzle. Which one of these is wrong? Here are the three sets of templates that my solver returns:

gaby · Posted: Sat Sep 24, 2005 12:46 pm Post subject:

Solutions 1 and 2 are valid, solution 3 is broken. Yes, more debuggering to do methinks...

Ruud · Site Admin

Set 1 overlaps on values 4 and 5.
Set 2 seems to be fine.
Set 3 overlaps on values 4 and 6.

Check your code and you will probably see that you do not correctly compare the templates of these values.

gaby · Posted: Sat Sep 24, 2005 3:05 pm Post subject:

How very curious. I have two types of comparison that the system does, template_overlap and template_contained. template_overlap( $a, $b ) checks if template $a has any common elements with template $b, and template_contained( $a, $b ) checks that template $a is a subset of template $b, eg is completely contained within it. Templates are either the 46656 initial templates, or templates of the current state of a number, or an exclusion map, where numbers cannot go.

All the templates are in a binary form, as shown above. Firstly the initial templates are calculated that each number can contain. For each of the 46656 templates {t}, we do two comparisons:

1. Look at the template for each number{tN}. If the binary AND of {t} & {tN} == {tN}, then {tN} is completely contained within {t}, so {t} is a possible template for the number N.

2. Look at the template that represents where the number N cannot go in the board, eg a 1 for cells that don't have N as a candidate, and a 0 for ones that do. This is called the exclusion template, or {tNX}. If the binary AND of {t} & {tNX} > 0, then there are some elements in the template {t} that appear in {tNX}. However, {tNX} contains all the places we know that we can't put the number N, so we can remove that template.

We now have a list of templates for number N. Repeat for all the numbers until we have a list for each number.

Start with the number with fewest templates. For each template for this number, remove other templates from the other numbers that have any places in common. That is, if by doing a binary AND of this template and each of the other number's templates, the result is > 0, there is some overlap, so we can remove that template.

We recursively try this for all the templates. If we end up with a number that has 0 templates left for it, it's not a valid combination. If we end up at a point where each number has 1 template, we've found a valid combination (like the three above). The recursive function will try all combinations and find all possibiliites.

So, the glitch is somewhere in the recursive comparison function, as it's not removing some templates that should not be there. Am I missing a vital step here? Should I be removing more templates to begin with?
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

gaby · Posted: Sat Sep 24, 2005 8:55 pm Post subject:

Interesting. The recursive function sorts the list of templates for each number by the number of templates that each number has left for it, so the output will be a sequence, but not necessarily in order 1 to 9. Sets 1, 2 and 3 come out in this order:

Numbers for Set 1: 2, 3, 8, 9, 7, 6, 1, 4, 5
Numbers for Set 2: 2, 3, 8, 9, 7, 6, 1, 4, 5
Numbers for Set 3: 2, 8, 3, 9, 7, 1, 5, 6, 4

Set 1 has an overlap in numbers 4 and 5, and set 3 with numbers 4 and 6. In both cases these are the last numbers that are searched, so the problem lies within the closing conditions of the recursive function...

Success! One template set matches, and it is a valid set. The section of the recursive function that detected if there was only one number left to find a template for, wasn't removing overlapping templates. Now it removes the overlaps, the results come out clean.

Question now is how to speed it up. I'm guessing that your program is written in a slighty faster language that PHP? C++ or something similar? When you say it took less than a millisecond, was that just the templating analysis? How do you scan the tree of possibilities, recursively or using a 9 level nested set of for loops? I kept mine recursive because I'd like my solver to be able to solve NxN sudoku as well as the usual 9x9.
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

Ruud · Site Admin

rkral · Posted: Mon Nov 28, 2005 8:52 pm Post subject:

Auguste · Posted: Mon Feb 20, 2006 5:33 am Post subject:

Interesting idea.

All the exclusions or assertions by logic will be proofed by template. This method seems very quick and require no knowledge. As a matter of fact, the templates themselves are the knowledge!

I am interested in the speed comparison with DLX.

Razz

Ruud · Site Admin

Hi Auguste,

I have both templates and DLX implemented in SudoCue, and DLX is definitely faster.

Templates have more flexibility. You can choose to test the templates for a single digit only, or for 2 digits.

With templates, it is also easy to implement POM (Pattern Overlay Mapping)

Ruud.
_________________
Meet me at sudocue.net

Auguste · Posted: Tue Feb 21, 2006 1:01 pm Post subject:

A seeming crazy idea is using the templates as the nodes in DLX, considering the fact that sudoku puzzles have given clues to remarkably reduce the size of DLX search.

daj95376