Programming Challenge 16 - Solve 1,000 Sliding Puzzles

When I was a kid, parents and relatives gave me little puzzles to solve. The one I remember most is the sliding puzzle. In a 4 x 4 square there are 15 pieces and a gap to slide a piece into either horizontally or vertically (you cannot slide diagonally).

You can still buy these puzzles, some have numbers, letters or even parts of a picture. The idea is to restore the puzzle back to the original state which is typically this. You can see an illustration of a sliding puzzle (Thanks to wikipedia for that).

1 - 2 - 3 - 4
5 - 6 - 7 - 8
9- 10-11-12
13-14-15-X

The puzzle can be messed up by sliding any any piece adjacent to the hole X, in this case only 12 or 15 can be slid. So if 12 is slid down.

1 - 2 - 3 - 4
5 - 6 - 7 - 8
9 - 10-11- X
13-14-15-12

Then piece 11 is slid to the right etc.

1 - 2 - 3 - 4
5 - 6 - 7 - 8
9 - 10- X -11
13-14- 15-12

So this programming puzzle is to solve a puzzle and restore it back to its original configuration in as few moves as possible. Just to make it interesting, not just one puzzle but 1,000, read line by line from a file. I've coded it to make it easier to read, so instead of 10-15, I use hexadecimal notation - the letters ABCDEF where A= 10, 11 = B and 15 =F. The hole is piece 0.

So the starting position is defined by a 16 char string. An unmessed up puzzle looks like this.

123456789ABCDEF0

But after moving the two pieces

Move C (12) - 123456789AB0DEFC
Move B (11) - 123456789A0BDEFC

Moves must be valid so only the 2,3, or 4 pieces next to the gap can be moved. (2 if the gap is in a corner, 3 if its on an edge or 4 if its in the middle.

The Input

This is a file of 1,000 16 character strings, each on its own line. Each messed up board will be a valid position. A nasty trick is to pull two adjacent pieces out of a real puzzle and swap their positions. That renders the puzzle unsolvable. That won't happen here. This file should be in the same location as your executable.

Download the Input File

The Output

Create an output file containing 1,000 rows something like this In the same location as the input file.

0001 1234567890ABCDEF BA682A35C7EF675437683E

The 4 digits are the puzzle number, (0001 - 1000) the next 16 are the puzzle's starting position (same as the input file) and the 3rd are the moves needed to solve it. Note the starting position and the solution refer to the piece number (1-9,A-F) in it's current position.

Using the example above: call it puzzle 1. the input would be

123456789A0BDEFC

and the output would be

0001 123456789A0BDEFC BC

I will write a test program which reads your output file and runs the solution. It then totals up the length of your answers. If an answer is wrong, 15 is added to your total. The lowest overall score wins. In the case of a tie, the quickest wins. Please print the total time it took, including the time to load the input data file and output the answers file. This is the code that you can use for timing.

• How To Time C Code.
• How To Time C++ Code.
• How To Time C# Code.

Results

Just two entries - Michael Chock and Aliaksei Sanko. Congratulations to Aliaksei who beat Michael by several minutes. For once entries didn't run in 3 thousandths of a second but three minutes for the winner.

1. Aliaksei Sanko (Belarus) - C++ Score = Time(secs) = 180.223
2. Michael Chock - C++ Score = Time(secs) = 851.235

More Programming Challenges

• Link to Rock, Scissors and Paper Bot Ongoing Programming Challenge - Runs weekly.
• Link to Programming Challenge 2 - Count the Islands. (Finished)
• Link to Programming Challenge 3 - Manage Elevators. (Finished)
• Link to Programming Challenge 4 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 5 - Squeeze words into a crossword grid - (Finished)
• Link to Programming Challenge 6 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 7 - Validate Chess Positions - (Finished)
• Link to Programming Challenge 8 - Score Poker Hands - (Finished)
• Link to Programming Challenge 9 - Manage a Data structure - (Finished)
• Link to Programming Challenge 10 - Hide Text (Finished)
• Link to Programming Challenge 11 - Match Sets of Cards (Finished)
• Link to Programming Challenge 12 - Calculate Shortest Path - Completed)
• Link to Programming Challenge 13 - Play Battleships (Finished)
• Link to Programming Challenge 14 - Multiply Large Numbers(Completed)
• Link to Programming Challenge 15 - Generate a Dungeon (Completed)
• Link to Programming Challenge 17 - Implement the Life Cellular Automaton (Deadline October 31)