Is it still cheating if you come up with the cheat yourself? [Simple code to solve a "sliding pieces" puzzle]
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; } } }