Click here to Skip to main content
15,867,488 members
Articles / Mobile Apps / Windows Phone 7

Build Puzzle 15 - Walkthrough

Rate me:
Please Sign up or sign in to vote.
4.93/5 (27 votes)
23 Feb 2012Ms-PL4 min read 83.4K   4.2K   34   16
How to Build Puzzle 15 (n-Puzzle)

Introduction

In one of my articles I wrote about My First Windows 8 Application – Metro Puzzle there I talked about Windows 8 Metro application and demonstrate how to build app for Win 8, the application I built was Puzzle 15. later I started to get requests to explain the steps for building that game.

So I'm writing the steps for building a Puzzle 15 Game.

1.png

Background

The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle. If the size is 3×3 tiles, the puzzle is called the 8-puzzle or 9-puzzle, and if 4×4 tiles, the puzzle is called the 15-puzzle or 16-puzzle named, respectively, for the number of tiles and the number of spaces. The object of the puzzle is to place the tiles in order (see diagram) by making sliding moves that use the empty space.

Step 1: The Puzzle Base

There are several ways to build the puzzle layer, In my demo I chose a simple way of a Canvas with 16 children's type of StackPanel.

Basically I have a lower canvas with the Board image, on top of it I put another canvas with 16 Stack Panels, each panel spread to 100X100

2.png

Now, when I have the main puzzle structure I added an image of size 95x95 to each Stack Panel. (the reason it’s not 100X100 – is to leave a space between each), for each image I set the Tag property with the value of the image – 1.png Tag = 1

3.png

I’ve also add a timer for counting the time took to solve this puzzle and another int property to count the moves the user made.

Step 2: Find

One of the most common things we’ll use in our code, is FIND:

  • Find Stack Panel by Image Id
  • Find the Empty Panel
  • Find the Value by position

Find the parent of image with a specific Tag value

C#
StackPanel FindStackPanelByTagId(int tag)
{
  if (tag == 16)
  {
     return (from stackPanel in ContentPanel.Children.OfType<StackPanel>() 
          where stackPanel.Children.Count == 0 select stackPanel).First();
  }
  else
  {
     return (from stackPanel in ContentPanel.Children.OfType<StackPanel>()
             from img in stackPanel.Children.OfType<Image>()
             where Convert.ToInt32(img.Tag) == tag
             select stackPanel).First();
  }
}  

Find the position of StackPanel without children

C#
int FindEmptyItemPosition()
{
    int index = 15;
    for (int i = 0; i < 15; i++)
    {
        if (((StackPanel)ContentPanel.Children[i]).Children.Count == 0)
            return index;
 
        index--;
    }
    return 0;
} 

Get the Tag value by StackPanel position

C#
int FindItemValueByPosition(int position)
{
  return ((StackPanel)ContentPanel.Children[position]).Children.Count > 0 
          ? Convert.ToInt32(((Image)((StackPanel)ContentPanel.Children
            [position]).Children[0]).Tag) : 16;
} 

Step 3: Scrambles

Now we have are puzzle structure and Find method helpers, the first thing is to Scramble or puzzle.

So I wrote a method that runs n times and generate random numbers from 1 to 16, for each number find the current StackPanel that hold him. (FindStackPanelByTagId) .

If First and Second number are smaller then 16 then - swipe the images and tag values.

If One of the values is 16 the swipe - One Stackpanel will be cleared of Items

C#
 void Scrambles()
{
    var count = 0;
    while (count < 25)
    {
        var a = _rnd.Next(1, 17);
        var b = _rnd.Next(1, 17);
 
        if (a == b) continue;
 
        var stack1 = FindStackPanelByTagId(a);
        var stack2 = FindStackPanelByTagId(b);
 
        if (a == 16)
        {
            var image2 = stack2.Children[0];
            stack2.Children.Clear();
            stack1.Children.Add(image2);
        }
        else if (b == 16)
        {
            var image1 = stack1.Children[0];
            stack1.Children.Clear();
            stack2.Children.Add(image1);
        }
        else
        {
            var image1 = stack1.Children[0];
            var image2 = stack2.Children[0];
 
            stack1.Children.Clear();
            stack2.Children.Clear();
 
            stack1.Children.Add(image2);
            stack2.Children.Add(image1);
        }
 
        count++;
    }
} 

