Skip to main content

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.

Title

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 problem
  • get_valid_action_set(self, state : State) : returns the set of valid actions from the given state
  • do_action(self, action: Action, state: State) : returns the new state after doing the given action
  • is_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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

backtracking-0.1.2.tar.gz (5.3 kB view details)

Uploaded Source

Built Distribution

backtracking-0.1.2-py3-none-any.whl (6.2 kB view details)

Uploaded Python 3

File details

Details for the file backtracking-0.1.2.tar.gz.

File metadata

  • Download URL: backtracking-0.1.2.tar.gz
  • Upload date:
  • Size: 5.3 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.9.7

File hashes

Hashes for backtracking-0.1.2.tar.gz
Algorithm Hash digest
SHA256 ddb0b2b049d46183324cdb3a5af06f8385cc52e7315abdea67158ed0eabe9f0b
MD5 cecc5647ccb066a291995c07af48ff57
BLAKE2b-256 018a0cb590ee39800ac8f8cfe33f780d7340e439de2455e83a67c22646b3b4c2

See more details on using hashes here.

File details

Details for the file backtracking-0.1.2-py3-none-any.whl.

File metadata

File hashes

Hashes for backtracking-0.1.2-py3-none-any.whl
Algorithm Hash digest
SHA256 15efa521c76a8cda7a9f9184664db5f7b6bab220aaed3a2b0ead88950f76c84a
MD5 3222258869fc5e4421931ed8c357e891
BLAKE2b-256 51a4d536888bad13a378c45a4e507e4effbe5ad0293bd6d229d7edda3d8daa8f

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page