Fifteen slide puzzle and the A* algorithm

In this tutorial we will be modifying our breadth first search (BFS) code from the eight tutorial to work for a 15 slide puzzle. We'll acheive this by switching from BFS to A*. A star is similar to BFS except that it uses some metric to prioritize which states to explore next. So we'll need a way to rate our states and we'll also need a priority queue to efficiently get the nearest-to-goal state.

Solvability

Some jerk made this game return unsolvable puzzles 10% of the time, so we should check the solvability of the puzzle when we first get it. There is a great write up on slide puzzle solvability here. The short of it is that you calculate something called inversions then depending on if the puzzle has odd or even rows you do a check to see if it's solvable.

Inversions

Inversions are calculated by counting the number of lower tiles that come after each number in our board array, not considering the blank tile. A small example for the board [2, 3, 1, 0]. 2 is followed by 1 which is lower than it, so inversions = 1. 3 is also followed by 1 so inversions += 1. We don't count the blank tile so no lower tiles come after 1. So we have the total being inversions = 2. Some code to calculate this for our 15 puzzle.

let inversions = 0;
for (let idx = 0; idx < board.length; idx++) {
    let val = board[idx];

    for (var jdx = (idx + 1); jdx < board.length; jdx++) {
        if (board[jdx] < val && board[jdx] != 0) {
            inversions++;
        }
    }
}

We can ES6ify this, I personally think it's horribly unclear but some people are into this kind of thing.

let inversions = board.map(
    (val, idx) => board.slice(idx+1)
        .filter(
            sub => sub < val && sub != 0
        ).length
    ).reduce(
        (total, val) => total + val
    );

If you really want to turn this into an interview white board problem you can do it with merge sort but the array is only 16 elements so I think what we have will work just fine.

Satisfiability

Alright, we have our inversions, how do we know if a layout is solvable? If the puzzle width (e.g. the 4 in 4x4) is odd, then the puzzle is solvable if the number of inversions is even. We're working with a 4x4 though so we don't really care about the odd rule or the generic case and can hardcode some values.

If the width is even (it is), then we check if the zero is on an even or odd row from the bottom (the last row is 1).

let zeroIdx = board.indexOf(0);
// four minus cause we're going from the bottom
let row = 4 - Math.floor(zeroIdx / 4);
let evenRow = row % 2 === 0;

It is solvable if the number of inversions is even and the zero is on an odd row. It is also solvable if the number of inversions is odd and the zero is on an even row. Basically if one is odd and the other is even, it's solvable. We can use xor (^) for this.

function solvable(board) {
    let zeroIdx = board.indexOf(0);
    let row = 4 - Math.floor(zeroIdx / 4);
    let evenRow = row % 2 === 0;

    let inversions = inversionCount(board);
    let inversionsEven = inversions % 2 === 0;

    return inversionsEven ^ evenRow;
}

Metric for guiding A*

Great, we can now discard the junk puzzles sent by the server. A* needs some metric to prioritize which state is closer to the solution and which is further. It turns out that number of inversions is a perfectly acceptable metric, so we'll use that since we've already written it.

function inversionCount(board) {
    let inversions = 0;
    for (let idx = 0; idx < board.length; idx++) {
        let val = board[idx];

        for (var jdx = (idx + 1); jdx < board.length; jdx++) {
            if (board[jdx] < val && board[jdx] != 0) {
                inversions++;
            }
        }
    }

    return inversions;
}

Priority Queue

Next we'll need a priority queue. Unlike our metric, we cannot just use inversions for this, so we'll have to write one. Priority queues are implemented using min (or max if you like to number things like that) heaps. A minheap is a tree where the child nodes have a higher value than their parent. This means the lowest element is at the top of the heap. Ditto but backward for max heaps. We'll be using a minheap.

This can be represented using an array. Your lowest value is at index 0, and children to a node at an index are at index*2 + 1 and index*2 + 2 (e.g. the children of index 0 are indices 1 and 2). To insert a new node you place it at the end of the array then swap it with its parents until it is in the proper spot (parents less than it and children greater). This gives an insertion (push) time of O(log n). To remove a node (we only care about the first one) you save off the first one, then take the one from the last position and place it in the first position, then you swap it down the heap until it is in a proper spot. This gives a deletion (pop) of O(log n).

We'll start with a couple convenience methods to get the parent and child indices given an index.

function parent(idx) {
    return Math.round(idx / 2) - 1;
}

function left(idx) {
    return idx*2 + 1;
}

function right(idx) {
    return idx*2 + 2;
}

Next, we can write our push method. We're going to be pushing game state objects, the same ones that were explained in the bfs tutorial except we add a score property to them for the priority queue to use.