Step 4: Check Board

Each move the user do, perform a loop and checks values from 1 to 16. if the numbers are not in the correct order than nothing happen.

Else You stop the game timer and display a win message.

 void CheckBoard()
{
    var index = 1;
    for (var i = 15; i > 0; i--)
    {
        if (FindItemValueByPosition(i) != index) return;
        index++;
    }
 
    _timer.Stop();
    WinGrid.Visibility = System.Windows.Visibility.Visible;
} 

Step 5: Move Items

Before we can apply move of items we need to check several things, the first thing is:

Check if the Item Can move, Checking all panels around the specific item with -1 +1 -4 +4, if one of them is empty then he can move.

 StackPanel CanMove(UIElement itemToMove)
{
    var count = ContentPanel.Children.Count;
    for (var i = 0; i < count; i++)
    {
        if (!(ContentPanel.Children[i] is StackPanel)) continue;
 
        var stackPanel = (StackPanel)ContentPanel.Children[i];
        if (!stackPanel.Children.Contains(itemToMove)) continue;
 
        if (!IsBorderSwich(i, i + 1) && i + 1 <= 15 && ContentPanel.
            Children[i + 1] != null && 
           ((StackPanel)ContentPanel.Children[i + 1]).Children.Count == 0)
            return ((StackPanel)ContentPanel.Children[i + 1]);
 
        if (!IsBorderSwich(i, i - 1) && i - 1 > -1 && ContentPanel.
            Children[i - 1] != null && 
           ((StackPanel)ContentPanel.Children[i - 1]).Children.Count == 0)
            return ((StackPanel)ContentPanel.Children[i - 1]);
 
        if (i + 4 <= 15 && ContentPanel.Children[i + 4] != null && 
           ((StackPanel)ContentPanel.Children[i + 4]).Children.Count == 0)
            return ((StackPanel)ContentPanel.Children[i + 4]);
 
        if (i - 4 > -1 && ContentPanel.Children[i - 4] != null && 
           ((StackPanel)ContentPanel.Children[i - 4]).Children.Count == 0)
            return ((StackPanel)ContentPanel.Children[i - 4]);
 
    }
    return null;
} 

The Second - if both of the items you want to swipe are in the Board borders do nothing.

private readonly int[] _bordersNums = { 0, 4, 8, 12, 3, 7, 11, 15 };

bool IsBorderSwich(int a, int b)
{
    return _bordersNums.Contains(a) && _bordersNums.Contains(b);
}

4.png

Now after we have those safety methods we can move the items based on user clicks: Just register to ItemManipulationStarted on the entire windows, for each event check if the item isn’t image do nothing,

if it does, call the CanMove method to verify that this item can move around.

 private void ItemManipulationStarted(object sender, 
                                          ManipulationStartedEventArgs e)
{
    var item = (UIElement)e.OriginalSource;
    if (!(item is Image)) return;
 
    var to = CanMove(item);
 
    if (to != null)
    {
        _moves++;
        txtMoves.Text = _moves.ToString();
        MoveItem(item, to);
        CheckBoard();
    }
 
    e.Handled = true;
    e.Complete();
} 

MoveItem - Move Item From One StackPanel to Another.

 void MoveItem(UIElement item, StackPanel targetPanel)
{
    foreach (var stackPanel in
        ContentPanel.Children.OfType<StackPanel>().Where(stackPanel => 
    stackPanel.Children.Count > 0 && stackPanel.Children.Contains(item)))
    {
        stackPanel.Children.Remove(item);
    }
 
    targetPanel.Children.Add(item);
} 

Step 6: Check If Puzzle Solvable

This part of very important, because half of the starting positions for the n-puzzle are impossible to resolve.

Johnson & Story (1879) used a parity argument to show that half of the starting positions for the n-puzzle are impossible to resolve, no matter how many moves are made. This is done by considering a function of the tile configuration that is invariant under any valid move, and then using this to partition the space of all possible labeled states into two equivalence classes of reachable and unreachable states.

