Originally posted by iamatigerI've tried, but it looks impossible to me. Are you supposed to fill the target region completely?
I came across this site
http://www.tile-puzzler.com/unsolved_mysteries.asp
I see number 5351 has never been solved and has been on there since May
First one to solve it wins!
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by TheMaster37I think if you can fit them all in you will win, whether or not they fit the area.
Yes, I was that far. I didn't see a rule about filling the entire field.
But I also suspect that the designer would have designed it to tile exactly, remember that tiles of identical colour can overlay.
Ok, first one to solve it or prove it is impossible wins.
Originally posted by iamatigerHaving done some of the others on this site now (but not this one yet), I think you have to fill the space. You don't have to use all the shapes, but in a well-designed puzzle it'll be necessary.
I think if you can fit them all in you will win, whether or not they fit the area.
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by AThousandYoungThe all fit in a 5x5 area, and if they are all to be used there has to be some significant overlapping.
When I realized the pieces were connected to other pieces AND that they could overlap I gave up.
However now I'm having some new thoughts...
Are all the groups of pieces the same size? All fit in a 4x4 area for example? Hmm.
I'm in the process of writing a perl program to solve this puzzle, but it is tricky.
Originally posted by iamatigerBrute force 🙂. I read your previous note and thought writing a program to do it would be interesting.
Wow, nice one! How did you do it?
(I had tried several times to solve it without help, but never got very far).
Incidentally, my program did first find a solution that fits all the shapes in and does not fill the shape. That wasn't accepted, so it's definitely filling the shape that is required to solve the problem.
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by mtthwWell, nice programming!
Brute force 🙂. I read your previous note and thought writing a program to do it would be interesting.
(I had tried several times to solve it without help, but never got very far).
Incidentally, my program did first find a solution that fits all the shapes in and does not fill the shape. That wasn't accepted, so it's definitely filling the shape that is required to solve the problem.
I think I might have tried to be a bit too optimal with my approach, I'm trying to keep track of the number of ways each shape can fit in, and the number of shapes that can fit over each uncovered square, and recursively search by placing the shape which can fit in the least positions or which covers a square that that fewest other shapes can cover, and I'm rather tangled up in pointers as a result.
Yeah, I tried to avoid being too clever with mine - thought I'd worry about optimising if I found it was taking too long to solve it.
The heart of the program is a function that takes a list of shapes to put into the grid. It takes the first shape, tries all possible positions for that shape, and for those positions that fit it calls the same function recursively with a list of the remaining shapes.
It looked like this (in Java). Sorry about the lack of indenting. Hopefully it makes sense.
private boolean solveNext(List<Shape> remainingShapes) {
if (remainingShapes.isEmpty()) {
// No more shapes to fit, have we filled the grid?
return layout.isComplete();
}
Shape shape = remainingShapes.remove(0);
for (Shape subShape : shape.getCongruentShapes()) {
for (int x = 0; x <= layout.getWidth() - subShape.getWidth(); ++x) {
for (int y = 0; y <= layout.getHeight() - subShape.getHeight(); ++y) {
if (layout.shapeFits(subShape, x, y)) {
layout.addShape(subShape, x, y);
List<Shape> restOfShapes = new LinkedList<Shape>(remainingShapes);
boolean restFit = solveNext(restOfShapes);
if (restFit) {
// Wahay! Problem solved
return true;
}
else {
// Not possible in this position - remove and carry on
layout.removeShape(subShape);
}
}
}
}
}
return false;
}
Originally posted by mtthwSo do we have any results of your work yet? If so, can that program be modified for a general overlapping piece puzzle solution? Good job BTW.
Yeah, I tried to avoid being too clever with mine - thought I'd worry about optimising if I found it was taking too long to solve it.
The heart of the program is a function that takes a list of shapes to put into the grid. It takes the first shape, tries all possible positions for that shape, and for those positions that fit it calls the same function recu ...[text shortened]... layout.removeShape(subShape);
}
}
}
}
}
return false;
}