Solving Unblock me: Recognizing board configuration in a screenshot using Mathematica

Introduction

Unblock me is a sliding block puzzle game with board size of 6 X 6. Solving for a solution with minimum number of steps is not a easy task, since the generalization of the game is PSPACE complete. 

Fig 1. Unblock me screenshot

 The objective of the game is to move the red block to the exit. All the blocks can only be moved along it's longer length. You need to slide the other blocks to free the red one into the exit.

In the following sections, I am going to demostrate how to use image processing functions in Mathematica to process the screenshot as Fig 1, and the end result that I will get is:

Where the empty space is represented by 0, the red block by 1, and different blocks by a different integers.

Method

Assume that the screenshot is stored as c:\1.png. Now let's import the file into Mathematica first.

i1 = Import["c:\\1.PNG"];

Let's crop the image to get rid of the unneccessary part.

i2 = ImageTake[i1, {123, 416}, {14, 307}]

Fig 2. cropped image

Since we will have to extract the red block, let's separate the color channels of the image.

i3 = ColorSeparate[i2]

Fig 3. RGB colors of the image

It is clear that the red block is quite difference from others in the second image. We will take advantage of that later.

Now, to make the images more easily to process, we will transform the image to white-black color.

i4 = Binarize[i3[[1]]]

Fig 4. Black and white image of red color channel

To extract different blocks, let use the MorphologicalComponents function. This function is used to find all connected regions in a binary image, and label them with integers.

mc = MorphologicalComponents[i4, Method -> "BoundingBox"];

Now, mc is a 2D array. To visualize it, we can do:

MatrixPlot[mc]

Fig 5. Morphological Components in the image with MatrixPlot

To reduce the above array into a matrix as shown in introduction is easy. I will show how to do that in the final section. Before that, let's extract the red block first.

Extracting the red block

From Fig 3, it is found that the main difference between the red block with others lies in the 2nd image, the green channel. So, let's make it into a binary image first.

ir1 = Binarize[i3[[2]]]

Fig 6. Binary image of the green channel

If we subtract ir1 from i3, only the red block is left.

ir2 = ImageSubtract[i4, ir1]

Fig 7. Subtraction of ir1 from i4

However, there are much noise with it from the wood grain. To remove them is easy. Just do:

ir3 = DeleteSmallComponents[ir2]

Fig 8. red block image

To extract the red block, we will use MorphologicalComponents function again.

ir4 = MorphologicalComponents[ir3, Method -> "BoundingBox"];
MatrixPlot[ir4]

Fig 9. Morphological Components of the red block

Transforming the Morphological matrix into a simple matrix

The final step is to transform the matrix mc and ir4 into a simple matrix. Since the board size is of 6 X 6, we will use a 6 X 6 matrix to represent the game board. The red block will be represented by -1, the empty space by 0, and the others by positive integers.

boxLength = IntegerPart[Length[mc]/6];

First we calculate the length of each box, by dividing the total length into 6 parts.

Then let's define a function:

boxValue[i_, j_, mc_] := 
 Commonest[
   Flatten[mc[[boxLength (i - 1) + 1 ;; boxLength i, 
     boxLength (j - 1) + 1 ;; boxLength j]]], 1][[1]]

where mc is the morphological matrix. This function separate the mc matrix into 6 X 6 boxes, and take the commonest value out as the (i, j)-th box value.

Fig. 10 Divided the matrix into 6X6 grids

Finally, we run the following code to get the matrix:

board = Table[boxValue[i, j, mc], {i, 1, 6}, {j, 1, 6}];
redBoard = Table[boxValue[i, j, ir4], {i, 1, 6}, {j, 1, 6}];
pb = Position[broadTarget, 1];
Scan[(board[[#[[1]], #[[2]]]] = -1) &, pb]
board // MatrixForm

First of all, we generate the matrix for the matrix mc and ir4. Since ir4 only has the red block, and the value of the red block is 1, so we take its position and make the corresponding position in board to -1. The result is:

After getting this matrix, we may start solving the game using breath-first or depth-first search. Please check for update for this article. The method to solve the puzzle will be provided soon.