let state = {
    score: 1000
    board: board,      
    parent: undefined, 
    move: undefined,   
}

The push method is fairly straight forward. We add the new state to the end of our minheap array. Then, while it's not in the top position and its score is less then its parent's score, we swap it with its parent.

let minheap = [];

function push(minheap, state) {
    // index of added node
    let curr = minheap.length;
    minheap.push(state);

    // swap the last node up until it's in a good spot
    while(curr > 0 && state.score < minheap[parent(curr)].score) {
        minheap[curr] = minheap[parent(curr)];
        minheap[parent(curr)] = state;
        curr = parent(curr);
    }
}

For the pop method we define a few more helper functions. The method minChildIdx returns the index of the child with the lowest score, minChild returns the child with the lowest score, and hasSwapDown is the logic for checking if a node should be swapped downward.

function minChildIdx(minheap, idx) {
    // only one child node
    if (minheap[right(idx)] === undefined) {
        return left(idx);
    }

    if (minheap[left(idx)].score < minheap[right(idx)].score) {
        return left(idx);
    }

    return right(idx);
}

function minChild(minheap, idx) {
    return minheap[minChildIdx(minheap, idx)];
}

function hasSwapDown(minheap, idx) {
    if(!hasChild(minheap, idx)) {
        return false;
    }

    return minChild(minheap, idx).score < minheap[idx].score;
}

The pop method takes the first element. If that's the only element it will empty the minheap array and return it. Otherwise, it will place the last element at the first index, then swap it downward as long as its score is greater than the score of its children. At the end it returns the first element that it saved off.

function pop(minheap) {
    // save the first node for return
    let state = minheap[0];

    // if there is only 1 node return it
    if (minheap.length == 1) {
        minheap.pop();
        return state;
    }

    // remove last node and put it first
    minheap[0] = minheap.pop();
    let curr = 0;

    // swap the last node downward until it's in a good spot
    while(hasSwapDown(minheap, curr)) {
        let minIdx = minChildIdx(minheap, curr);
        let tmp = minheap[curr];
        minheap[curr] = minheap[minIdx];
        minheap[minIdx] = tmp;
        curr = minIdx;
    }

    return state;
}

Now that we have a prototype we can turn it into a class so we don't have to keep track of the minheap array and pass it around everywhere. Classes allow us to create instances of our object, in this case, we'll be creating a single priority queue instance.

We start by creating a class level variable minheap in the constructor. This allows us to access the minheap variable in any function of our class, so we can remove it as the first argument to our functions. When we call the functions now we have to refer to them with this, indicating that they belong to our priority queue object. There are also a few more functions added to keep the code neat; parentScore, leftScore, and rightScore return the score of the parent, left child, or right child respectively. There is also empty which checks if the priority queue is empty.

class PriorityQueue {
    constructor() {
        this.minheap = [];
    }

    parent(idx) {
        return Math.round(idx / 2) - 1;
    }

    parentScore(idx) {
        return this.minheap[this.parent(idx)].score;
    }

    push(state) {
        // index of added node
        let curr = this.minheap.length;
        this.minheap.push(state);

        // swap the last node up until it's in a good spot
        while(curr > 0 && state.score < this.parentScore(curr)) {
            this.minheap[curr] = this.minheap[this.parent(curr)];
            this.minheap[this.parent(curr)] = state;
            curr = this.parent(curr);
        }
    }

    left(idx) {
        return idx*2 + 1;
    }

    right(idx) {
        return idx*2 + 2;
    }

    leftScore(idx) {
        return this.minheap[this.left(idx)].score;
    }

    rightScore(idx) {
        return this.minheap[this.right(idx)].score;
    }

    hasChild(idx) {
        return this.left(idx) < this.minheap.length;
    }

    minChildIdx(idx) {
        // only one child node
        if (this.minheap[this.right(idx)] === undefined) {
            return this.left(idx);
        }

        if (this.leftScore(idx) < this.rightScore(idx)) {
            return this.left(idx);
        }

        return this.right(idx);
    }

    minChild(idx) {
        return this.minheap[this.minChildIdx(idx)];
    }

    hasSwapDown(idx) {
        if(!this.hasChild(idx)) {
            return false;
        }

        return this.minChild(idx).score < this.minheap[idx].score;
    }

    pop() {
        // save the first node for return
        let state = this.minheap[0];

        // if there is only 1 node return it
        if (this.minheap.length == 1) {
            this.minheap.pop();
            return state;
        }

        // remove last node and put it first
        this.minheap[0] = this.minheap.pop();
        let curr = 0;

        // swap the last node downward until it's in a good spot
        while(this.hasSwapDown(curr)) {
            let minIdx = this.minChildIdx(curr);
            let tmp = this.minheap[curr];
            this.minheap[curr] = this.minheap[minIdx];
            this.minheap[minIdx] = tmp;
            curr = minIdx;
        }

        return state;
    }

