Search code examples
algorithmlogic

Algorithm for solving tiling/jigsaw puzzle

I've been thinking about an algorithm for solving small puzzles. I found different algortihms on the internet and on stackoverflow but they do not meet my needs in some points:

  • My puzzle pieces are in one color, there is no image/pattern/... on them
  • Every edge of a part can be one of 8 options, similar to them on the picture (you can describe the parts as ABCD, cdab, cBBb, ADcb for example); there are no more complicated structures or anything like that
  • The puzzles I want to solve are not to big, there are no ones bigger than 8x8
  • The corner/egde pieces have no specific edges, the result will just not be a clean rectangle
  • Not all my puzzles are solvable
  • The parts can be rotated but not turned
  • Every puzzle part is unique

Puzzle parts

Solution

  • So my starting point would be just brute force - lay piece 0 down in the (0,0) position, then start trying any of the remaining pieces in (0,1) until one fits, then move on to (0,2), etc. At any step if there are no pieces that fit in that space, take out the previously fit piece and try to find a new fit for that square.

    I can't prove it, but I suspect that filling in pieces such that you are more likely to be evaluating a piece with 2 constraints (that is, instead of doing larger squares, 2x2, 3x3, 4x4, moving out) will terminate faster than just doing rows.

    It reminds me of those 3x3 puzzles where you have square pieces with heads and tails of animals. One optimization there is to count up the mismatch between pairs - if you you have a lot more A than you have a then you know that A will tend to be located at the edges of the puzzle, but in an 8x8 puzzle you have a lot less edge to interior ratio so that difference isn't as likely to be useful, nor do I have a good idea for integrating it into an algorithm.

    (Edit) Thinking about it more, I think the first thing that counting would get you is an early out if no solution exists. An NxN grid has 2*N*(N-1) interior matches that must be satisfied. If min(A,a) + min(B,b) + min(C,c) + min(D,d) < 2*N*(N-1) you know no solution exists.

    (Edit 2) had abs() where I meant to have min(). Ooops.