search_algorithms

KO | EN

gitlite — search

#javascript #python #css #html #java #deep-learning #mongodb #nodejs #php #logging #hacktoberfest #api

search_algorithms

★ 3 Open GitHub ↗

different types of search algorithms in 8-puzzle game (BFS, DFS, A*, etc)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# 8-Puzzle Search Algorithms

This project explores and implements various search algorithms to solve the classic 8-puzzle game. You can experiment with different strategies like Breadth-First Search (BFS), Depth-First Search (DFS), A*, and Greedy Best-First Search.

## 🌟 Features

* **Multiple Search Algorithms**: Implements a range of search algorithms:
    * Breadth-First Search (BFS)
    * Depth-First Search (DFS)
    * Uniform Cost Search (UCS) - *Note: Currently uses BFS logic*
    * Greedy Best-First Search
    * A\* Search
* **Tree Search vs. Graph Search**: Option to perform either tree search or graph search for most algorithms.
* **Customizable Maps**: Easily change the initial state of the 8-puzzle by modifying the `map.txt` file.
* **Results Logging**: Outputs the solution path, number of nodes generated, execution time, and depth of the answer to a text file.
* **Performance Tracking**: Displays the number of nodes generated in real-time during the search process (updates every 1000 nodes).

## 📋 Requirements

To run this project, you'll need Python and the libraries listed in `requirements.txt`. The key libraries include:
* `treelib` (for tree data structure manipulation)
* Other libraries such as `APScheduler`, `numpy`, `matplotlib`, etc., can be found in the `requirements.txt` file.

## ⚙️ Installation

1.  **Clone the repository (or download the files).**
2.  **Navigate to the project folder** in your terminal or command prompt.
    ```bash
    cd path/to/your/search_algorithms
    ```
3.  **Install the required packages**:
    ```bash
    pip install -r requirements.txt
    ```

## 🚀 Running the Solver

1.  **Ensure you are in the project's root folder.**
2.  **Run the `main.py` script**:
    ```bash
    python main.py
    ```
   
3.  **Follow the prompts**:
    * **Choose the algorithm**: Enter the desired search strategy (e.g., `dfs`, `bfs`, `greedy`, `A*`).
    * **Select search type**: Enter `True` for tree search or `False` for graph search.

## 🗺️ Configuring the Map

To change the initial state of the 8-puzzle:

1.  Open the `map.txt` file located in the root folder of the project.
2.  Modify the puzzle configuration. Use numbers `1` through `8` and `_` (or `0`) for the empty tile. Ensure it's a 3x3 grid. For example:
    ```
    _ 2 5
    3 4 8
    1 7 6
    ```

## 📊 Output

* The script will print "searching..." while it looks for a solution.
* Progress (number of nodes generated) will be updated in the console.
* Once the search is complete, the results, including the solution path, time taken, nodes created, and answer depth, will be saved in a `.txt` file inside the `/res/` directory. The filename will correspond to the algorithm used (e.g., `res/dfs.txt`, `res/As.txt`).
* A message indicating the path to the results file will be printed (e.g., "answer is in res/dfs.txt !").

## 🧠 Implemented Algorithms

The following search strategies are available:

* **Depth-First Search (DFS)**: Explores as far as possible along each branch before backtracking.
* **Breadth-First Search (BFS)**: Explores all neighbor nodes at the present depth prior to moving on to nodes at the next depth level. This is also used for Uniform Cost Search (UCS) in the current implementation.
* **Greedy Best-First Search**: Expands the node that is estimated to be closest to the goal, based on a heuristic function `h(n)`.
* **A\* Search**: Expands nodes based on a combination of the cost from the start node `g(n)` and an estimated cost to the goal `h(n)`, i.e., `f(n) = g(n) + h(n)`.

### Heuristic Function (`h(n)`)

The heuristic `h(n)` used for Greedy Search and A\* is the Manhattan distance. It calculates the sum of the absolute differences between the current and goal positions of each tile.

## 🛠️ Code Overview (`main.py`)

* **`g(node, tree)`**: Calculates the depth of a node (cost from the start).
* **`h(state)`**: The heuristic function (Manhattan distance).
* **`f(node, tree, state)`**: Evaluation function for A\* (`g + h`).
* **`create_goal()`**: Defines the goal state of the 8-puzzle.
* **`is_goal(state)`**: Checks if the current state is the goal state.
* **`generate_moves(state)`**: Generates all possible next states from the current state.
* **`get_board(path)`**: Reads the initial puzzle configuration from `map.txt`.
* **`write_result(...)`**: Writes the solution and statistics to the output file.
* **Algorithm functions (`dfs`, `bfs`, `greedy`, `As`)**: Implement the core logic for each search strategy.

## 🚧 Known Issues / Future Work

* **DLS and IDS**: The Depth-Limited Search (DLS) and Iterative Deepening Search (IDS) are marked as "-- still not working --" in `main.py`. These could be completed.
* **UCS Implementation**: Uniform Cost Search (UCS) currently uses the BFS logic. For a true UCS, especially if step costs vary (though not typical in a standard 8-puzzle), it should prioritize paths with the lowest `g(n)`.
* **Error Handling**: More robust error handling could be added (e.g., for invalid map configurations).
* **Solvability Check**: Implement a check to determine if the initial puzzle state is solvable before starting the search, as not all 8-puzzle configurations have solutions. The `As` function has a `solvable` flag, but a preemptive check would be efficient.

search_algorithms

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README