AI Puzzle Solver

This GitHub repository contains Python implementations of various puzzle-solving algorithms for a 10x10 grid puzzle. The puzzle involves filling a grid with colored blocks and finding the optimal sequence of moves to clear the last row. The implemented algorithms include

Introduction

The AI Puzzle Solver is a Python application that uses Pygame for graphical representation and implements various search algorithms to solve puzzles. The main focus is on searching algorithms such as Depth-First Search, Breadth-First Search, A*, Uniform Cost Search, and others.

Algorithms

The following search algorithms are implemented:

• Depth-First Search (DFS)
• Breadth-First Search (BFS)
• Depth-Limited Search (DLS)
• Iterative deepening depth-first search (IDLS)
• Uniform Cost Search (UCS)
• Greedy Best-First Search
• A Search

screenshot from game

Algorithm analysis and comparison

Algorithm analysis and comparison

Algorithm analysis and comparison

Algorithm analysis and comparison

Algorithm analysis and comparison

Name	Greedy	A*	BFS	DFS	DLS	IDLS	UCS
Total State	51	18635	136975	217	648443	501328	107538
Path	5	5	5	17	6	5	5
Space (KB)	19	7279	53498	84	253298	195831	42030
Time (ms)	2	1943	15604	12	25444	19817	12855
Complete	YES	YES	YES	YES	NO	YES	YES
Optimal	YES	YES	YES	NO	NO	YES	YES

Agent Specification ( PEAS )

Aspect	Description
Performance Measure	- The number of squares cleared in a given time.
	- The time taken to complete the level and space.
Environment	- A grid of colored squares linked in a top, right, left, and bottom manner.
	- The state of the environment changes as the agent makes moves to destroy interconnected squares.
Actuators	- Select and destroy squares in the grid.
Sensors	- The colors of the squares and their connectivity.
	- Look at the last row to see if it is complete or not.

contributors

Tools

• Python 3.x
• Pygame

Install dependencies using:

pip install pygame