    empty() {
        return this.minheap.length === 0
    }
}

We can now create an instance of our priority queue and test it out.

let pq = new PriorityQueue();

pq.push({score: 5});
pq.push({score: 0});
pq.push({score: 3});
pq.push({score: 10});
pq.push({score: 1});

pq.pop();
pq.pop();
pq.pop();
pq.pop();
pq.pop();

Updating our BFS code

We'll adapt the code from the BFS tutorial. To make it suitable for 4x4 slide puzzles we'll need up replace the 3s with 4s and the 2s with 3s in the getMoves and recoverSolution functions. Also, the isSolved function will need to update the board to the 15 puzzle board.

Once that is done we can focus on the solve function. We replace the candidates array with our priority queue.

    let pq = new PriorityQueue();

We modify our states to contain a score.

    // add the starting state
    pq.push({
        board: board,      
        parent: undefined, 
        move: undefined,  
        score: inversionCount(board), 
    });

Modify our game loop to use the priority queue.

    while(!pq.empty()) {
        // get the state with the lowest score
        let current = pq.pop();

        // ...

Finally, we update the for loop (the one inside the while loop) that adds child moves for each state to add states with a score property and to use the priority queue.

        // create states from moves
        for (let idx = 0; idx < move.length; idx++) {
            let move = moves[idx];
            let nextBoard = applyMove(current.board, move);
            if (nextBoard in visited) {
                continue;
            }

            let state = {
                board: nextBoard,
                parent: current,
                move: move,
                score: inversionCount(nextBoard),
            };

            // mark visited
            visited[nextBoard] = true;

            pq.push(state);
        }

Conclusion

I hope you enjoyed this tutorial. Stay tuned for our future work. If you liked this it post or game it really helps us out to get shared on social media. The full A* solver if included below.

class PriorityQueue {
    constructor() {
        this.minheap = [];
    }

    parent(idx) {
        return Math.round(idx / 2) - 1;
    }

    parentScore(idx) {
        return this.minheap[this.parent(idx)].score;
    }

    push(state) {
        // index of added node
        let curr = this.minheap.length;
        this.minheap.push(state);

        // swap the last node up until it's in a good spot
        while(curr > 0 && state.score < this.parentScore(curr)) {
            this.minheap[curr] = this.minheap[this.parent(curr)];
            this.minheap[this.parent(curr)] = state;
            curr = this.parent(curr);
        }
    }

    left(idx) {
        return idx*2 + 1;
    }

    right(idx) {
        return idx*2 + 2;
    }

    leftScore(idx) {
        return this.minheap[this.left(idx)].score;
    }

    rightScore(idx) {
        return this.minheap[this.right(idx)].score;
    }

    hasChild(idx) {
        return this.left(idx) < this.minheap.length;
    }

    minChildIdx(idx) {
        // only one child node
        if (this.minheap[this.right(idx)] === undefined) {
            return this.left(idx);
        }

        if (this.leftScore(idx) < this.rightScore(idx)) {
            return this.left(idx);
        }

        return this.right(idx);
    }

    minChild(idx) {
        return this.minheap[this.minChildIdx(idx)];
    }

    hasSwapDown(idx) {
        if(!this.hasChild(idx)) {
            return false;
        }

        return this.minChild(idx).score < this.minheap[idx].score;
    }

    pop() {
        // save the first node for return
        let state = this.minheap[0];

        // if there is only 1 node return it
        if (this.minheap.length == 1) {
            this.minheap.pop();
            return state;
        }

        // remove last node and put it first
        this.minheap[0] = this.minheap.pop();
        let curr = 0;

        // swap the last node downward until it's in a good spot
        while(this.hasSwapDown(curr)) {
            let minIdx = this.minChildIdx(curr);
            let tmp = this.minheap[curr];
            this.minheap[curr] = this.minheap[minIdx];
            this.minheap[minIdx] = tmp;
            curr = minIdx;
        }

        return state;
    }

    empty() {
        return this.minheap.length === 0
    }
}

function recoverSolution(state) {
    let current = state;
    let solution = [];

    while (current.parent !== undefined) {
        let zeroIdx = current.move[0];
        let swapIdx = current.move[1];
        let difference = swapIdx - zeroIdx;
        
        switch(difference) {
            case 1: 
                solution.push('right');
                break;
            case -1: 
                solution.push('left');
                break;
            case 4: 
                solution.push('down');
                break;
            case -4: 
                solution.push('up');
                break;
        }

        current = current.parent;
    }

    return solution;
}

function inversionCount(board) {
    let inversions = 0;
    for (let idx = 0; idx < board.length; idx++) {
        let val = board[idx];

        for (var jdx = (idx + 1); jdx < board.length; jdx++) {
            if (board[jdx] < val && board[jdx] != 0) {
                inversions++;
            }
        }
    }

    return inversions;
}

function solvable(board) {
    let zeroIdx = board.indexOf(0);
    let row = 4 - Math.floor(zeroIdx / 4);
    let evenRow = row % 2 === 0;

    let inversions = inversionCount(board);
    let inversionsEven = inversions % 2 === 0;

    return inversionsEven ^ evenRow;
}

function applyMove(board, move) {
    // create a copy
    let newBoard = board.slice();

    let zeroIdx = move[0];
    let swapIdx = move[1];

    newBoard[zeroIdx] = newBoard[swapIdx];
    newBoard[swapIdx] = 0;

    return newBoard;
}

function getMoves(board) {
    let zeroIdx = board.indexOf(0);
    let zeroRow = Math.floor(zeroIdx / 4);
    let zeroCol = zeroIdx % 4;

    let moves = [];

    // left (col - 1)
    if (zeroCol !== 0) {
        moves.push([zeroIdx, zeroRow * 4 + (zeroCol - 1)])
    }

    // down (row + 1)
    if (zeroRow !== 3) {
        moves.push([zeroIdx, (zeroRow + 1) * 4 + zeroCol])
    }

    // right (col + 1)
    if (zeroCol !== 3) {
        moves.push([zeroIdx, zeroRow * 4 + (zeroCol + 1)])
    }

    // up (row - 1)
    if (zeroRow !== 0) {
        moves.push([zeroIdx, (zeroRow - 1) * 4 + zeroCol])
    }

    return moves;
}

function isSolved(board) {
    let solved = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0];
    
    for (let idx = 0; idx < board.length; idx++) {
        if (board[idx] !== solved[idx]) {
            return false;
        }
    }

    return true;
}

