Here are some papers, code and blog posts
(this is nice one too
) on how to algorithmically search for solutions to squzzles/scramble square puzzles. You might have received one of these puzzles as a holiday gift over the last few years, they were quite popular.
C and Perl Implemenations
General Backtracking Approach
The algorithm is straightforward - just one that searches through solutions.
What's interesting is that I've seen people solve these puzzles, even brand new ones (no prior knowledge), very quickly. There's something that happens with a persons vision or something that's helping them not have to exhaustively search the full solution space. If I'd seen someone do this once or twice, I'd think it was just lucky picks. (these puzzles have enormous solution spaces (4^8 x 9! = 23,781,703,680 puzzle configurations) )
Is there something in this puzzle that "hints" to a human early in the solution testing that a solution is viable or not. That is, after 1 or 2 pieces placed, can the human see a promising solution "faster" than the basic algorithm that searches quickly through all piece placements and orientations. If so, what is that data ("hint") the human sees and how can we factor it into the algorithm?
Possible hint data:
Rules of thumb on how all these puzzles are printed and cut (do the puzzles all get made with same orientations so exposure to one puzzle provides data on other puzzles?)
Humans can see the whole pattern in parallel even when pieces aren't lined up so they don't have to check each piece systematically
Are combinations of pieces eliminated as the humans solve it thus taking them out of future solution attempts, reducing solution space the more the human works on the puzzle.