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;
}
}
}
