PY-Tile-Arrangement-Solver

Overview

PY-Tile-Arrangement-Solver is a Python project designed to solve a tile rearrangement puzzle on a grid of dimensions m x n. The objective is to find the shortest sequence of moves to arrange tiles in a specified order, with the final arrangement showing sequential numbers across each row. This project implements multiple graph traversal algorithms, including BFS, an improved BFS, and A*, to optimize the solution. A graphical interface created with Pygame allows users to interact with the puzzle and experiment with different configurations.

Features

• Algorithms: The project explores multiple algorithms for finding the optimal solution:
  • Breadth-First Search (BFS) for a basic breadth-first search through grid states.
  • Improved BFS which dynamically generates nodes, reducing memory usage.
  • A* with Manhattan distance heuristic for faster and more informed searches.
• User Interface: An interactive graphical interface built with Pygame enables users to manually solve the puzzle or observe the automated solution.
• Difficulty Levels: Puzzle difficulty can be scaled by grid size, which influences the number of tiles and complexity.

Project Structure

PY-Tile-Arrangement-Solver/  
├── docs/                        # Project documentation
│   ├── API.md                   # API documentation of classes and methods
│   └── report.md                # Detailed report on algorithms and complexity analysis
│  
├── input/                       # Test input files for different grid configurations
│   ├── grid0.in
│   ├── grid1.in
│   └── ...                      # Additional test files
│
├── src/                         # Contains the main source code
│   ├── game.py
│   ├── graph.py                 # Graph class for BFS and A*
│   ├── grid.py                  # Grid class for tile manipulations
│   └── solver.py                # Solver class implementing BFS, Improved BFS, and A*
│
├── tests/                       # Unit tests for each module
│   ├── test_A_star.py           # Tests for A*
│   ├── test_bfs.py              # Tests for BFS
│   ├── test_bfs_improved.py     # Tests for Improved BFS
│   ├── test_grid_from_file.py   # Tests for Grid functions
│   ├── test_is_sorted.py        # Tests for sorted state detection
│   └── test_swap.py             # Tests for swap operations in the grid
│
├── main.py                      # Script to run algorithms for solving and testing solutions
├── run_game.py                  # Main script to launch the interactive game
├── README.md                    # Project overview and instructions (this file)
└── requirements.txt             # Python packages necessary for the proper functioning of the project.

Algorithms

Breadth-First Search (BFS)

• Description: A standard BFS algorithm that explores all neighbors of a node before moving on. Each grid state is considered a node, and valid moves form edges between nodes.
• Complexity: O(m * n * (m * n)!), as BFS explores all possible configurations of the grid.

Improved BFS

• Description: Optimized to generate only necessary nodes, significantly reducing memory usage.
• Complexity: Equivalent to BFS in worst-case scenarios, but faster in practice due to reduced nodes.

A* Search

• Description: Uses Manhattan distance as a heuristic for faster and informed traversal.
• Complexity: O(m * n * log((m * n)!)), dominated by sorting and list operations.

Installation

1. Clone the repository:

   git clone https://github.com/moranenzo/PY-Tile-Arrangement-Solver.git

2. Navigate to the project directory:

   cd PY-Tile-Arrangement-Solver

3. Install the required dependencies:

   pip install -r requirements.txt

Usage

Run the Interactive Game

To start the interactive puzzle game with a graphical interface:

python run_game.py

This will launch the game interface where you can choose a difficulty level and interact with the puzzle.

Run the Solver Algorithms

To execute the script focused on algorithm testing and pathfinding solutions:

python main.py

This script loads a grid from an input file, applies different solving algorithms (BFS, Improved BFS, A*), and displays the paths found for each algorithm in the console.

Testing

Run unit tests for each module with:

python -m unittest discover -s tests

Future Improvements

• Experiment with additional heuristics for A*.
• Add scoring to track user performance.
• Integrate custom grid options for varied gameplay.