8 Puzzle solver in Python

A Python implementation of 4 diffrent algorithms to solve the 8-puzzle game using pygame for the GUI.

---

Table of content:

1. Installing pygame and pygame-menu
2. Application Overview
3. Play Mode
4. Experimental Mode and the algorithms used
   1. bfs
   2. dfs
   3. limited dfs
   4. A*
5. Conclution

1.Installing pygame and pygame-menu:

pygame : pip install pygame
pygame-menu: pip install pygame-menu -U
Pygame-menu is a python-pygame library for creating menus and GUIs

2.Application Overview:

This application is divided into two sections :

• experimental mode🧪: experimental mode allows you to solve the 8-puzzle game with 4 different algorithms and count the number of visited nodes in each algorithme
• play mode 🎮: play Mode allows you to try and beat the game yourself.

---

3.Play Mode:

You can increase the difficulty of the game by increasing the SHUFFLE_NUMBER constant.

4.Experimental Mode and the algorithms used:

You can change the start and the target bord by changing this constants:

BORD=[
    [3,2,7],
    [8,6,0],
    [1,5,4]
]
TARGET=[
    [1,2,3],
    [8,0,4],
    [7,6,5]
]

4.1.bfs:

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

4.2.dfs:

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

4.3.limited dfs :

limited dfs is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found.

4.4.A*:

A* is a heuristic algorithm sacrifices optimality, with precision and accuracy for speed, to solve problems faster and more efficiently.

5.Conclution:

After running these algorithms we get this:

we can notice that the number of visited nodes in the A* algorithm is the smallest and the limited dfs(with a limit of 3) does not have a solution(-1)

made by amine-a11 && mehrezbey