Follow this pattern to set up the “puzzle board.” Where i write square you actually draw a square shape. Have all the squares touching the sides of the adjacent ones.
Where the 2 boldified squares are write:
A B
D C
on the inside
On a separate square the same size as the ones you have drawn(you may want to cut this out) write the letters in the same position. The task is to start your moveable square on top of bold square 1 and move it to bold square 2 with the letters lining up in the same position. Movement can only be done by pivoting on a corner 1 at a time. I’ve spent almost an hour working on this and it seems to me like trying to get both of your Chess Bishops to end up on the same colored tile. Anyone know if this can be accomplished?
It’s easy to model as a graph problem. There’s one vertex for each square, and an edge from a vertex to the vertices representing the squares above, below, to the left, and to the right of it. You’re looking for a path from the start vertex to the end vertex whose length is a multiple of 4.
I’ll play around with it a bit later, if no one else has got to it first.
It’s quite simple to describe. Coding it is another matter.
What you need to do is create a set of vertices–let’s call it S. Place the starting vertex in there. Now enter a loop that continues until the |S| is unchanged over an iteration.
For each iteration, you’re going to be looking at all the current elements of S. You’ll need to find all the vertices that are reachable in four edge crossings from each vertex and add them into a secondary set. Throw that secondary set into S at the end of the loop body.
At the end, S will contain all the vertices which are reachable from the starting vertex in 4k steps for some integer k. If the ending vertex is in there, the puzzle is solvable. Otherwise, it’s not.
Now here’s a trick: let A be the adjacency matrix for a graph G. The (i, j)th entry of A[sup]n[/sup] is the number of paths of length n from vertex i to vertex j. You can use that in the middle part to figure out which vertices are reachable in four steps from a given vertex.
The algorithm would work if a solution was possible. But the target square is an odd number of steps from the starting square - that means an odd number of 90 degree rotations. So any path you take from the start to the target will always leave the letters plus or minus 90 degrees out of kilter.
And as soon as I post that, I find an even-length path to the finish. Go down 2, right 1, down 2, right 2, and up 2. Rotate 180[sup]o[/sup] if need be.
You can even extend that path by two to get a path of length 4.
Actually, if we’re on a square grid, and we allow only left, right, up, and down movement (as we have here), then if I pick any two squares and find there’s an odd length path between them, then all paths between them must be odd length. Think about coloring the grid like a checkerboard to see why this is so. So the original problem is impossible for the reason ChordedZither mentioned–there’s obviously an odd length path between them, therefore, there is no even length path between them.
Can you move from any square to any adjacent one (including diagonal ones) by pivoting once in the appropriate direction? That is, rotate clockwise to move to the right - any square to the right - and counterclockwise to the left. If so, this seems pretty simple.
It’s impossible.
If you colour the board in ‘checker board’ fashion with the top left square (the starting square) black then the moving piece will always be ‘the right way up’ or ‘upside down’ on black squares and lying on one of it’s ‘sides’ on white squares.
As the ending square is white the puzzle can’t be solved. The piece on the ending square will always have B or D top-right not A or C.
I wonder if this isn’t the critical piece of information. Instead of thinking in two-dimensions, try three. In that case a valid move could be shown as:
|0||
||1|
||||X|
|||||
||||_|
where 0 is the starting point and 1 is the first move. I’m not sure how the orientation of the letters comes out, but perhaps someone with more time can work on that angle (or angel - I never can remember).
bnorton, even with that, the problem still has no solution. With that move, the square’s orientation will flip along the diagonal (or its orientation will simply rotate 180[sup]o[/sup], if the square spins around on its corner during the process). Say we color the grid like a black/white checkerboard, black in the upper left, and we allow these additional types of moves. Then any time the square is on black, it will have one of four orientations, all with “A” in the upper left or bottom right; any time the square is on white, it will have one of the remaining four orientations, with “A” in the upper right or bottom left. Since the end square is white, it can’t end up with the same orientation it started with on the black square.
