Sliding Puzzle solver
Project description
Sliding Puzzle
Installation | Documentation (Latest | Stable)
A package for solving sliding tile puzzles.
Installation
pip install slidingpuzzle
Examples
>>> from slidingpuzzle import *
>>> board = new_board(3, 3)
>>> print_board(board)
1 2 3
4 5 6
7 8
>>> print_board(shuffle_board(board))
8 3 1
4 2
5 6 7
Regular boards are stored as numpy arrays. The number 0
is reserved for the blank.
>>> board
array([[8, 3, 1],
[4, 5, 6],
[5, 6, 7]])
You can easily build your own boards using numpy or any of the provided convenience methods:
>>> board = board_from([4, 5, 6], [7, 8, 0], [1, 2, 3])
>>> print_board(board)
4 5 6
7 8
1 2 3
>>> board = board_from_iter(3, 3, [4, 5, 6, 7, 8, 0, 1, 2, 3])
>>> print_board(board)
4 5 6
7 8
1 2 3
>>> manhattan_distance(board)
11
>>> is_solvable(board)
False
Not all board configurations are solvable. The search()
routine will validate the board before beginning, and may throw a ValueError
if the board is illegal.
The default search is A*
with linear_conflict_distance()
as the heuristic:
>>> board = shuffle_board(new_board(3, 3))
>>> search(board)
solution=[5, 4, 1, 2, 6, 5, 3, 7, 4, 1, 2, 3, 5, 8, 7, 4, 1, 2, 3, 6]
solution_len=20, generated=360, expanded=164, unvisited=197, visited=136
generated
is the total number of nodes generated during the searchexpanded
is the total number of nodes that were evaluated (removed from search frontier)unvisited
is the number of nodes that we never reached because search terminated early (search frontier, "open")visited
is the number of unique states visited (expanded
minus duplicate state expansions, "closed")
>>> search(b, "bfs")
solution=[3, 7, 5, 4, 1, 2, 6, 8, 7, 5, 4, 1, 2, 3, 5, 4, 1, 2, 3, 6]
solution_len=20, generated=125450, expanded=88173, unvisited=37278, visited=45763
>>> search(b, "greedy")
solution=[3, 7, 5, 4, 1, 3, 4, 1, 3, 2, 6, 8, 7, 4, 2, 6, 8, 7, 4, 5, 1, 2, 5, 4, 7, 8]
solution_len=26, generated=556, expanded=374, unvisited=183, visited=202
Notice how many states are generated for BFS to find a solution. Greedy search finds a solution quickly, but the solution is of lower quality.
There are numerous convenience functions available for working with boards. Below are a few examples.
>>> find_blank(board)
(1, 1)
>>> find_tile(board, 3)
(1, 0)
>>> moves = get_next_moves(board)
>>> moves
[(1, 0), (1, 2), (0, 1), (2, 1)]
>>> swap_tiles(board, moves[0])
array([[7, 5, 4],
[0, 3, 1],
[8, 6, 2]])
>>> result = search(board)
>>> result.solution
[(0, 1), (0, 2), (1, 2), (2, 2), (2, 1), (1, 1), (1, 0), (0, 0), (0, 1), (0, 2), (1, 2), (1, 1), (2, 1), (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
If you are working with a physical puzzle and actual tile numbers would be easier to read, you can obtain them using the convenience function solution_as_tiles()
:
>>> solution_as_tiles(result.board, result.solution)
[5, 4, 1, 2, 6, 5, 3, 7, 4, 1, 2, 3, 5, 8, 7, 4, 1, 2, 3, 6]
We can compare()
two heuristics like this:
>>> compare(3, 3, ha=manhattan_distance, hb=euclidean_distance)
(1594.87, 3377.5)
The numbers are the average number of states generated over num_iters
runs for each heuristic.
Or we can compare two algorithms:
>>> compare(3, 3, alga="a*", algb="greedy")
(2907.5, 618.0)
The solutions are actually stored as a list of (y, x)-coords of moves, indicating which tile is to be moved next:
Algorithms
>>> print(ALGORITHMS)
('a*', 'beam', 'bfs', 'dfs', 'greedy', 'ida*', 'iddfs')
The available algorithms are:
"a*"
(default) - Docs, Wiki"beam"
- Docs, Wiki"bfs"
- Docs, Wiki"dfs"
- Docs, Wiki"greedy"
- Docs, Wiki"ida*"
- Docs, Wiki"iddfs"
- Docs, Wiki
All algorithms support behavior customization via kwargs
. See the docs for individual algorithms linked above.
Of the provided algorithms, only beam search is incomplete by default. This means it may miss the goal, even thought the board is solvable.
Heuristics
The available heuristics are:
euclidean_distance
- The straight line distance in Euclidean space between two tiles. This is essentially the hypotenuse of a right triangle. (The square root is not used as it does not affect the sorting order.)hamming_distance
- Count of how many tiles are in the correct positionlinear_conflict_distance
- This is an augmented Manhattan distance. Roughly speaking, adds an additional 2 to each pair of inverted tiles that are already on their goal row/column.manhattan_distance
- Count of how many moves it would take each tile to arrive in the correct position, if other tiles could be ignoredrandom_distance
- This is a random number (but a consistent random number for a given board state). It is useful as a baseline.relaxed_adjacency_distance
- This is a slight improvement over Hamming distance that includes a penalty for swapping out-of-place tiles.- Neural net heuristics from
slidingpuzzle.nn
submodule (see section below) - Any heuristic you want. Just pass any function that accepts a board and returns a number. The lower the number, the closer the board is to the goal (lower = better).
There are two simple provided utility functions for evaluating algorithm/heuristic performance: evaluate()
and compare()
.
For example, here we use compare()
with a trivial custom heuristic to see how it fares against Manhattan Distance:
>>> def max_distance(board):
... return max(manhattan_distance(board), relaxed_adjacency_distance(board))
...
>>> compare(3, 3, ha=manhattan_distance, hb=max_distance)
(3020.5, 2857.53)
We can reasonably conclude that on average the max of these two heuristics is slightly better than either one alone (Hansson et al., 1985).
We can use evaluate()
to study an algorithm's behavior when tweaking a parameter.
import matplotlib.pyplot as plt
import numpy as np
x = np.linspace(1, 32, num=256)
y = [evaluate(3, 3, weight=w) for w in x]
plt.plot(x, y)
plt.title("Average Nodes Generated vs. A* Weight")
plt.xlabel("Weight")
plt.ylabel("Generated")
plt.show()
)
Neural Nets
Well-trained neural networks are generally superior to the other heuristics. Pre-trained nets will be available for download soon. For now, you can follow the steps below to train and use your own net from scratch using the models defined in slidingpuzzle.nn.models
.
pip install -r requirements-nn.txt
Note: This will install the CUDA 11.6 version of PyTorch. If you want another version, you will need to follow the official instructions.
You can then train a new network easily:
>>> import slidingpuzzle.nn as nn
>>> nn.set_seed(0) # if you want reproducible weights
>>> model = nn.Model_v1(3, 3)
>>> nn.train(model)
Note: Unless you are providing your own dataset, for model sizes larger than
3 x 3
you probably need to passkwargs
totrain()
so that the search algorithm used for generating training example can find solutions in a reasonable timeframe. For example:
>>> import slidingpuzzle.nn as nn
>>> model = nn.Model_v1(4, 4, weight=2) # use Weighted A* with weight of 2; all kwargs forwarded to search()
>>> nn.train(model)
The default behavior runs until it appears test accuracy has been declining for "a while". See the docs for for details.
If you left the default settings for checkpoint_freq
, you will now have various model checkpoints available from training.
The model with estimated highest accuracy on the test data is tagged "acc"
in the checkpoints directory.
You can evaluate a checkpoint similar to evaluate
:
>>> nn.eval_checkpoint(model, tag="acc")
417.71875
Or the latest model epoch:
>>> nn.eval_checkpoint(model, tag="latest", num_iters=128)
The call to eval_checkpoint()
will load the model weights from the appropriate checkpoint file and run evaluate()
.
You can also manually load checkpoints:
>>> checkpoint = nn.load_checkpoint(model, tag="epoch_1499")
>>> checkpoint["epoch"]
1499
(See the checkpoints
directory for all trained models available to load by tag
.)
You can then register the model:
>>> nn.set_heuristic(model)
Your model is now available as nn.v1_distance
if you are using the default provided model Model_v1
. (These are associated behind the scenes via the model.version
property.)
You can freeze your preferred model to disk to be used as the default for nn.v1_distance
:
>>> nn.save_model(model)
Note: This may overwrite a previously saved model.
Your model will now be available whenever you import slidingpuzzle.nn
.
>>> compare(3, 3, ha=nn.v1_distance, hb=manhattan_distance, num_iters=128, weight=7)
(73.375, 514.1328125)
Training uses GPU if available and falls back to CPU otherwise.
Custom Models
First define your torch.nn.Module
somewhere.
Your model class must:
- have a unique
self.version
string that is safe to use in filenames (e.g."my_model_v1"
) - have
self.h
andself.w
indicating the input board dimensions it expects, - have a
forward()
that accepts board as a tensor constructed by:torch.tensor(board, dtype=torch.float32)
- (The tensor above does not include the batch dimension.)
- For example, expect:
model(board)
Train and save your model as above.
You can now copy-paste the model-based heuristic function below:
def my_model_distance(board) -> float:
h, w = len(board), len(board[0])
heuristic = nn.get_heuristic(h, w, "my_model_version")
return heuristic(board)
Just change "my_model_version"
to the string you used in your model class.
And you use it as expected:
>>> search(board, "a*", heuristic=my_model_distance)
You can add your my_model_distance()
function to the bottom of nn/heuristics.py
to make it permanently available.
During training, tensorboard will show your training/test loss and accuracy. After training is complete, you can also evaluate each checkpoint for comparison as shown above.
Contributing
First of all, thanks for contributing! Setup your dev environment:
pip install -r requirements-dev.txt
pre-commit install
After you've added your new code, verify you haven't broken anything by running pytest
:
pytest
If you changed anything in the slidingpuzzle.nn
package, also run:
pip install -r requirements-nn.txt
pytest tests/test_nn.py
Don't forget to add new tests for anything you've added.
Finally, check that the docs look correct:
cd docs
make html
Note: Use
./make html
on Windows.
You can also run mypy
and look for any new violations:
mypy src
Black
and flake8
are used for formatting and linting, but they are automatically run by the pre-commit hooks you installed earlier in the Git repo.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for slidingpuzzle-0.0.24rc0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3dfeb28e17f095f1728b2399ff343bd964ae85cdc558a0f3d07bcb61c38a2047 |
|
MD5 | a7aabe2de47c29de7695a5346f6d9c4d |
|
BLAKE2b-256 | dfacfd5d52e6bd2e97d7233af4f4c69ee36f1e8443e0e443a48f6faac61c1a76 |