I was playing around with one of those "rearrange the pieces on the board" puzzles recently and realized I was stumped after unsuccessfully making the same moves over and over and over...:|

Aside: If you're not familiar with sliding puzzles, the 15-puzzle and Klotski puzzle are both classic examples.

 

For the particular puzzle I was stuck on, the board looks like:

  ######
 #      #
 #      #
 #      #
#        #
 #  ##  #
 #  ##  #
  ##  ##

And uses the following seven pieces:

AA  BB  CC  DD   E  FF   G
AA  BB  CC  D   EE   F   GG

The challenge is to get the 'A' piece from here:

  ######
 #      #
 #      #
 #      #
#        #
 #AA##  #
 #AA##  #
  ##  ##

To here:

  ######
 #      #
 #      #
 #      #
#        #
 #  ##AA#
 #  ##AA#
  ##  ##

With the starting state:

  ######
 #DDBBFF#
 #DEBBGF#
 #EECCGG#
#   CC   #
 #AA##  #
 #AA##  #
  ##  ##

Go ahead and give it a try if you want a challenge! You can make your own puzzle out of paper cutouts or build something with interlocking cubes (which I can say from experience works quite well).

Aside: I'm not going to reveal where the original puzzle came from because I don't want to spoil it for anyone. But feel free to leave a comment if it looks familiar!

 

Now, maybe the puzzle's solution is/was obvious to you, but like I said, I was stuck. As it happens, I was in a stubborn mood and didn't want to admit defeat, so I decided to write a simple program to solve the puzzle for me!

I'd done this before (many years ago), and had a decent sense of what was involved; I managed to bang out the solution below pretty quickly. My goal was to solve the puzzle with minimal effort on my part - so the implementation favors simplicity over performance and there's a lot of room for improvement. Still, it finds the solution in about a second and that's more than quick enough for my purposes.:)

I've included the complete implementation below. The code should be fairly self-explanatory, so read on if you're interested in one way to solve something like this. Two things worth calling out are that this approach is guaranteed to find the solution with the fewest number of moves and it can handle arbitrarily-shaped pieces and boards - both of which flow pretty naturally from the underlying design.

There's not much more to say - except that you should feel free to reuse the code for your own purposes!

 

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

// Quick (minimally-optimized) solver for a typical "slide the pieces" puzzle.
// * Implements breadth-first search to guarantee it finds the optimal solution
// * Detects already-seen states and avoids analyzing them again
// * Handles arbitrarily shaped pieces and irregular/non-contiguous boards
// Performance notes:
// * Board.GetHashCode is called *very* often; keeping it fast is ideal
// * Board.IsValid is also called frequently and should be quick to run
// * Board._locations could have the board location removed (it's always 0)
// * It may be more efficient check validity before creating Board instances
class SlidePuzzleSolver
{
    public static void Main()
    {
#if DEBUG
        // Quick sanity check of the Board class
        var test = new Board();
        Debug.Assert(test.IsValid);
        Debug.Assert(!test.IsSolved);
#endif

        // Stopwatch is handy for measuring/improving performance
        var stopwatch = new Stopwatch();
        stopwatch.Start();

        // Initialize
        Board start = new Board();
        Board solved = null;
        var seen = new HashSet<Board>(start); // IEqualityComparer<Board>
        var todo = new Queue<Board>();
        todo.Enqueue(start);
        seen.Add(start);

        // Keep going as long as there are unseen states...
        while (0 < todo.Count)
        {
            // Get the next board and process its moves
            var board = todo.Dequeue();
            foreach (var move in board.GetMoves())
            {
                if (move.IsSolved)
                {
                    // Solved!
                    solved = move;
                    todo.Clear();
                    break;
                }
                if (!seen.Contains(move))
                {
                    // Enqueue the new state
                    todo.Enqueue(move);
                    seen.Add(move);
                }
            }
        }

        // Write elapsed time to debug window
        stopwatch.Stop();
        Debug.WriteLine("Elapsed time: {0}ms", stopwatch.ElapsedMilliseconds);

        // Reverse the solved->start parent chain
        Debug.Assert(null != solved);
        var solution = new Stack<Board>();
        while (null != solved)
        {
            solution.Push(solved);
            solved = solved.Parent;
        }

        // Display the solution start->solved
        foreach (var board in solution)
        {
            board.Show();
        }
    }

    // Representation of a board and the arrangement of pieces on it
    // (IEqualityComparer<Board> is used by HashSet<Board> above)
    private class Board : IEqualityComparer<Board>
    {
        // Constants for board size
        private const int Width = 10;
        private const int Height = 8;

        // Statics for pieces and moves
        private static readonly IReadOnlyList<Piece> _pieces;
        private static readonly IReadOnlyList<int> _deltas;

