5

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

Improve this question
2
  • Seems like you could have multiple solutions as well? Also, by rotated but not turned, you mean perhaps flipped? Commented Feb 27, 2013 at 20:45
  • Yes, there can be multiple solutions. The parts can not be turned upside down. They can be rotated but figurative they are just painted on one side. Commented Feb 27, 2013 at 20:53

1 Answer 1

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Sorry I do not exactly get how I would calculate |A-a| + |B-b| + |C-c| + |D-d|. It does not need to be NxN, it can be NxM too.
Sorry, should have elaborated - A in that context is the total number of A nubs that appear in the set of pieces, a is the total number of a nubs. Taking the absolute value of the difference gives us the maximum number of A-a matches that can be formed. If there aren't enough matches to fill out the puzzle you are sunk; note that the converse isn't true though, having enough may still yield no solution if they don't line up right.
I do not find my fallacy - I think it should be < 4N or < 2N+2M. Where is my mistake?
4N or 2N + 2M would be the number of edges; that summation sets an upper bound on the number of Matching conditions. If that upper bound is less than the number of required matches, it can't work. The number of interior constraints in an NxM matrix would be (N * (M-1)) + (M * (N-1))
I thought As are a specific kind of nubs and a the fitting holes (or the opposite)? Then I would calculate all nubs not fitting in any holes and compare it to the number of edge nubs/holes? Maybe I misunderstoud "A in that context is the total number of A nubs that appear in the set of pieces, a is the total number of a nubs."? How to determine the "total number [...] that appers in the set" and just the "total number"?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.