Search code examples
javamultidimensional-arraysliding-tile-puzzle

Solving a 4x4 Puzzle Grid

I'm attempting to create a program that will find the steps to solve a puzzle with the following rules:

  • Given any set of colors in a 4x4 grid, attempt to match to an ending pattern with the same number of colors.
  • Colors are not swapped, but rotated either horizontally or vertically, such that

{W, W, B, W}

can be rotated to

{W, W, W, B}

{B, W, W, W}

{W, B, W, W}

  • The entire puzzle can be solved in less than 16 steps.

I've already figured out how to store the data of the puzzle itself, but I'm struggling on how to proceed about finding a solution that can display steps. Since the depth is limited to 16 steps, I'm ok with trying to brute force this, but don't really have an idea of how to establish a pattern.

This is similar to solving a Rubik's cube, and I've already looked at the following resources:

  • stackoverflow.com/questions/34656587/solving-rubiks-cubes-for-dummies/34656726#34656726

  • stackoverflow.com/questions/5563671/solving-rubiks-cube-programmatically

  • amzi.com/articles/rubik.htm

  • chessandpoker.com/rubiks-cube-solution.html

and the 15 numbers problem

  • stackoverflow.com/questions/3621623/how-to-programatically-solve-the-15-moving-numbers-puzzle

To make this question as clear as possible: What is a good way to a) store/print the steps, and b) find the solution that takes the least steps?

Solution

  • I guess I can't explain a tree without pictures.

    Say you have this starting pattern:

    [W, W, W, B]
[W, W, W, B]
[B, W, W, W]
[W, W, W, B]

    This would be the top node of the tree. Level 0.

    So now, we do all possible horizontal and vertical rotations. Horizontal to the right first.

    [B, W, W, W]
[W, W, W, B]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[B, W, W, W]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[W, B, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[B, W, W, W]
[B, W, W, W]

    Horizontal to the left.

    [W, W, B, W]
[W, W, W, B]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, B, W]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[W, W, W, B]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[B, W, W, W]
[W, W, B, W]

    Vertical up 

    [W, W, W, B]
[B, W, W, B]
[W, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, W]
[B, W, W, B]
[W, W, W, B]

    Vertical down

    [W, W, W, B]
[W, W, W, B]
[W, W, W, W]
[B, W, W, B]

[W, W, W, B]
[W, W, W, B]
[B, W, W, B]
[W, W, W, W]

    Since the second and third columns are all W, we only have 2 patterns for vertical up and vertical down.

    We have a total of 12 patterns at level 1.

    We moved very methodically. There was no randomness in our moves. Horizontal to the right, horizontal to the left, vertical up, and vertical down.

    Now, take each of the 12 patterns at level 1 and generate the 16 patterns. You don't have to save the patterns that match the patterns at level 0 and level 1.

    The patterns generated and saved make up level 2.

    Continue generating each level until you hit level 16 or you have a solution. Because you're removing duplicates from the tree levels, you won't hit the theoretical maximum of 16 to the 16th power nodes on level 16.

    Finish the level in case there's more than one solution with a minimum number of moves.