0
$\begingroup$

From the 1970s I have a Hexomino called

Computer Puzzle in Computer Age

promising more than 1.000.000 solutions. A later version with a different title (I could not remember) says more than 1.000.000.000 solutions are possible. Probably the number is closer to 1.000.000.000.000 - but of course a single solution is hard to find by hand.

In this Hexomino the 35 pieces are arranged in a rectangle 19 x 11 plus a nose in the middle of one of the longer sides. (This has a specific reason, because it is not possible to arrange the 35 pieces in a square.)

Especially for this arrangement I'd like to find all solutions.

The puzzle looks like this (could not put into comment):

┌─┬───┬─────┬─────────┬───┬─┬─────┬───┐ │ ├─┐ └───┐ └───┐ ┌─┬─┘ │ │ ┌─┤ │ │ │ └─┐ ┌─┴───┬─┴─┘ ├─┐ ┌─┤ ├─┐ │ │ │ │ └─┐ ├─┤ ┌─┐ │ ┌─┐ │ └─┘ │ │ └─┤ └───┤ │ ┌─┘ │ │ │ └─┼─┘ └─┴─┐ ┌─┤ ├─┐ └───┐ │ ├─┼───┘ └─┤ │ ┌─┬───┴─┘ │ │ └─┬───┴─┤ │ └─┬───┬─┴─┐ ├─┘ └───┬─┐ ├─┴─┐ └─┐ │ │ │ ┌─┴─┐ ├─┴─┐ ┌─┬─┘ └─┤ ├─┐ ├─┐ │ │ ┌─┘ │ │ │ ┌─┴─┘ └─┬─┐ │ ┌─┘ └─┘ ├─┤ ├─┤ ┌─┘ ┌─┘ │ ├─┐ ┌───┘ │ │ ├───────┤ │ │ └─┴───┴─┬─┘ │ └─┴───┐ └─┼─┘ ┌─────┘ │ └─────────┴───┴───┐ ┌─┴───┴───┴───────┘ └─┘

|improve this question
$\endgroup$
  • $\begingroup$ What do you mean by "solve"? $\endgroup$ – xnor May 19 '15 at 1:01
  • 2
    $\begingroup$ Could you give an image of the frame as to make the question easier to understand? $\endgroup$ – BmyGuest May 19 '15 at 7:53
  • $\begingroup$ Solve means to put all pieces into the given shape - see example above for one solution. $\endgroup$ – V15I0N May 19 '15 at 22:10
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Dancing_Links ? $\endgroup$ – Dennis_E May 20 '15 at 10:11
1
$\begingroup$

I think the best algorithm would be:

Just a depth-first backtracking search. Assuming the long side without the "nose" is on the bottom, start in the bottom left. Try pieces until one fits without any 1x1 spaces or spaces that another piece could not occupy. Once one is in place, try of the remaining pieces until one fits next to it without spaces. Keep doing this until the puzzle is either complete, or there are no pieces that fit properly, at which point you backtrack to the most recent valid configuration (the version of the puzzle without the last piece in) and pick a different piece. Again you continue the algorithm and if you can't find any good configurations with this piece either, you take it out and try another piece in it's place.

|improve this answer
$\endgroup$
  • $\begingroup$ That is a general approach to find effectively a solution for such kind of puzzle. The combination of pieces could create closed areas (holes) where no other piece fits inside. Would you do some extra check for such holes? When or how often would be most efficient? $\endgroup$ – V15I0N May 19 '15 at 22:22
  • $\begingroup$ When I said "try pieces until one fits" I meant that you would do that for every piece, but I'll update my answer to explain that a little better. $\endgroup$ – MisterEman22 May 19 '15 at 22:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.