Eight slide puzzle and breadth-first search

In this post you'll be getting a walkthrough on how to solve the eight slide puzzle using breadth-first search (BFS). BFS is an algorithm for traversing (or searching) tree structures. It is usally taught alongside depth-first search (DFS). To visually understand these algorithms, see the following animation.

tree traversal animation

DFS traverses all the way down branches before back tracking and going down the next branch. That is, it optimzes for depth, hence the name... BFS on the other hand, it visits all nodes at the current depth before moving deeper.

Slide puzzle representations

What do trees have to do with slide puzzles? Well, if we make the nodes of the tree a state of the puzzle (some specific configuration of tiles), then the branches would be the moves that are possible to make from that state.

slide puzzle states represented as a tree

Using BFS to traverse this tree will give us a solution in as few moves as possible.

How Eight represents the game

Right now would be a good time to look at the docs. I'll give the tl;dr here though.

The board is represented as an array of values. This is just a flattened board where indices 0 through 2 represent the first row, 3 through 5 represent the second, and 6 through 8 represent the third.

[1, 2, 3, 4, 5, 6, 7, 8, 0]

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 0 |

Moves are the strings left, down, right, and up. A left move would swap the zero tile | 0 | with the tile to its left (in this case | 8 |). Moves are sent to the server as JSON in the following structure.

{
    Move: 'move'
}

High level algorithm

Starting out, it is good to get a sketch of your code in comments. For each state, this is the high level algorithm we're going to follow.

// check solved

// get possible moves (left, down, right, up)

// eliminate invalid moves

// eliminate previously visited states

// enqueue moves

// visit next state

Implementation

Checking solved

First things first, we need to check if our current state is the solved state.

function isSolved(board) {
    let solved = [1, 2, 3, 4, 5, 6, 7, 8, 0];
    
    for (let idx in board) {
        if (board[idx] !== solved[idx]) {
            return false;
        }
    }

    return true;
}

We will have a solved state and iterate over the indices of the board array, if any values don't match that of the solved state we will return false. If we complete the loop successfully, we know that the value at each index matched, so we will return true.

Get possible moves

If the board is not solved we generate some more states. In order to do this, we will need to get the left, down, right, and up moves for the current state. We're going to represent moves with the index of zero in the board array and the index of the tile it is swapping with. For the board [1, 2, 3, 4, 5, 6, 7, 8, 0] and move left we would produce the [zeroIdx, swapIdx] pair [8, 7].

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

    let moves = [];

    // left (col - 1)
    moves.push([zeroIdx, zeroRow * 3 + (zeroCol - 1)])

    // down (row + 1)
    moves.push([zeroIdx, (zeroRow + 1) * 3 + zeroCol])

    // right (col + 1)
    moves.push([zeroIdx, zeroRow * 3 + (zeroCol + 1)])

    // up (row - 1)
    moves.push([zeroIdx, (zeroRow - 1) * 3 + zeroCol])

    return moves;
}

Get valid moves

That's great but some of the moves we're returning are invalid. Rather than trying to figure this out after we get the moves, we can just modify the getMoves function to only return valid moves. The basic idea is that if the column is zero, we can't move left, if the column is two we can't move right. If the row is zero we can't move up, and if the row is two we can't move down.

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

    let moves = [];

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

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

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

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

    return moves;
}

Eliminate previously visited states

In order to track previously visited states we'll use a JavaScript Map. This will provide us a fast lookup, we can just ask if the current state is in the map of previously visited states, and skip it if it is.

let visited = new Map();

Solver function check in

Our solver function will take in the initial board state, then go through the algorithm we outlined above in comments. Since we have some functions written we can start filling this out. We'll use a state (different from the state received from the server) that contains the board, the move used to get from the previous state to this one, and a link back to the previous state. The board will allow us to apply its valid moves to reach the next state. The parent state will allow us to walk back up the chain of states and recover the moves that make up the solution. The move, well... the move is what we're after.

function solve(board) {
    // our queue
    let candidates = [];

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

    // add the starting state
    candidates.push({
        // current board
        board: board,      
        // the parent state that the move was applied to 
        parent: undefined, 
        // the move used to get here
        move: undefined,   
    });

    while(candidates.length) {
        // remove states from the front
        let current = candidates.shift();

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

            visited[nextBoard] = true;

            candidates.push(state);
        }
    } 

    return [];
}

Filling in the blanks

We threw in two placeholder functions in the last snippet, recoverSolution and applyMove. We'll start with applyMove. We need a function that copies the board array then applies the swap indicies. If we don't copy the board we'll be applying the change to the board reference, which would affect it in all the other states.

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

Now we need to recover the moves that reached our solved state. An example current state at the time of solve is shown below.

let current = {
    board: [1, 2, 3, 4, 5, 6, 7, 8, 0],
    move: (7, 8),
    parent: {
        board: [1, 2, 3, 4, 5, 6, 7, 0, 8],
        move: (6, 7),
        parent: {
            board: [1, 2, 3, 4, 5, 6, 0, 7, 8],
            move: (3, 6),
            parent: {
                board: [1, 2, 3, 0, 5, 6, 4, 7, 8],
                move: (6, 7),
                parent: undefined,
            },
        },
    },
};

