Solving 8 puzzle: building the graph
I am starting my journey into AI and it seems like a study of search is a primary requisite for the space. The initial coming of age problem looks to be a simple puzzle, Eight Puzzle. I was introduced to the puzzle as child, and was reminded of that as I returned 40 yrs later.
My first puzzle was not too unlike the cat puzzle to the left. Instead of consisting of a 4x4 with 15 moving pieces, my toy was 3x3 with 8 moving pieces (oh, and it was a train moving down some tracks). The game allows you to slide a piece into the blank slot and concludes when you solve the problem by reproducing the image. It turns out there are more variants where each tile is a a number, and the solution is to put the numbers in order. Regardless of whether the tile have images on them or display their numerical value, the numerical value is the right way to solve this computationally (at least in this point in my AI journey).
The first decisions was how to represent the board. I wanted to keep this simple so I decided that my board should be represented as a a 1 x 9 array with each element selected (without replacement) from the set { 1,2,3,4,5,6,7,8, null }. There are 9 choose 9 permutations = 362,880 of the board, are best represented as a graph.
The board changes state by sliding a tile into the vacant spot. By leveraging an array to represent board state, you need to first determine where the empty (null) spot is.
Once you identify the empty cell, you can determine whether another cell can slide into that spot with a few calculations: 1, take the difference between the index of the empty cell and that of every other cell; 2. cells one unit apart from each other can slide left or right and cells three units from each other can slide up or down; 3. you need to be conscious of sliding one unit from different rows, that is not a legal move. That code looks like:
// boardPermutation is an array of all possible premutations
boardPermutations.map(permutation => {
const emptyIndex = permutation.findIndex(x => x == null)
const allowLeft = emptyIndex % 3 != 2
const allowRight = emptyIndex % 3 != 0 const moves = permutation.map((state, index) => {
const delta = emptyIndex - index
return {index, delta} }).filter(node => {
return node.delta == 1 && allowRight
|| node.delta == -1 && allowLeft
|| Math.abs(node.delta) == 3 }).map(node => {
let label = ""
if (node.delta == 1 && allowRight) {
label = "RIGHT"
} else if(node.delta == -1 && allowLeft) {
label = "LEFT"
} else if(node.delta == 3) {
label = "DOWN"
} else if(node.delta == -3) {
label = "UP"
}
const nextPermutation = permutation.slice(0)
const temp = nextPermutation[emptyIndex]
nextPermutation[emptyIndex] = nextPermutation[node.index]
nextPermutation[node.index] = temp return nextPermutation
})
})
To understand how many edges we will need to add its useful to envision the number of possible moves if any given cell was null:
There are on average 2.66 moves across all possible board states. When multiplied by the 362,880 board states that equates to 967,680 possible moves. Each of these moves (as indicated by board state / transition graphic) becomes an edge in our graph.
In defining the graph, I wanted to favor readability over efficiency, and liked the way this flowed(psuedo):
const graph = Graph()
graph.addNode( Node("a") )
graph.addNode( Node("b") )
graph.from("a").to("b").withEdge("a-to-b", Edge.UNIDIRECTIOAL)In 8 Puzzle, the Node has both an id and a value and we instantiate with both components Node("1,,6,2,3,5,4,7,8", [1,null,6,2,3,5,4,7,8]); Edges have a cost (of 1 unit) associated with them and are also constructed with that value.
To generate the complete graph we need to generate all 362,880 permutations of the board. This function was nabbed of of stack (https://stackoverflow.com/questions/27177026/derive-every-possible-combination-of-elements-in-array):
function makePermutations(length, data) {
const current = new Array(length)
, used = new Array(length)
, seen = {}, result = [];
function permute(pos) {
if (pos == length) {
if (!seen[current]) {
seen[current] = true;
result.push(current.slice());
}
return;
}
for (var i = 0; i < data.length; ++i) {
if (!used[i]) {
used[i] = true;
current[pos] = data[i];
permute(pos+1);
used[i] = false;
}
}
}
permute(0);
return result;
}And are able to create all possible board permutations via:
const boardPermutations = makePermutations(9, [1,2,3,4,5,6,7,8,null])I chose to write a script to build the graph and independently save it to a file, so I could just “require” it into memory. I thought it would save time over dynamic generation each time I wanted to run the model. It turns out, relative to search time, the loading was trivial — but I will provide that goodness nonetheless:
const fs = require('fs')
const {makePermutations} = require("../../../utility/array-permutations")
// make all combinations of where the elements can be
const boardPermutations = makePermutations(9, [1,2,3,4,5,6,7,8,null])
const answer = [null,1,2,3,4,5,6,7,8]
const builder = fs.createWriteStream('./eight-puzzle-graph.js')
builder.write(`const {Graph, Edge, Node} = require("../../../abstract-data-types/graph.js")\n`)
builder.write(`const graph = Graph()\n`)
// add each permutation of the board to the graph
boardPermutations.map(permutation => {
builder.write(
`graph.addNode(Node("${permutation.join(",")}",
[${permutation}], ${h(permutation, answer)}))\n`)
})
// identify and add edges
boardPermutations.map(permutation => {
const emptyIndex = permutation.findIndex(x => x == null)
const allowLeft = emptyIndex % 3 != 2
const allowRight = emptyIndex % 3 != 0
const moves = permutation.map((state, index) => {
const delta = emptyIndex - index
return {index, delta} }).filter(node => {
return node.delta == 1 && allowRight
|| node.delta == -1 && allowLeft
|| Math.abs(node.delta) == 3 }).map((node) => {
let label = ""
if (node.delta == 1 && allowRight) {
label = "RIGHT"
} else if(node.delta == -1 && allowLeft) {
label = "LEFT"
} else if(node.delta == 3) {
label = "DOWN"
} else if(node.delta == -3) {
label = "UP"
}
label += `(${permutation[node.index]})`
const nextPermutation = permutation.slice(0)
const temp = nextPermutation[emptyIndex]
nextPermutation[emptyIndex] = nextPermutation[node.index]
nextPermutation[node.index] = temp
builder.write(
`graph.from("${permutation.join(",")}").
to("${nextPermutation.join(",")}").
withEdge(Edge("${label}", 1, Edge.UNIDIRECTIOAL))\n`)
})
})
builder.write(`module.exports = graph\n`)
builder.end()
In my next article I will walk through my search implementation.
- “working example”: https://github.com/tb01923/aima-js/blob/main/search/eight-puzzle/eight-puzzle-graph-generator.js
