fifteen-puzzle-solvers

Name	fifteen-puzzle-solvers JSON
Version	2.0.0 JSON
	download
home_page	https://github.com/MilanPecov/15-Puzzle-Solvers
Summary	Different solvers for the 15 puzzle sliding game
upload_time	2024-07-14 02:26:31
maintainer	None
docs_url	None
author	Milan Pecov
requires_python	>=3.6
license	None
keywords	15-puzzle sliding-game algorithms a* breadth-first search heuristics python path-finding
VCS
bugtrack_url
requirements	No requirements were recorded.
Travis-CI	No Travis.
coveralls test coverage	No coveralls.

            [![Tests](https://github.com/MilanPecov/15-Puzzle-Solvers/actions/workflows/tests.yaml/badge.svg)](https://github.com/MilanPecov/15-Puzzle-Solvers/actions/workflows/tests.yaml)

# Introduction

The 15-puzzle is a classic problem that has captivated mathematics enthusiasts for centuries. The objective
is to arrange the tiles in order by sliding them into the empty space. The challenge lies in its vast 
state space, with approximately 10<sup>13</sup> possible configurations. Numerous algorithms have been 
developed to tackle the 15-puzzle, highlighting its complexity and the significant challenge it presents.

In this project, we employ advanced algorithms to effectively manage this large state space. Specifically,
the A* algorithm utilizes multiple heuristics to reduce the number of states generated and expand fewer 
nodes, thereby improving efficiency. The heuristics, such as Manhattan Distance (MD), Linear Conflict (LC),
and Walking Distance (WD), are combined in a hybrid approach to provide optimal or near-optimal solutions
while maintaining manageable space complexity.

![Alt text](puzzle_img1.png) ![Alt text](puzzle_img2.png)

# Installation
```
pip install fifteen-puzzle-solvers
```

## Running the GUI
```
# requires `tkinter` to be installed
from fifteen_puzzle_solvers import run_ui
run_ui()
```

# Running the puzzle solvers

This code implements two different puzzle solvers:
* Breadth First Algorithm
* __A* Algorithm__
  * **Heuristic 1:** Counting the number of misplaced tiles
  * **Heuristic 2:** Finding the sum of the Manhattan distances between each block
      and its position in the goal configuration
  * **Heuristic 3:** Combining Manhattan distance, Linear Conflict, and walking distance for a comprehensive estimate (default heuristic)

```
from fifteen_puzzle_solvers.domain import Puzzle
from fifteen_puzzle_solvers.services.algorithms import AStar, BreadthFirst
from fifteen_puzzle_solvers.services.solver import PuzzleSolver

puzzle = Puzzle([[1, 2, 3, 4], [5, 6, 7, 8], [0, 10, 11, 12], [9, 13, 14, 15]])

for strategy in [BreadthFirst, AStar]:
    puzzle_solver = PuzzleSolver(strategy(puzzle))
    puzzle_solver.run()
    puzzle_solver.print_performance()
    puzzle_solver.print_solution()  
```

Output
```
Breadth First - Expanded Nodes: 56
Solution:
—————————————
│ 1│ 2│ 3│ 4│
│ 5│ 6│ 7│ 8│
│ 0│10│11│12│
│ 9│13│14│15│
—————————————
—————————————
│ 1│ 2│ 3│ 4│
│ 5│ 6│ 7│ 8│
│ 9│10│11│12│
│ 0│13│14│15│
—————————————
—————————————
│ 1│ 2│ 3│ 4│
│ 5│ 6│ 7│ 8│
│ 9│10│11│12│
│13│ 0│14│15│
—————————————
—————————————
│ 1│ 2│ 3│ 4│
│ 5│ 6│ 7│ 8│
│ 9│10│11│12│
│13│14│ 0│15│
—————————————
—————————————
│ 1│ 2│ 3│ 4│
│ 5│ 6│ 7│ 8│
│ 9│10│11│12│
│13│14│15│ 0│
—————————————

A* - Expanded Nodes: 4
Solution:
—————————————
│ 1│ 2│ 3│ 4│
│ 5│ 6│ 7│ 8│
│ 0│10│11│12│
│ 9│13│14│15│
—————————————
—————————————
│ 1│ 2│ 3│ 4│
│ 5│ 6│ 7│ 8│
│ 9│10│11│12│
│ 0│13│14│15│
—————————————
—————————————
│ 1│ 2│ 3│ 4│
│ 5│ 6│ 7│ 8│
│ 9│10│11│12│
│13│ 0│14│15│
—————————————
—————————————
│ 1│ 2│ 3│ 4│
│ 5│ 6│ 7│ 8│
│ 9│10│11│12│
│13│14│ 0│15│
—————————————
—————————————
│ 1│ 2│ 3│ 4│
│ 5│ 6│ 7│ 8│
│ 9│10│11│12│
│13│14│15│ 0│
—————————————
```

# Testing different A* heuristic functions
```
from fifteen_puzzle_solvers.domain.puzzle import Puzzle
from fifteen_puzzle_solvers.services.algorithms import AStar
from fifteen_puzzle_solvers.services.solver import PuzzleSolver
from fifteen_puzzle_solvers.services.puzzle.shuffle import PuzzleShuffleService

# Generate a shuffled 3x3 puzzle using the PuzzleShuffleService
shuffled_puzzle = PuzzleShuffleService.shuffle_puzzle(3)

# Create a solver using the A* algorithm with the 'misplaced' heuristic
puzzle_solver = PuzzleSolver(AStar(shuffled_puzzle, heuristic='misplaced'))
puzzle_solver.run()

# Print the performance and the solution
puzzle_solver.print_performance()

>> Output: A* - Expanded Nodes: 979

puzzle_solver = PuzzleSolver(AStar(puzzle, heuristic='total'))  # default
puzzle_solver.run()
puzzle_solver.print_performance()

>> Output: A* - Expanded Nodes: 68
```

# Under the hood

Both the Breadth First and A* algorithms take an initial puzzle state as input and return a list of Puzzle objects that represent the sequence of moves needed to solve the puzzle.

## BreadthFirst

Uses a queue list to keep track of the paths that need to be explored. 
The algorithm begins by adding the initial puzzle state to the queue list. Then, it repeatedly takes the 
first path from the queue list, gets all the possible moves from the last position in the path, and adds the 
new paths to the end of the queue list. This process continues until the end position of the puzzle is reached 
or there are no more paths to explore.

## A*
The A* algorithm is an extension of the Breadth-First Search that uses heuristics to prioritize which paths to explore. It maintains a priority queue where each path is associated with a cost, which is the sum of the path length and a heuristic estimate of the remaining cost to reach the goal.

### Heuristics

Heuristics are used to estimate the cost of reaching the goal from a given state. The A* algorithm in this implementation supports the following heuristics:

* Misplaced Tiles:
This heuristic counts the number of tiles that are not in their goal position. It is simple but not always very accurate.

* Manhattan Distance:
This heuristic calculates the sum of the Manhattan distances (i.e., the sum of the absolute differences of the row and column indices) of the tiles from their goal positions. It is more accurate than the misplaced tiles heuristic.

* Total Heuristic (Default):
This heuristic combines multiple heuristic functions—Manhattan distance, linear conflict, and walking distance—to provide a comprehensive estimate. This combination balances accuracy and performance, making it the default choice for solving the puzzle efficiently.


## How to Play

* Shuffle: Click the "Shuffle" button to shuffle the puzzle.
* Solve: Click the "Solve" button to automatically solve the puzzle using the selected algorithm.
* Manual Play: Click on the tiles adjacent to the empty space to move them.
* Previous/Next Steps: After solving the puzzle, use the "Previous Step" and "Next Step" buttons to navigate through the solution steps.

## Directory Overview

* domain/: Contains the core logic and data structures for the puzzle game.
* services/: Includes the algorithms and services for shuffling and solving the puzzle.
* tests/: Contains test cases for the project.
* ui/: Holds the graphical user interface code.

            

Raw data

            {
    "_id": null,
    "home_page": "https://github.com/MilanPecov/15-Puzzle-Solvers",
    "name": "fifteen-puzzle-solvers",
    "maintainer": null,
    "docs_url": null,
    "requires_python": ">=3.6",
    "maintainer_email": null,
    "keywords": "15-puzzle sliding-game algorithms A* breadth-first search heuristics python path-finding",
    "author": "Milan Pecov",
    "author_email": "mpecov@yahoo.ca",
    "download_url": "https://files.pythonhosted.org/packages/12/83/59a1bbc4e97b8bdead8d3f04bd9d23830084cde7656712a167756664b981/fifteen_puzzle_solvers-2.0.0.tar.gz",
    "platform": null,
    "description": "[![Tests](https://github.com/MilanPecov/15-Puzzle-Solvers/actions/workflows/tests.yaml/badge.svg)](https://github.com/MilanPecov/15-Puzzle-Solvers/actions/workflows/tests.yaml)\n\n# Introduction\n\nThe 15-puzzle is a classic problem that has captivated mathematics enthusiasts for centuries. The objective\nis to arrange the tiles in order by sliding them into the empty space. The challenge lies in its vast \nstate space, with approximately 10<sup>13</sup> possible configurations. Numerous algorithms have been \ndeveloped to tackle the 15-puzzle, highlighting its complexity and the significant challenge it presents.\n\nIn this project, we employ advanced algorithms to effectively manage this large state space. Specifically,\nthe A* algorithm utilizes multiple heuristics to reduce the number of states generated and expand fewer \nnodes, thereby improving efficiency. The heuristics, such as Manhattan Distance (MD), Linear Conflict (LC),\nand Walking Distance (WD), are combined in a hybrid approach to provide optimal or near-optimal solutions\nwhile maintaining manageable space complexity.\n\n![Alt text](puzzle_img1.png) ![Alt text](puzzle_img2.png)\n\n# Installation\n```\npip install fifteen-puzzle-solvers\n```\n\n## Running the GUI\n```\n# requires `tkinter` to be installed\nfrom fifteen_puzzle_solvers import run_ui\nrun_ui()\n```\n\n# Running the puzzle solvers\n\nThis code implements two different puzzle solvers:\n* Breadth First Algorithm\n* __A* Algorithm__\n  * **Heuristic 1:** Counting the number of misplaced tiles\n  * **Heuristic 2:** Finding the sum of the Manhattan distances between each block\n      and its position in the goal configuration\n  * **Heuristic 3:** Combining Manhattan distance, Linear Conflict, and walking distance for a comprehensive estimate (default heuristic)\n\n```\nfrom fifteen_puzzle_solvers.domain import Puzzle\nfrom fifteen_puzzle_solvers.services.algorithms import AStar, BreadthFirst\nfrom fifteen_puzzle_solvers.services.solver import PuzzleSolver\n\npuzzle = Puzzle([[1, 2, 3, 4], [5, 6, 7, 8], [0, 10, 11, 12], [9, 13, 14, 15]])\n\nfor strategy in [BreadthFirst, AStar]:\n    puzzle_solver = PuzzleSolver(strategy(puzzle))\n    puzzle_solver.run()\n    puzzle_solver.print_performance()\n    puzzle_solver.print_solution()  \n```\n\nOutput\n```\nBreadth First - Expanded Nodes: 56\nSolution:\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2502 1\u2502 2\u2502 3\u2502 4\u2502\n\u2502 5\u2502 6\u2502 7\u2502 8\u2502\n\u2502 0\u250210\u250211\u250212\u2502\n\u2502 9\u250213\u250214\u250215\u2502\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2502 1\u2502 2\u2502 3\u2502 4\u2502\n\u2502 5\u2502 6\u2502 7\u2502 8\u2502\n\u2502 9\u250210\u250211\u250212\u2502\n\u2502 0\u250213\u250214\u250215\u2502\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2502 1\u2502 2\u2502 3\u2502 4\u2502\n\u2502 5\u2502 6\u2502 7\u2502 8\u2502\n\u2502 9\u250210\u250211\u250212\u2502\n\u250213\u2502 0\u250214\u250215\u2502\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2502 1\u2502 2\u2502 3\u2502 4\u2502\n\u2502 5\u2502 6\u2502 7\u2502 8\u2502\n\u2502 9\u250210\u250211\u250212\u2502\n\u250213\u250214\u2502 0\u250215\u2502\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2502 1\u2502 2\u2502 3\u2502 4\u2502\n\u2502 5\u2502 6\u2502 7\u2502 8\u2502\n\u2502 9\u250210\u250211\u250212\u2502\n\u250213\u250214\u250215\u2502 0\u2502\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\nA* - Expanded Nodes: 4\nSolution:\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2502 1\u2502 2\u2502 3\u2502 4\u2502\n\u2502 5\u2502 6\u2502 7\u2502 8\u2502\n\u2502 0\u250210\u250211\u250212\u2502\n\u2502 9\u250213\u250214\u250215\u2502\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2502 1\u2502 2\u2502 3\u2502 4\u2502\n\u2502 5\u2502 6\u2502 7\u2502 8\u2502\n\u2502 9\u250210\u250211\u250212\u2502\n\u2502 0\u250213\u250214\u250215\u2502\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2502 1\u2502 2\u2502 3\u2502 4\u2502\n\u2502 5\u2502 6\u2502 7\u2502 8\u2502\n\u2502 9\u250210\u250211\u250212\u2502\n\u250213\u2502 0\u250214\u250215\u2502\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2502 1\u2502 2\u2502 3\u2502 4\u2502\n\u2502 5\u2502 6\u2502 7\u2502 8\u2502\n\u2502 9\u250210\u250211\u250212\u2502\n\u250213\u250214\u2502 0\u250215\u2502\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n\u2502 1\u2502 2\u2502 3\u2502 4\u2502\n\u2502 5\u2502 6\u2502 7\u2502 8\u2502\n\u2502 9\u250210\u250211\u250212\u2502\n\u250213\u250214\u250215\u2502 0\u2502\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n```\n\n# Testing different A* heuristic functions\n```\nfrom fifteen_puzzle_solvers.domain.puzzle import Puzzle\nfrom fifteen_puzzle_solvers.services.algorithms import AStar\nfrom fifteen_puzzle_solvers.services.solver import PuzzleSolver\nfrom fifteen_puzzle_solvers.services.puzzle.shuffle import PuzzleShuffleService\n\n# Generate a shuffled 3x3 puzzle using the PuzzleShuffleService\nshuffled_puzzle = PuzzleShuffleService.shuffle_puzzle(3)\n\n# Create a solver using the A* algorithm with the 'misplaced' heuristic\npuzzle_solver = PuzzleSolver(AStar(shuffled_puzzle, heuristic='misplaced'))\npuzzle_solver.run()\n\n# Print the performance and the solution\npuzzle_solver.print_performance()\n\n>> Output: A* - Expanded Nodes: 979\n\npuzzle_solver = PuzzleSolver(AStar(puzzle, heuristic='total'))  # default\npuzzle_solver.run()\npuzzle_solver.print_performance()\n\n>> Output: A* - Expanded Nodes: 68\n```\n\n# Under the hood\n\nBoth the Breadth First and A* algorithms take an initial puzzle state as input and return a list of Puzzle objects that represent the sequence of moves needed to solve the puzzle.\n\n## BreadthFirst\n\nUses a queue list to keep track of the paths that need to be explored. \nThe algorithm begins by adding the initial puzzle state to the queue list. Then, it repeatedly takes the \nfirst path from the queue list, gets all the possible moves from the last position in the path, and adds the \nnew paths to the end of the queue list. This process continues until the end position of the puzzle is reached \nor there are no more paths to explore.\n\n## A*\nThe A* algorithm is an extension of the Breadth-First Search that uses heuristics to prioritize which paths to explore. It maintains a priority queue where each path is associated with a cost, which is the sum of the path length and a heuristic estimate of the remaining cost to reach the goal.\n\n### Heuristics\n\nHeuristics are used to estimate the cost of reaching the goal from a given state. The A* algorithm in this implementation supports the following heuristics:\n\n* Misplaced Tiles:\nThis heuristic counts the number of tiles that are not in their goal position. It is simple but not always very accurate.\n\n* Manhattan Distance:\nThis heuristic calculates the sum of the Manhattan distances (i.e., the sum of the absolute differences of the row and column indices) of the tiles from their goal positions. It is more accurate than the misplaced tiles heuristic.\n\n* Total Heuristic (Default):\nThis heuristic combines multiple heuristic functions\u2014Manhattan distance, linear conflict, and walking distance\u2014to provide a comprehensive estimate. This combination balances accuracy and performance, making it the default choice for solving the puzzle efficiently.\n\n\n## How to Play\n\n* Shuffle: Click the \"Shuffle\" button to shuffle the puzzle.\n* Solve: Click the \"Solve\" button to automatically solve the puzzle using the selected algorithm.\n* Manual Play: Click on the tiles adjacent to the empty space to move them.\n* Previous/Next Steps: After solving the puzzle, use the \"Previous Step\" and \"Next Step\" buttons to navigate through the solution steps.\n\n## Directory Overview\n\n* domain/: Contains the core logic and data structures for the puzzle game.\n* services/: Includes the algorithms and services for shuffling and solving the puzzle.\n* tests/: Contains test cases for the project.\n* ui/: Holds the graphical user interface code.\n",
    "bugtrack_url": null,
    "license": null,
    "summary": "Different solvers for the 15 puzzle sliding game",
    "version": "2.0.0",
    "project_urls": {
        "Homepage": "https://github.com/MilanPecov/15-Puzzle-Solvers"
    },
    "split_keywords": [
        "15-puzzle",
        "sliding-game",
        "algorithms",
        "a*",
        "breadth-first",
        "search",
        "heuristics",
        "python",
        "path-finding"
    ],
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "blake2b_256": "cf16fc9b31620a42f1542ec77d834c7bb27cf1cbaa2a8d016ecda106280b0000",
                "md5": "7947dd0bf0e7fee16762674c7270c9ba",
                "sha256": "baf01d7d8d0e46ec5f5a17c7dcbc9c2dbde1757c81f8b12ab46b9eef0692cd0f"
            },
            "downloads": -1,
            "filename": "fifteen_puzzle_solvers-2.0.0-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "7947dd0bf0e7fee16762674c7270c9ba",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": ">=3.6",
            "size": 14807,
            "upload_time": "2024-07-14T02:26:29",
            "upload_time_iso_8601": "2024-07-14T02:26:29.675140Z",
            "url": "https://files.pythonhosted.org/packages/cf/16/fc9b31620a42f1542ec77d834c7bb27cf1cbaa2a8d016ecda106280b0000/fifteen_puzzle_solvers-2.0.0-py3-none-any.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "blake2b_256": "128359a1bbc4e97b8bdead8d3f04bd9d23830084cde7656712a167756664b981",
                "md5": "4cf481f7875f7c690d34475618308ba1",
                "sha256": "d9cd0b0a478388441a8cbbf38bb0010bf3cc4363e79606fad8c82d549879b3fa"
            },
            "downloads": -1,
            "filename": "fifteen_puzzle_solvers-2.0.0.tar.gz",
            "has_sig": false,
            "md5_digest": "4cf481f7875f7c690d34475618308ba1",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": ">=3.6",
            "size": 13205,
            "upload_time": "2024-07-14T02:26:31",
            "upload_time_iso_8601": "2024-07-14T02:26:31.210517Z",
            "url": "https://files.pythonhosted.org/packages/12/83/59a1bbc4e97b8bdead8d3f04bd9d23830084cde7656712a167756664b981/fifteen_puzzle_solvers-2.0.0.tar.gz",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "upload_time": "2024-07-14 02:26:31",
    "github": true,
    "gitlab": false,
    "bitbucket": false,
    "codeberg": false,
    "github_user": "MilanPecov",
    "github_project": "15-Puzzle-Solvers",
    "travis_ci": false,
    "coveralls": false,
    "github_actions": true,
    "lcname": "fifteen-puzzle-solvers"
}