Before you read this article, play with the above puzzle. You can move the block around by left-clicking on a numbered tile that's adjacent to the empty tile.

The source code for this puzzle can be found over here.

Background

This is a game that has been on my list of projects for a long time and I've finally decided to work on it last night. Although, this post has nothing to do with Artificial Intelligence, I was inspired to write this game when I studied about Heuristics in the book named Artificial Intelligence: A Modern Approach and on how it was applied to this game.

What are the game mechanics?

This game is played on a four-by-four grid with numbered tiles that are shuffled randomly. As you can see, there are 15 numbered cells and 1 empty cell in the grid, this is to allow movement of the tiles within the grid.

However, the movement is limited to the numbered tiles that are adjacent to the empty tile.

The player wins the game after ordering all the numbered tiles in the grid in an order of ascending sequence.

Source code

Here's the source code of the entire game:

var board = [], rows = 4, cols = 4;
var possibleMoves, zx, zy, oldzx = -1, oldzy = -1;

//Generate 2D Board
function generateBoard()
{
    for(var i=0; i<rows; i++)
    {
        board[i] = [];
    }

    for(var j=0; j<cols; j++)
    {
        for(var i=0; i<rows; i++)
        {
            board[j][i] = (i + j * 4) + 1;
        }
    }

    //position of the empty cell in the grid i.e. 3,3
    zx = zy = 3;
    board[zx][zy] = 16;
}

//Generate the cells
function generateCells()
{
    var grid = document.createElement("div");
    grid.className += "board";

    document.body.appendChild(grid);

    for(var j=0; j<4; j++)
    {
        for(var i=0; i<4; i++)
        {
            var cell = document.createElement("div");
            cell.className += "cell";
            cell.id = "cell_" + (i + j * 4);
            cell.row = i;
            cell.col = j;
            cell.addEventListener("click", cellEventHandle, false);
            cell.appendChild(document.createTextNode(""));
            grid.appendChild(cell);
        }
    }
}

/*
    Determine the possible number of moves
    based on the empty cell's coordinates.
*/
function genPossibleMoves()
{
    possibleMoves = [];
    var ii, jj;

    /*
        Just for reference:
        The empty cell can be moved in the following x,y coords:
        -1,0, 0,-1, 1,0, 0,1
    */
    var xCoords = [-1, 0, 1, 0];
    var yCoords = [0, -1, 0, 1];

    for(var i=0; i<4; i++)
    {
        ii = zx + xCoords[i];
        jj = zy + yCoords[i];

        //If it's out of bounds, skip it
        if(ii < 0 || jj < 0 || ii > 3 || jj > 3)
        {
            continue;
        }

        possibleMoves.push({x: ii, y: jj});
    }
}

function updateCells()
{
    for(var j=0; j<cols; j++)
    {
        for(var i=0; i<rows; i++)
        {
            var cell_id = "cell_" + (i + j * 4);
            var cell = document.getElementById(cell_id);
            var val = board[i][j];

            if(val < 16)
            {
                cell.innerHTML = ("" + val);
                if(val % 2 == 0)
                {
                    cell.className = "cell dark";               
                }
                else
                {
                    cell.className = "cell light";
                }
            }
            else
            {
                cell.innerHTML = "";
                cell.className = "empty";
            }
        }
    }
}

//Event handler for each cell
function cellEventHandle(e)
{
    genPossibleMoves();

    //Current coords of the cell
    var r = e.target.row;
    var c = e.target.col;
    var pos = -1;
    var isPossible = false;
    // console.log(r + "," + c);

    /*
        Check if the current cell is 
        one of the possible moves
    */
    for(var i=0; i<possibleMoves.length; i++)
    {
        if(possibleMoves[i].x == r && possibleMoves[i].y == c)
        {
            isPossible = true;
            pos = i;
            break;
        }
    }

    if(isPossible)
    {
        var temp = possibleMoves[pos];

        //Swap position of the empty cell
        board[zx][zy] = board[temp.x][temp.y];
        //Update the coordinates of the empty cell
        zx = temp.x;
        zy = temp.y;
        board[zx][zy] = 16;
        updateCells();

        //Check if the game is over
        if(is_game_over())
        {
            setTimeout(function(){
                alert("Congrats!");
            }, 2);
        }
    }

}

//Check if the game is over
function is_game_over()
{
    var currentVal = 0;
    for(var j=0; j<cols; j++)
    {
        for(var i=0; i<rows; i++)
        {
            if(board[i][j] < currentVal)
            {
                return false;
            }

            currentVal = board[i][j];
        }
    }
    return true;
}

//Shuffle the board
function shuffleBoard()
{
    var shuffleLimit = 0;
    var temp;

    do
    {
        genPossibleMoves();

        while(true)
        {
            // Pick a random cell of possible moves
            temp = possibleMoves[Math.floor(Math.random() * possibleMoves.length)];
            if (temp.x != oldzx || temp.y != oldzy)
            {
                break;
            }
        }

        oldzx = zx;
        oldzy = zy;

        board[zx][zy] = board[temp.x][temp.y];
        zx = temp.x;
        zy = temp.y;
        board[zx][zy] = 16;

    }while(++shuffleLimit < 200);
}

//REstart the game
function restart()
{
    shuffleBoard();
    updateCells();
}

//Start the game
function start()
{
    generateBoard();
    generateCells();
    restart();
}

As I had mentioned above, today's article has nothing to do with Artificial Intelligence but in the future, I plan to write a solver for this game that makes use of Heuristics.

Hope you liked reading this article and have fun playing the game!

Stay tuned for more!