        static Board()
        {
            // Initialize (shared) piece instances
            // Pieces are defined by cells they occupy as deltas from their origin (top-left)
            // Cells are numbered 0..N going from top-left to bottom-right
            // The board is treated as a piece, but never allowed to move
            var pieces = new List<Piece>();
            pieces.Add(new Piece('A', 0, 1, 10, 11)); // Square
            pieces.Add(new Piece('B', 0, 1, 10, 11)); // Square
            pieces.Add(new Piece('C', 0, 1, 10, 11)); // Square
            pieces.Add(new Piece('D', 0, 1, 10));     // 'L'
            pieces.Add(new Piece('E', 1, 10, 11));    // 'L'
            pieces.Add(new Piece('F', 0, 1, 11));     // 'L'
            pieces.Add(new Piece('G', 0, 10, 11));    // 'L'
            pieces.Add(new Piece('#', 2, 3, 4, 5, 6, 7, 11, 18, 21, 28, 31, 38, 40, 49, 51, 54, 55, 58, 61, 64, 65, 68, 72, 73, 76, 77)); // Irregular board shape
            _pieces = pieces.AsReadOnly();
            // Initialize move deltas (each represents one cell left/right/up/down)
            _deltas = new int[] { -1, 1, -Width, Width };
        }

        // Piece locations
        private readonly int[] _locations;

        // Parent board
        public Board Parent { get; private set; }

        // Create starting state of the puzzle
        public Board()
        {
            // Board piece (last element) is always at offset 0
            _locations = new int[] { 52, 14, 34, 12, 22, 16, 26, 0 };
        }

        // Create a board from its parent
        private Board(Board parent, int[] locations)
        {
            Parent = parent;
            _locations = locations;
        }

        // Get the valid moves from the current board state
        public IEnumerable<Board> GetMoves()
        {
            // Try to move each piece (except for the board)...
            for (var p = 0; p < _pieces.Count - 1; p++)
            {
                // ... in each direction...
                foreach (var delta in _deltas)
                {
                    // ... to create the corresponding board...
                    var locations = (int[])_locations.Clone();
                    locations[p] += delta;
                    var board = new Board(this, locations);
                    // ... and return it if it's valid
                    if (board.IsValid)
                    {
                        yield return board;
                    }
                }
            }
        }

        // Checks whether a board is valid (i.e., has no overlapping cells)
        public bool IsValid
        {
            get
            {
                // Array to track occupied cells
                var locations = new bool[Width * Height];
                // For each piece (including the board)...
                for (var p = 0; p < _pieces.Count; p++)
                {
                    var piece = _pieces[p];
                    var offsets = piece.Offsets;
                    // ... for each cell it occupies...
                    for (var o = 0; o < offsets.Length; o++)
                    {
                        // ... check if the cell is occupied...
                        var location = _locations[p] + offsets[o];
                        if (locations[location])
                        {
                            // Already occupied; invalid board
                            return false;
                        }
                        // ... and mark it occupied
                        locations[location] = true;
                    }
                }
                return true;
            }
        }

        // Checks if the board is solved
        public bool IsSolved
        {
            get
            {
                // All that matters in *this* puzzle is whether the 'A' piece is at its destination
                return (56 == _locations[0]);
            }
        }

        // Show the board to the user
        public void Show()
        {
            // Clear the console
            Console.Clear();
            // For each piece (including the board)...
            for (var p = 0; p < _pieces.Count; p++)
            {
                var piece = _pieces[p];
                // ... for each offset...
                foreach (var offset in piece.Offsets)
                {
                    // ... determine the x,y of the cell...
                    var location = _locations[p] + offset;
                    var x = location % Width;
                    var y = location / Width;
                    // ... and plot it on the console
                    Console.SetCursorPosition(x, y);
                    Console.Write(piece.Marker);
                }
            }
            // Send the cursor to the bottom and wait for a key
            Console.SetCursorPosition(0, Height);
            Console.ReadKey();
        }

        // IEqualityComparer<Board> implemented on this class for convenience

        // Checks if two boards are identical
        public bool Equals(Board x, Board y)
        {
            return Enumerable.SequenceEqual(x._locations, y._locations);
        }

        // Gets a unique-ish hash code for the board
        // XORs the shifted piece locations into an int
        public int GetHashCode(Board b)
        {
            var hash = 0;
            var shift = 0;
            foreach (var i in b._locations)
            {
                hash ^= (i << shift);
                shift += 4;
            }
            return hash;
        }
    }

    // Representation of a piece, its visual representation, and the cells it occupies
    private class Piece
    {
        public char Marker { get; private set; }
        public int[] Offsets { get; private set; }

        public Piece(char marker, params int[] offsets)
        {
            Marker = marker;
            Offsets = offsets;
        }
    }
}