function solve(board) {
    // our queue
    let pq = new PriorityQueue();

    // track previously visited states
    let visited = new Map();

    // add the starting state
    pq.push({
        board: board,      
        parent: undefined, 
        move: undefined,  
        score: inversionCount(board), 
    });

    while(!pq.empty()) {
        let current = pq.pop();

        // check solved
        if (isSolved(current.board)) {
            // recover state
            return recoverSolution(current);
        }

        // get valid moves
        let moves = getMoves(current.board);

        // create states from moves
        for (let idx in moves) {
            let move = moves[idx];
            let nextBoard = applyMove(current.board, move);
            if (nextBoard in visited) {
                continue;
            }

            let state = {
                board: nextBoard,
                parent: current,
                move: move,
                score: inversionCount(nextBoard),
            };

            // in hindsight this isn't the best name
            // since we haven't "visited" these nodes yet
            // a more appropriate name would be seen...
            // oh well, you can deal with it
            visited[nextBoard] = true;

            pq.push(state);
        }
    } 

    return [];
}

function run(items) {
    // Connect to the websocket endpoint.
    var socket = new WebSocket("wss://pointatinfinity.com/fifteen/ws");
    var ready = false;

    // Handle messages. See /docs/fifiteen for message formats.
    let first = true;
    socket.onmessage = function(e) { 
        var state = JSON.parse(e.data);
        // Handle responses from the server, check the state here...
        
        console.log(state);
        displayState(state);

        if (state.Status === "complete") {
            return;
        }

        // make solution a global
        if (first) {
            if (!solvable(state.Board)) {
                console.log('unsat');
                return;
            }
            
            solution = solve(state.Board);
            console.log(solution);
            first = false;
        } else {
            nextMove();
        }
    };

    // Function that is called when the websocket is ready.
    function onReady() {
        ready = true;
        nextMove();
    }

    // Recursive timer loop to wait for the websocket.
    function waitReady() {
        setTimeout(function() {
            if(socket.readyState === 1 && solution) {
                onReady();
            } else {
                waitReady();
            }
        }, 100);
    }

    function nextMove() {
        let move = solution.pop();
        send(move);
    }

    // Helper function to visualize state.
    function displayState(state) {
        for(var idx in state.Board) {
            var cell = document.getElementById("cell_" + idx);
            var style = 'url("/bin/tiles/' + state.Board[idx] + '.png")';
            cell.style['background-image'] = style;
        }
    
        var status = document.getElementById("status");
        status.innerText = state.Status;

        var score = document.getElementById("score");
        score.innerText = state.Score;      
    }

    // Send function for the buttons and to demonstrate message format.
    window.send = function(move) {
        if (!ready) {
            return;
        }
        socket.send(JSON.stringify({Move: move}));
    }
    
    waitReady();
}

// Run the code when executed.
run();