The blog of dlaa.me

Posts from July 2013

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

Setting a value to null might be more dangerous than you think [Simple ToolTipServiceExtensions class avoids a runtime exception in Windows Store apps]

I was playing around with a Windows Store app this weekend and ran into a pretty annoying problem. At first, I couldn't tell what was going on; it seemed the app would crash at random times for no apparent reason. But after a bit of debugging to isolate the problem, I figured out what was going on.

Problem: If you have a ToolTipService.ToolTip data binding in a Windows Store app and the value of that binding transitions from non-null to null while it's being displayed, the next time the tooltip is shown, the platform will throw a NullReferenceException from native code and terminate the application.

This is a surprisingly severe consequence for something that's likely to happen with some regularity, so you'd expect someone to have run into it before now. And indeed, someone did: tkrasinger reported this problem in November of last year. It's unclear where things went from there, but I've verified the problem still occurs with fully-patched Windows 8 and also with the Windows 8.1 preview released last week.

At first glance, the situation seems pretty dire because there's no clear way to intercept the exception. And while changing the code to use an empty string instead of null does avoid the crash, it also results in an ugly little white square when you hover. Fortunately, if you know a bit about how tooltips work, you know there's a ToolTip class that gets injected in this scenario to host the bound content. What if we intercepted the binding and made sure to always provide a non-null ToolTip instance? Would that avoid the crash?

Spoiler alert: It does. :)

 

There are various ways you might go about implementing this workaround - I chose to use a custom attached property because the result looks the same in XAML and neatly encapsulates all the code in one simple, standalone class.

Let's say you were using a tooltip like so:

<Border ToolTipService.ToolTip="{Binding BindingThatCanBecomeNull}">
    <TextBlock Text="Watch out, ToolTipService might crash your app..."/>
</Border>

As we've established, if that binding goes null while the user is mouse-ing around, the app is likely to crash soon afterward.

 

So let's use my ToolTipServiceExtensions class to avoid the problem! First, download ToolTipServiceExtensions.cs from the link below and add it to your Windows Store app project. Next, add the corresponding namespace declaration to the top the XAML:

xmlns:delay="using:Delay"

And lastly, tweak the XAML to use ToolTipServiceExtensions instead of ToolTipService:

<Border delay:ToolTipServiceExtensions.ToolTip="{Binding BindingThatCanBecomeNull}">
    <TextBlock Text="ToolTipServiceExtensions saves the day!"/>
</Border>

That's it - you're done! Random crashes from null-going tooltips should be a thing of the past. :)

 

[Click here to open ToolTipServiceExtensions.cs or right-click/save-as to download it to your machine]

 

Aside: If you're using any of the other ToolTipService properties in your code, they are unaffected by this change. All ToolTipServiceExtensions does is wrap the content in a ToolTip before deferring to the existing ToolTipService implementation.

 

For the curious, here's what the code looks like:

namespace Delay
{
    /// <summary>
    /// Class containing a replacement for ToolTipService.SetToolTip that works
    /// around a Windows 8 platform bug where NullReferenceException is thrown
    /// from native code the next time a ToolTip is displayed if its Binding
    /// transitions from non-null to null while on screen.
    /// </summary>
    public static class ToolTipServiceExtensions
    {
        /// <summary>
        /// Gets the value of the ToolTipServiceExtensions.ToolTip XAML attached property for an object.
        /// </summary>
        /// <param name="obj">The object from which the property value is read.</param>
        /// <returns>The object's tooltip content.</returns>
        [SuppressMessage("Microsoft.Design", "CA1062:Validate arguments of public methods", MessageId = "0", Justification = "Underlying method will validate.")]
        public static object GetToolTip(DependencyObject obj)
        {
            return (object)obj.GetValue(ToolTipProperty);
        }

        /// <summary>
        /// Sets the value of the ToolTipServiceExtensions.ToolTip XAML attached property.
        /// </summary>
        /// <param name="obj">The object to set tooltip content on.</param>
        /// <param name="value">The value to set for tooltip content.</param>
        [SuppressMessage("Microsoft.Design", "CA1062:Validate arguments of public methods", MessageId = "0", Justification = "Underlying method will validate.")]
        public static void SetToolTip(DependencyObject obj, object value)
        {
            obj.SetValue(ToolTipProperty, value);
        }

        /// <summary>
        /// Gets or sets the object or string content of an element's ToolTip.
        /// </summary>
        [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes", Justification = "Stardard attached property implementation.")]
        public static readonly DependencyProperty ToolTipProperty =
            DependencyProperty.RegisterAttached(
                "ToolTip",
                typeof(object),
                typeof(ToolTipServiceExtensions),
                new PropertyMetadata(null, ToolTipPropertyChangedCallback));

        /// <summary>
        /// Method called when the value of an element's ToolTipServiceExtensions.ToolTip XAML attached property changes.
        /// </summary>
        /// <param name="element">Element for which the property changed.</param>
        /// <param name="args">Event arguments.</param>
        private static void ToolTipPropertyChangedCallback(DependencyObject element, DependencyPropertyChangedEventArgs args)
        {
            // Capture the new value
            var newValue = args.NewValue;

            // Create a ToolTip instance to display the new value
            var toolTip = new ToolTip { Content = newValue };

            // Hide the ToolTip instance if the new value is null
            // (Prevents the display of a small white rectangle)
            if (null == newValue)
            {
                toolTip.Visibility = Visibility.Collapsed;
            }

            // Defer to ToolTipService.SetToolTip for the actual implementation
            ToolTipService.SetToolTip(element, toolTip);
        }
    }
}