 # 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. 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. 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;
let swapIdx = move;

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;
let swapIdx = current.move;
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;
let swapIdx = current.move;
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;
let swapIdx = move;

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.
nextMove();
}

// Recursive timer loop to wait for the websocket.
setTimeout(function() {
if(socket.readyState === 1 && solution) {
} else {
}
}, 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;
let swapIdx = current.move;
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;
let swapIdx = move;

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.
nextMove();
}

// Recursive timer loop to wait for the websocket.
setTimeout(function() {
if(socket.readyState === 1 && solution) {
} else {
}
}, 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) {
return;
}
socket.send(JSON.stringify({Move: move}));
}