A framework for backtracking algorithm, as an interface and a solving function.
Project description
Backtracking Algorithm
A framework for backtracking algorithm, as an interface and a solving function.
This framework is designed to be used for any backtracking algorithm, and it is not limited to a specific problem.
You need to implement the (quite simple) interface, and then you can use the solve() function to solve your problem and return all (or one) solutions.
The methods to implement are:
get_initial_state()
: returns the initial state of the problemget_valid_action_set(self, state : State)
: returns the set of valid actions from the given statedo_action(self, action: Action, state: State)
: returns the new state after doing the given actionis_state_solution(self, state: State)
: returns True if the given state is a solution, False otherwise
Installation
Install from PyPI:
pip install backtracking
Install from source:
git clone git@github.com:tboulet/backtracking_algorithm.git
cd backtracking_algorithm
pip install -e .
Code example
from backtracking import BacktrackingSolver, State, Action
# The 'State' and 'Action' are just aliases for 'Any' type, for more clarity
class MyProblemSolver(BacktrackingSolver):
def get_initial_state(self) -> State:
pass
def get_valid_action_set(self, state : State) -> List[Action]:
pass
def do_action(self, action: Action, state: State) -> State:
pass
def undo_action(self, action: Action, state: State) -> State: # Optional, only if you want to use the 'use_only_one_state' parameter
pass
def is_state_solution(self, state: State) -> bool:
pass
solver = MyProblemSolver()
solutions = solver.solve(find_all_solutions = True, use_only_one_state = False)
print("Found", len(solutions), "solutions:")
for solution in solutions:
print(solution)
Example : N-Queens Problem
An example of the N-Queens problem is provided in the examples\n_queens.py
file.
The N-Queens problem is a classic problem in which you have to place N queens on a NxN chessboard, such that no queen can attack another queen.
To run it :
python examples\n_queens.py
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 backtracking-0.1.2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 15efa521c76a8cda7a9f9184664db5f7b6bab220aaed3a2b0ead88950f76c84a |
|
MD5 | 3222258869fc5e4421931ed8c357e891 |
|
BLAKE2b-256 | 51a4d536888bad13a378c45a4e507e4effbe5ad0293bd6d229d7edda3d8daa8f |