The innermost parent is our starting state [1, 2, 3, 0, 5, 6, 4, 7, 8]. It has no parent. So as we walk back up and recover our chain of moves our terminating condition will be reaching the state with no parent. The one tricky thing, and we probably could have stored this, is the server wants the text representation of the move, not the swap indices.

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 3: 
                solution.push('down');
                break;
            case -3: 
                solution.push('up');
                break;
        }

        current = current.parent;
    }

    return solution;
}

We use push for each move so that they are in reverse order. This allows us to simply pop them as we send them to the server though.

Putting it all together

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 3: 
                solution.push('down');
                break;
            case -3: 
                solution.push('up');
                break;
        }

        current = current.parent;
    }

    return solution;
}

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 / 3);
    let zeroCol = zeroIdx % 3;

    let moves = [];

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

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

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

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

    return moves;
}

function isSolved(board) {
    let solved = [1, 2, 3, 4, 5, 6, 7, 8, 0];
    
    for (let idx in board) {
        if (board[idx] !== solved[idx]) {
            return false;
        }
    }

    return true;
}

function solve(board) {
    // our queue
    let candidates = [];

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

    // add the starting state
    candidates.push({
        // current board
        board: board,      
        // the parent state that the move was applied to 
        parent: undefined, 
        // the move used to get here
        move: undefined,   
    });

    while(candidates.length) {
        // remove states from the front
        let current = candidates.shift();

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

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

            candidates.push(state);
        }
    } 

    return [];
}

Add some meat to our skeleton code

All that code should be above the provided skeleton code now. You can also paste it into your browser console (F12 to open dev tools, select the tab console) and test it out. solve([1, 2, 3, 0, 5, 6, 4, 7, 8]). You should see the solution ["right", "right", "down"] (remember, it's in reverse order). Let's put that solution to use!

Let's learn a little about how websockets work. You connect to the websocket endpoint wss://pointatinfinity.com/eight/ws by creating a new Websocket object.

var socket = new WebSocket("wss://pointatinfinity.com/eight/ws");

We provide an onmessage callback that the websocket will call any time it receives a message. It passes in the message it got, the JSON from the server is in the .data property. Since the server sends a message with the starting state upon connection, this will be a good place to call our solve function.

    socket.onmessage = function(e) { 
        var state = JSON.parse(e.data);
        // Handle responses from the server, check the state here...
        
        console.log(state);
        displayState(state);

        // make solution a global
        solution = solve(state.Board);
        console.log(solution);
    };

TODO(tacixat): check assumption that ws can be not ready if it has received state from the server

Websockets take a second or so to get into a ready state, if you try to send stuff on them immediately it can fail. For this reason, we have a little setTimeout loop that waits for the websocket to be ready. We can use this to also wait for our solution to be ready by adding an && solution to the ready check. Once it is ready we can kick off the party with our (not yet created) nextMove function.

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

Since we have our solution and the websocket is ready, we can send moves. The function nextMove will pop a move off of our solution array and send it to the server. There is already a send function that wraps our string move in the structure it needs to be, converts it to JSON, then fires it off to the server, so we'll use that.

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

That's great for the first move, but what about all the rest? Since the server sends back the state after every move we can use that as the trigger to send the next. We'll modify our onmessage function to look at a global variable first to know if it is the first move or not. (Note: it's not actually a global, it's scoped to the run function, but to onmessage it is effectively global). We will also check if the state.Status is complete and just return if it is.

    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) {
            solution = solve(state.Board);
            console.log(solution);
            first = false;
        } else {
            nextMove();
        }
    };

Putting it all together II

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 3: 
                solution.push('down');
                break;
            case -3: 
                solution.push('up');
                break;
        }

        current = current.parent;
    }

    return solution;
}

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 / 3);
    let zeroCol = zeroIdx % 3;

    let moves = [];

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

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

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

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

    return moves;
}

function isSolved(board) {
    let solved = [1, 2, 3, 4, 5, 6, 7, 8, 0];
    
    for (let idx in board) {
        if (board[idx] !== solved[idx]) {
            return false;
        }
    }

    return true;
}

function solve(board) {
    // our queue
    let candidates = [];

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

    // add the starting state
    candidates.push({
        // current board
        board: board,      
        // the parent state that the move was applied to 
        parent: undefined, 
        // the move used to get here
        move: undefined,   
    });

    while(candidates.length) {
        // remove states from the front
        let current = candidates.shift();

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

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

            candidates.push(state);
        }
    } 

    return [];
}

function run(items) {
    // Connect to the websocket endpoint.
    var socket = new WebSocket("wss://pointatinfinity.com/eight/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) {
            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();

Conclusion

I hope you enjoyed this tutorial. Your next challenge is the 15 puzzle. BFS won't work there so you'll learn about A*. A* is the path finding algorithm most popular with game bots. Take your skills to the next level, play now!