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.
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.
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
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,
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
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
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