Solution Signatures

Finding existing problems is useful for avoiding duplicates and finding problems that have similar shapes. One approach is to use Pattern Search. Another system is Solution Signatures.

How it Works

Solution Signatures is based on looking at the board state surrounding a solution path. For example, this problem:

Let's look at the solution paths:

We can see the solution is on the 2-2 point. There is another problem with a similar solution:

The 2-2 point solution matches with a radius of 2. The radius is how far out the board tries to match. (Rotations, translations, and color flipping are ignored.) Radius 2 looks like this (edges of the board are ignored):


Using Solution Signatures

One nice property is duplicates and similar problems can be detected without having to do a manual Pattern Search. The signatures are already precalculated for all problems on the site and matching is done instantly in real time. Additionally, this works for problems in the middle of the board, unlike Pattern Search.

Adding and Editing

When adding a new problem, as soon as you mark a position as a solution, the site will automatically do a signature search for you, and warn you if there is a match at radius 2.

Problem Pages

When expanding the info section, there is an indication of signature matches. This can be useful for finding similar problems or even duplicates.

Radius Values

Radius 1 seems close to useless as there are too many similar matches. Radius 2 seems pretty good for finding duplicates or near duplicates. There doesn't seem to be a need for radius 3.

Future Improvements

Smarter partial matches may be useful -- for example matching all but one intersection on radius 2.

Matches combining multiple signatures may give more precision (if a problem has multiple solutions).