The Puzzle 15 (n-puzzle) is a classical problem for modeling algorithms involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible, i.e., they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*.

bool CheckIfSolvable()
{
    var n = 0;
    for (var i = 1; i <= 16; i++)
    {
        if (!(ContentPanel.Children[i] is StackPanel)) continue;
 
        var num1 = FindItemValueByPosition(i);
        var num2 = FindItemValueByPosition(i - 1);
 
        if (num1 > num2)
        {
            n++;
        }
    }
 
    var emptyPos = FindEmptyItemPosition();
    return n % 2 == (emptyPos + emptyPos / 4) % 2 ? true : false;
}

Step 7: Setup a New Game

Now, when we defined everything we need, let’s write the New Game method, reset all timer and moves number back to 0, call the Scrambles method, and while the game is unsolvable continue scramble the game, once it’s solvable start the timer.

public void NewGame()
{
    _moves = 0;
    txtMoves.Text = "0";
    txtTime.Text = Const.DefaultTimeValue;
 
    Scrambles();
    while (!CheckIfSolvable())
    {
        Scrambles();
    }
 
    _startTime = DateTime.Now.AddSeconds(1);
    _timer.Start();
 
    GridScrambling.Visibility = System.Windows.Visibility.Collapsed;
}

5.png

Enjoy

License

This article, along with any associated source code and files, is licensed under The Microsoft Public License (Ms-PL)


Written By
Architect Sela
Israel Israel
Shai Raiten is VS ALM MVP, currently working for Sela Group as a ALM senior consultant and trainer specializes in Microsoft technologies especially Team System and .NET technology. He is currently consulting in various enterprises in Israel, planning and analysis Load and performance problems using Team System, building Team System customizations and adjusts ALM processes for enterprises. Shai is known as one of the top Team System experts in Israel. He conducts lectures and workshops for developers\QA and enterprises who want to specialize in Team System.

My Blog: http://blogs.microsoft.co.il/blogs/shair/

Comments and Discussions

 
QuestionIf empty square not in the lower-right corner (16th). How to check solvable? Pin
Son Nguyen25-Oct-17 17:58
Son Nguyen25-Oct-17 17:58 
GeneralMy vote of 5 Pin
Michael Haephrati1-Mar-13 2:28
professionalMichael Haephrati1-Mar-13 2:28 
QuestionQuestion??? Pin
mr.pakapun16-Jan-13 15:28
mr.pakapun16-Jan-13 15:28 
AnswerRe: Question??? Pin
mr.pakapun17-Jan-13 4:31
mr.pakapun17-Jan-13 4:31 
QuestionWhat about puzzle 8 and 24 ?? Pin
mr.pakapun16-Jan-13 2:54
mr.pakapun16-Jan-13 2:54 
AnswerRe: What about puzzle 8 and 24 ?? Pin
mr.pakapun16-Jan-13 15:20
mr.pakapun16-Jan-13 15:20 
GeneralRe: What about puzzle 8 and 24 ?? Pin
phil.o1-May-14 1:49
professionalphil.o1-May-14 1:49 
QuestionAsk! Pin
Pramana Adi Putra10-Jan-13 13:01
Pramana Adi Putra10-Jan-13 13:01 
AnswerRe: Ask! Pin
Shai Raiten20-Jan-13 1:52
Shai Raiten20-Jan-13 1:52 
GeneralMy vote of 5 Pin
Kanasz Robert21-Sep-12 1:27
professionalKanasz Robert21-Sep-12 1:27 
GeneralRe: My vote of 5 Pin
Shai Raiten29-Sep-12 20:38
Shai Raiten29-Sep-12 20:38 
QuestionA few improvements Pin
Dennis_E10-Aug-12 2:21
professionalDennis_E10-Aug-12 2:21 
GeneralMy vote of 5 Pin
Anurag Gandhi12-Mar-12 9:50
professionalAnurag Gandhi12-Mar-12 9:50 
AnswerGreat game Pin
Marsh Joseph19-Feb-12 22:49
Marsh Joseph19-Feb-12 22:49 
GeneralRe: Great game Pin
Shai Raiten19-Feb-12 23:05
Shai Raiten19-Feb-12 23:05 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.