Solving 8-puzzle using breadth-first search
During the Andela-Stack Overflow mentorship programme, my mentor Nick, gave me a task to solve 8-puzzle using the breadth-first search algorithm.
In this post, I would try to explain my solution.
You can visit my gist to view the full implementation, but I would explain some methods I used here.
function time() {
startTime = new Date();
var puzzle = generatePuzzle();
console.log('Puzzle to solve', puzzle);
var result = breadthFirstSearch(puzzle, goalState);
console.log(result.length);
endTime = new Date();
console.log('Operation took ' + (endTime.getTime() - startTime.getTime()) + ' msec');
}I am using this function to calculate the total execution time of the program. In this method I am calling the generatePuzzle function to generate a random puzzle.
function generatePuzzle() {
var arr = [];
while(arr.length < 9){
var randomNumber = Math.floor(Math.random()*9);
var found = false;
for(var i = 0; i < arr.length; i++){
if(arr[i] == randomNumber){
found = true;
break;
}
}
if(!found) {
arr[arr.length] = randomNumber;
}
}
if(!checkSolvable(arr)) {
console.log('\n This puzzle: ' + arr + ' is unsolvable. \n Generating a new one \n');
return generatePuzzle();
}
return arr;
}The generatePuzzle function generates a random puzzle and almost half of the existing N-puzzles are unsolvable, so I wrote another function to check if the puzzle is solvable or not, so we won’t expend stupid mental effort.
function checkSolvable(state) {
var pos = state.indexOf(0);
var _state = state.slice();
var count = 0;
_state.splice(pos,1);
for (var i = 0; i < _state.length; i++) {
for (var j = i + 1; j < _state.length; j++) {
if (_state[i] > _state[j]) {
count++;
}
}
}
return count % 2 === 0;
}Thanks to Tushar’s post on stack exchange, I was able to write the method to check if the generated puzzle is solvable.
After all that preamble which is very useful, I called the breadthFirstSearch method
function breadthFirstSearch(state, goalState) {
state.prev = null;
allSuc.push(state);
allSuc.push.apply(allSuc, getSuccessors(state));
for (var i = 1; i < allSuc.length; i++) {
statesPerSecond();
if (compare(goalState, allSuc[i])) {
return collateStates(i);
} else {
allSuc.push.apply(allSuc, getSuccessors(allSuc[i]));
}
}
}What I am doing in breadthFirstSearch method is to find the successors - possible moves - of a state and add them to the allSuccessors array. The allSuccessors array is an open list of the states both yet to be evaluated and those I have evaluated.
Breadth First Search makes use of a Queue so I push the successors to the end of the allSuccessors array to mimic that behavior
One big optimization I did was with here, Initially I wrote this
allSuc = allSuc.concat(getSuccessors(allSuc[i]));
but I discovered that it is not scalable because with concat, js is creating a new array, which is O(n) runtime. However with the new modification,
allSuc.push.apply(allSuc, getSuccessors(allSuc[i]));
push.apply is acting on the existing array, and that’s O(1) regardless of the size.
After that, I am calling the statesPerSecond method to get the number of states evaluated in a second, after which I called a compare method to check if the present state is the same with the goal state, if true call the collateStates method
function collateStates(i) {
var _ = allSuc[i].prev;
var result = [allSuc[i]];
while (_) {
for (var j = 0; j < allSuc.length; j++) {
if (compare(_, allSuc[j])) {
_ = allSuc[j].prev;
result.push(allSuc[j]);
break;
}
}
}
console.log(allSuc.length);
return result.reverse();
}Also, I check if the state has been checked before. If the state has been checked before, then I do not want to check it again. Previously, I was using an array and looping through to check if the state exists which is O(n) runtime. To improve that, I used a hash which has O(1) runtime for lookups.
Another method I need to explain is the getSuccessors method. This was the initial method that set the ball rolling for me, thanks to Nick for putting me through.
function getSuccessors(state) {
var successors = [];
var pos = state.indexOf(0);
var row = Math.floor(pos / 3);
var col = pos % 3;
if (row > 0) {
//move up
move(state, successors, pos, -3);
}
if (col > 0) {
//move left
move(state, successors, pos, -1);
}
if (row < 2) {
//move down
move(state, successors, pos, 3);
}
if (col < 2) {
//move right
move(state, successors, pos, 1);
}
return successors;
}I checked the position of the empty space which is denoted by ‘0’ and find whether it can move either move, up, left, center and I call the move method
function move(state, successors, pos, steps) {
var _state, newState;
newState = state.slice();
swap(newState, pos, pos + steps);
if (!compare(newState, state.prev)) {
_state = newState.join('');
if (typeof hash[_state] === 'undefined') {
hash[_state] = newState;
newState.prev = state;
successors.push(newState);
}
}
}This performs some critical checks
- Checks if the current state is not equal to the previous state, this is to avoid infinite loops because if we allow such then a state can be going up and down till the end of the program.
- Also, I check if the state has been checked before. If the state has been checked before, then I do not want to check it again. In implementing this, I was using an array and looping through to check if the state exists, this is O(n) which is bad to the program, so instead I used a hash which has O(1), especially when finding.
and with that I solved the puzzle.
Do I think it can be more optimize? Yes!
Am I working on improving it? Yes!
Can you suggest ways to improve this? Of course Yes! Please use the comment section.
Currently working on implementing this with A* algorithm, Nick said that is way faster. So my next blog post should be that
If you liked this post, you can share it with your followers or follow me on Twitter!