The blog of dlaa.me
Archive: July, 2013
• Is it still cheating if you come up with the cheat yourself? [Simple code to solve a "sliding pieces" puzzle]
Tuesday, July 16th 2013

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

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

// 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

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
// Initialize move deltas (each represents one cell left/right/up/down)
_deltas = new int[] { -1, 1, -Width, Width };
}

// Piece 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])
{
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);
}

// 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;
}
}
}```
Tags: Miscellaneous Technical
• Setting a value to null might be more dangerous than you think [Simple ToolTipServiceExtensions class avoids a runtime exception in Windows Store apps]
Monday, July 1st 2013

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?

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. :)

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),

/// <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);
}
}
}```
Tags: Windows Store App