Table of contents
This puzzle was invented by Noyes Palmer Chapman in the 1870s. This is played on a 3-by-3 matrix with 8 elements labelled from 1 to 8 and one blank space. This is a state space search problem in which the starting state and goal state is given and you have to reach from the start state to the goal state showing its path.
This problem can have more than one solution. This problem can be solved using various approaches like Breadth First Search(BFS), Depth First Search(DFS), Best First Search, A algorithm, A* algorithm, AO* algorithm, etc. Among these BFS and DFS are blind search methods while the rest are heuristic search methods.
In this article, we are going to see the solution to the 8-puzzle problem using the BFS approach.
Breadth First Search(BFS)
BFS is a graph traversal algorithm in which we traverse all the nodes level-by-level. It maintains two different queues- the visited queue and exploration queue. The visited queue stores the nodes which have been traversed and the exploration queue stores the nodes which need to be traversed.
You can use any programming language for solving the 8-puzzle problem using BFS but I recommend you to use python because python is a versatile language.
This is my code for the solution:-
import copy
from collections import defaultdict
# start state
s = [[0,0,0],[0,0,0],[0,0,0]]
# goal state
g = [[0,0,0],[0,0,0],[0,0,0]]
bl = 0
for i in range(3):
for j in range(3):
s[i][j] = input()
seq = {str(s): '-1'}
visited = {}
visited = defaultdict(lambda: False,visited)
visited[str(s)] = True
exploration = [s]
for i in range(3):
for j in range(3):
print(s[i][j],end=" ")
print()
for i in range(3):
for j in range(3):
g[i][j] = input()
for i in range(3):
for j in range(3):
print(g[i][j],end=" ")
print()
print()
def a(arr1):
ins = 1
if visited[str(arr1)]:
ins = 0
if ins == 1:
exploration.append(arr1)
visited[str(arr1)] = True
seq[str(arr1)] = arr
matched = 1
for i in range(3):
for j in range(3):
if g[i][j] != arr1[i][j]:
matched = 0
return matched
while True:
arr = exploration.pop(0)
for i in range(3):
for j in range(3):
if arr[i][j] == "*":
bl = i * 3 + j
if (bl+1)%3 != 0:
arr1 = copy.deepcopy(arr)
arr1[int(bl/3)][bl%3], arr1[int(bl/3)][(bl%3)+1] = arr1[int(bl/3)][(bl%3)+1], arr1[int(bl/3)][bl%3]
matched = a(arr1)
if matched == 1:
break
if (bl%3) != 0:
arr1 = copy.deepcopy(arr)
arr1[int(bl / 3)][bl % 3], arr1[int(bl / 3)][(bl % 3) - 1] = arr1[int(bl / 3)][(bl % 3) - 1], arr1[int(bl / 3)][
bl % 3]
matched = a(arr1)
if matched == 1:
break
if int(bl/3) != 0:
arr1 = copy.deepcopy(arr)
arr1[int(bl / 3)][bl % 3], arr1[int(bl / 3)-1][bl % 3] = arr1[int(bl / 3)-1][bl % 3], arr1[int(bl / 3)][
bl % 3]
matched = a(arr1)
if matched == 1:
break
if int(bl/3) != 2:
arr1 = copy.deepcopy(arr)
arr1[int(bl / 3)][bl % 3], arr1[int(bl / 3) + 1][bl % 3] = arr1[int(bl / 3) + 1][bl % 3], arr1[int(bl / 3)][
bl % 3]
matched = a(arr1)
if matched == 1:
break
ans_arr = []
temp = g
i = 0
while temp!='-1':
ans_arr.append(temp)
temp = seq[str(temp)]
i+=1
print("Path from given state to goal state:-", end="\n\n")
dpt = 0
while i>0:
dpt+=1
arr = ans_arr.pop()
for j in range(3):
for k in range(3):
print(arr[j][k], end=" ")
print()
print()
i-=1
print("depth = " + str(dpt-1))
print("Time Complexity = O(" + str(pow(3,dpt-1)) + ")")
Output
1
2
3
4
*
6
7
5
8
1 2 3
4 * 6
7 5 8
1
2
3
4
5
6
7
8
*
1 2 3
4 5 6
7 8 *
Path from given state to goal state:-
1 2 3
4 * 6
7 5 8
1 2 3
4 5 6
7 * 8
1 2 3
4 5 6
7 8 *
depth = 2
Time Complexity = O(9)
The above solution is highly optimized and can find the solution to any puzzle from the easiest to the toughest in at most 10 seconds.