# Can this square puzzle be solved? **URL:** \ **Category:** Factual Questions\ **Created:** [March 4, 2004, 1:24am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437 "2004-03-04T01:24:35Z")\ **Posts on this page:** 19\ **Page:** 1
**Author:** ![SlickRoenick](https://avatars.discourse-cdn.com/v4/letter/s/e68b1a/32.png) [@SlickRoenick](https://boards.straightdope.com/u/SlickRoenick)\ **Post date:** [March 4, 2004, 1:24am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/1 "2004-03-04T01:24:35Z")
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. **square** square square square square square square **square** square square square square square square square square 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? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 4, 2004, 1:39am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/2 "2004-03-04T01:39:45Z")
|X|_| |_|_| |_|_|_|X| |_|_|_|_| |_|_|_|_| We’re looking at something like that, right? 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. ---
**Author:** ![ChordedZither](https://avatars.discourse-cdn.com/v4/letter/c/e9c0ed/32.png) [@ChordedZither](https://boards.straightdope.com/u/ChordedZither)\ **Post date:** [March 4, 2004, 1:52am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/3 "2004-03-04T01:52:15Z")
Looks like a parity problem to me. 1. Any square that can be reached in an odd number of steps from the start can _only_\* be reached in an odd number of steps. 2. Any square that can be reached in an even number of steps from the start can _only_\* be reached in an even number of steps. 3. You can only have the letters in the original orientaion after zero or an even number of rotations. 4. The target position is an odd number of steps from the start. I conclude that there’s no way to reach the target position with the letters in the original orientation. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 4, 2004, 3:14am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/4 "2004-03-04T03:14:44Z")
If you only rotate 90 degrees at a time, you need 4 steps to hit the original orientation. I’ve figured out how to quickly solve this with a computer program, but I need to write the program. It’ll get done tomorrow. ---
**Author:** ![Q.E.D](https://avatars.discourse-cdn.com/v4/letter/q/51bf81/32.png) [@Q.E.D](https://boards.straightdope.com/u/Q.E.D)\ **Post date:** [March 4, 2004, 3:20am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/5 "2004-03-04T03:20:34Z")
> [@ultrafilter](#): > > I’ve figured out how to quickly solve this with a computer program, but I need to write the program. Is the algorithm simple enough to post? If so, I’ll take a stab at coding it, since my plate is empty at the moment. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 4, 2004, 3:33am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/6 "2004-03-04T03:33:41Z")
> [@Q.E.D.](#): > > Is the algorithm simple enough to post? If so, I’ll take a stab at coding it, since my plate is empty at the moment. 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. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [March 4, 2004, 3:38am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/7 "2004-03-04T03:38:55Z")
> [@](#): > > f you only rotate 90 degrees at a time, you need 4 steps to hit the original orientation. But you can rotate clockwise and counterclockwise. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 4, 2004, 3:42am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/8 "2004-03-04T03:42:43Z")
> [@Cabbage](#): > > But you can rotate clockwise and counterclockwise. Point well-taken. If there is a solution that just involves rotation in one direction, that algorithm will find it, so it might still be worth trying. Accounting for two directions of rotation is trickier. ---
**Author:** ![ChordedZither](https://avatars.discourse-cdn.com/v4/letter/c/e9c0ed/32.png) [@ChordedZither](https://boards.straightdope.com/u/ChordedZither)\ **Post date:** [March 4, 2004, 3:57am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/9 "2004-03-04T03:57:18Z")
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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 4, 2004, 4:06am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/10 "2004-03-04T04:06:42Z")
> [@ChordedZither](#): > > 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. Yeah, I think you’re right. I’m saying there’s no solution now. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 4, 2004, 4:11am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/11 "2004-03-04T04:11:12Z")
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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 4, 2004, 4:14am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/12 "2004-03-04T04:14:21Z")
> [@ultrafilter](#): > > You can even extend that path by two to get a path of length 4. A path whose length is a multiple of 4, that is. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [March 4, 2004, 4:47am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/13 "2004-03-04T04:47:22Z")
> [@](#): > > 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. How’s that an even length path? 😉 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. ---
**Author:** ![Urban\_Ranger](https://avatars.discourse-cdn.com/v4/letter/u/e9c0ed/32.png) [@Urban\_Ranger](https://boards.straightdope.com/u/Urban_Ranger)\ **Post date:** [March 4, 2004, 7:09am UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/14 "2004-03-04T07:09:52Z")
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. ---
**Author:** ![SlickRoenick](https://avatars.discourse-cdn.com/v4/letter/s/e68b1a/32.png) [@SlickRoenick](https://boards.straightdope.com/u/SlickRoenick)\ **Post date:** [March 4, 2004, 12:14pm UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/15 "2004-03-04T12:14:14Z")
> [@ultrafilter](#): > > |X|_| > |_|_| > |_|_|_|X| > |_|_|_|_| > |_|_|_|_| > > We’re looking at something like that, right? Yes, that is pretty much what we are looking at. > [@Urban Ranger](#): > > ``` > 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. > > ``` My understanding is that there are no directly diagonal movements, unless you consider down and over to be diagonal. ---
**Author:** ![fezpp](https://avatars.discourse-cdn.com/v4/letter/f/da6949/32.png) [@fezpp](https://boards.straightdope.com/u/fezpp)\ **Post date:** [March 4, 2004, 1:35pm UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/16 "2004-03-04T13:35:53Z")
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. ---
**Author:** ![El\_Zagna](https://avatars.discourse-cdn.com/v4/letter/e/d2c977/32.png) [@El\_Zagna](https://boards.straightdope.com/u/El_Zagna)\ **Post date:** [March 4, 2004, 1:59pm UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/17 "2004-03-04T13:59:01Z")
> [@SlickRoenick](#): > > Movement can only be done by pivoting on a corner 1 at a time. 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). ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [March 4, 2004, 2:28pm UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/18 "2004-03-04T14:28:49Z")
**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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 4, 2004, 4:23pm UTC](https://boards.straightdope.com/t/can-this-square-puzzle-be-solved/232437/19 "2004-03-04T16:23:40Z")
> [@Cabbage](#): > > How’s that an even length path? 😉 > > 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. I could’ve sworn that I found two paths of different parity last night, but it was late and I was tired. Oh well.