Solving The Eight Puzzle Problem And Its Visualization withTkinter
Introduction
The Eight puzzle problem is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. It was invented and popularized by Noyes Palmer Chapman in the 1870s. It is a smaller version of n puzzle problem which is a classical problem for modeling algorithms involving heuristics. If the square frame size is 3×3 tiles, the puzzle is called the 8-puzzle.
Problem Background
The goal of the problem is to attain the destination configuration from source configuration by sliding the empty tile vertically or horizontally in each move. This is aimed to be done in minimum number of moves possible.
The destination state exists as a reachable or unreachable state from the source state. No matter how many moves are made some states can be unreachable from the source state.
Finding the shortest solution is a NP-Hard problem, so an exhaustive search is employed along with heuristics for better efficiency.
Initially source and destination states are passed as input and the list of steps to reach to destination is returned.
Approaches
The following are the possible approaches to solve the puzzle :
Depth first Search (DFS)
It is a recursive technique exploring all possible states until it finds the destination state. The visiting of child nodes occur before adjacent nodes.
// pseudocode
func dfs (src , dest):
if src is dest: return all the visited states
add src to visited states
for move in all_possible_moves_from(src):
if move not in visited states :
return dfs(move ,dest)
return Not foundIterative Deepening DFS
The disadvantage of DFS is that it explores all the levels starting from the root without exploring all adjacent nodes of the previous levels. This can lead to stack overflow problems or a slower solution if the destination is in one of the other nodes of the current level. Hence, in iterative deepening, DFS is performed through increments of maximum level threshold.
// pseudocode
func iterdfs(max_depth):
while i < max_depth:
res = dfs(src , dest, i) // performs dfs only till level i
if res != Not found:
return res
i = i + 1
return Not FoundBreadth First Search (BFS)
Though Iterative deepening can solve the problems of DFS, but it is inefficient as it takes multiple iterations of DFS. The Breadth first search is an iterative approach exploring all the adjacent positions before exploring the next level moves. It makes use of a queue which might add too much memory while solving in a large search space.
// pseudocode
func bfs(src, dest)
create a queue q
q.push(src)
while q is not empty:
c = q.pop()
if c is dest: return all visited states
add c to visited states
for move in all_possible_moves_from(c):
if move not in visited states :
q.push(c)
return Not foundA* Algorithm
This approach may use either BFS or DFS but only some moves are selected that minimize the following cost function :
f(n) = h(n) + g(n) (h(n) is the heuristic function and g(n) is the distance from source state)The definition of the heuristic h(n) makes the search intelligent. This function in the current approach sums up all the mismatching tiles. The distance g(n) from source is just the number of steps taken. The below is the pseudocode for DFS and BFS:
// pseudocode
func A*dfs (src , dest):
if src is dest: return all the visited states
add src to visited states
possible_moves = all_possible_moves_from(src):
scores = h(possible_moves, target) + g
selected_moves = possible_moves with min(scores)
for move in selected_moves:
if move not in visited states :
return dfs(move ,dest)
return Not Foundfunc A*bfs(src, dest)
create a queue q
q.push(src)
while q is not empty:
c = q.pop()
if c is dest: return all visited states
add c to visited states
possible_moves = all_possible_moves_from(c):
scores = h(possible_moves, target) + g
selected_moves = possible_moves with min(scores)
for move in selected_moves :
if move not in visited states :
q.push(c)
return Not found
The cost function parameters are computed as follows:
// pseudocode
def h(move,target): //heuristic function
for e1,e2 in zip(move, target):
if e1!=e2: sum+=1
return sum and g is the current_depth in DFS or BFS searchf = h(move,target) + g
with the given details the implementation of the algorithm is straight forward.
Building GUI with TKinter
Tkinter is Python’s de-facto standard GUI (Graphical User Interface) package. It is a thin object-oriented layer on top of Tcl/Tk. It provides various configurable GUI widgets and utilities.
The complete coding approach of A* algorithm is already discussed above which is integrated with the Tkinter UI, built as follows:
Setting up the Frame
Inside the root a frame widget is defined with all the other widgets. The label , reset button and speed control buttons are placed, along with the puzzle objects.
self.label = tk.Label(self, text="Let's solve the eight puzzle Problem", font=('Verdana', 15, 'bold'))
self.label.pack(side=tk.TOP)
self.score = tk.Label(self, text=" ", font=('Verdana', 10, 'bold'))
self.score.pack(side=tk.TOP, anchor=tk.NE)
self.reset = tk.Button(self, text="Reset", bg="grey", fg="white", command=self.stop_animation)
self.reset.pack(side=tk.LEFT, anchor=tk.N)
self.increase_speed = tk.Button(self, text="inc_speed", bg="grey", fg="white", command=self.inc_speed)
self.increase_speed.pack(side=tk.RIGHT, anchor=tk.N)
self.decrease_speed = tk.Button(self, text="dec_speed", bg="grey", fg="white", command=self.dec_speed)
self.decrease_speed.pack(side=tk.RIGHT, anchor=tk.N)// in init function
self.puzzle_src = Puzzle(self, {"tile_color": "red", "text": "Start Configuration"})
self.puzzle_dest = Puzzle(self, {"tile_color": "blue", "text": "Destination Configuration"})
The puzzle widget is created by arranging buttons in a two-dimensional grid in a separate Puzzle class inheriting the frame widget.
def draw_puzzle(self):
for i in range(3):
for j in range(3):
self.b[i].append(self.button())
self.b[i][j].config(command=lambda row=i, col=j: self.fill(row, col))
self.b[i][j].grid(row=i, column=j)def fill(self, i, j):
self.b[i][j].config(text=self.index, state=tk.DISABLED, bg="black", fg="white")
self.algo_value[i * 3 + j] = self.index
self.index += 1
if self.index == 9:
self.mark_tile()
self.val.config(text=str(self.algo_value))
Integrating with the Algorithm
Recursive A* implementation is used as follows :
def gui_search(self, src, target, visited_states, g=0):
if src == target or self.stop:
self.puzzle_src.set_state(target, self.speed) //update state
return True
visited_states.append(src)
adj = possible_moves(src, visited_states)
scores = []
selected_moves = []
for move in adj: scores.append(h(move) + g)
if len(scores) == 0:
min_score = 0
else:
min_score = min(scores)
for i in range(len(adj)):
if scores[i] == min_score: selected_moves.append(adj[i])
for move in selected_moves:
self.set_score(min_score, g + 1)
self.puzzle_src.set_state(move, self.speed) //update state
if self.gui_search(move, target, visited_states, g + 1): return True
return False// the stop flag is set by the reset button to stop algorithm execution
// the speed variable is used to control the rate of display by //calling python sleep// in puzzle's set_statedef set_state(self, move: list, speed: float):
curr_row, curr_col = self.get_corr(self.algo_value.index(-1))
new_row, new_col = self.get_corr(move.index(-1))
b1, b2 = self.b[curr_row][curr_col], self.b[new_row][new_col]
prop1, prop2 = self.get_prop(b1), self.get_prop(b2)
self.set_prop(prop2, b1)
self.set_prop(prop1, b2)
self.algo_value = move[:]
self.update()
sleep(speed)
The algorithm runs in parallel in a separate thread which is initialized as follows :
// called in init function
def start_background_task(self):
self.t1 = Thread(target=self.algo_update)
self.t1.setDaemon(True)
self.t1.start()// function that executes the algorithm in parallel
def algo_update(self):
while True:
while not (self.puzzle_src.is_set() and self.puzzle_dest.is_set()) or self.done:
if self.stop is True: self.done = False
self.stop = False
visited_states = []
res = self.gui_search(self.puzzle_src.algo_value, self.puzzle_dest.algo_value, visited_states)
if self.stop is True:
messagebox.showinfo("Debug", "Resetting Widgets")
self.reset_puzzle()
elif res is True:
messagebox.showinfo("Debug", "solution is reached !!")
elif not res:
messagebox.showinfo("Debug", "solution does not exist")
self.done = True
The speed of the algorithm in controlled by setting the speed variable to a value used in the python sleep function. The implementation of the remaining helper and handler functions are simple and can be found here.
check out the full code here in python : https://github.com/praguna/ai-puzzels/tree/master/eight_puzzle
clone this repository and run the main function
Verifying it Works
THANKS FOR GOING THROUGH, HAVE A NICE DAY :)
