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.

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.

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.

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

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

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.

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

This performs some critical checks

1. 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.
2. 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!