Backtracking Python package
Project description
BackTracker Class
The BackTracker class is a Python implementation of the backtracking algorithm, designed for solving problems where a sequence of decisions leads to a solution. This generic framework can be adapted to various problems, such as puzzles, crosswords, combinatorial problems, etc.
This is based on Steven Skiena.
GitHub Page: https://github.com/ryan-najafi/backtracker
Features
Generic backtracking implementation. Customizable for a wide range of problems. Allows defining problem-specific solution processing, candidate generation, and move making/unmaking.
Installation
pip install backtracker==0.0.7
Usage
To use the BackTracker class, you need to define functions for:
Checking if a current state is a solution (is_solution). Processing a complete solution (process_solution). Generating candidate moves (get_candidates). Making a move (make_move). Unmaking a move (unmake_move).
Here's an example demonstrating how to use the BackTracker class to generate combinations of elements:
from backtracker import backtracker as bt
from backtracker import BackTracker
a = []
level = 0
def is_solution(a, k, input):
return len(a) == len(input)
def process_solution(a, k, input):
result = []
for i, item in enumerate(a):
if item:
result.append(input[i])
return ''.join(result)
def get_candidates(a, k, input):
return [False, True]
def make_move(a, k, input, c):
a.append(c)
def unmake_move(a, k, input, c):
a.pop()
input = list('abc')
back_tracker = BackTracker(a=a, level=0, input=input,
is_solution=is_solution,
process_solution=process_solution,
get_candidates=get_candidates,
make_move=make_move,
unmake_move=unmake_move)
for sol in back_tracker.get_next_solution():
print(sol)
In this example, the BackTracker class is used to generate all combinations of the elements in the list 'abc'. The is_solution, process_solution, get_candidates, make_move, and unmake_move functions are defined to suit this specific problem.
Contributing
Contributions to enhance BackTracker are welcome. Please adhere to the standard Python coding guidelines.
License
This project is open-source and available under the MIT License.
Project details
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 backtracker-0.0.7-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 57eda9b97ad639cd29b0af288508fda10d4baad481513fe558ea2ef2c3b9e758 |
|
MD5 | dc1fa7092a4d0586376dbb5b0a2951dc |
|
BLAKE2b-256 | cb4714f852f61b80e16a3844c631c22441b3b21337d492ad2f7ec25edd7bdd3a |