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
Generic backtracking implementation. Customizable for a wide range of problems. Allows defining problem-specific solution processing, candidate generation, and move making/unmaking.
pip install backtracker==0.0.7
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
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):
if len(a) > len(input):
return []
else:
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')
subsets = bt.BackTracker(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 subsets.solutions():
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.
Here's another example to generate all the perumations of elements:
from backtracker import backtracker as bt
def is_solution(a, level, input):
return len(a) == len(input)
def process_solution(a, level, input):
return ''.join(a)
def get_candidates(a, level, input):
return list(set(input) - set(a))
def make_move(a, level, input, c):
a.append(c)
def unmake_move(a, level, input, c):
a.pop()
input = list('abc')
permutations = bt.BackTracker(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 permutations.solutions():
print(sol)
The following shows how to use the BackTracker class to solve Sudoku and get at least three solutions:
input = [[3, 0, 6, 5, 0, 8, 4, 0, 0],
[5, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 7, 0, 0, 0, 0, 3, 1],
[0, 0, 3, 0, 1, 0, 0, 8, 0],
[9, 0, 0, 8, 6, 3, 0, 0, 5],
[0, 5, 0, 0, 9, 0, 6, 0, 0],
[1, 3, 0, 0, 0, 0, 2, 5, 0],
[0, 0, 0, 0, 0, 0, 0, 7, 4],
[0, 0, 5, 2, 0, 6, 3, 0, 0]]
def is_solution(a, level, input):
return level == 9 * 9
def process_solution(a, level, input):
return input
def get_candidates(a, level, input):
row = level // 9
col = level % 9
if level >= 9*9:
return []
if input[row][col] !=0:
return [input[row][col]]
else:
col_values = set([x[col] for x in input])
rect_3x3 = []
for i in range(3 * (row // 3), 3+3 * (row // 3)) :
for j in range(3 * (col // 3),3 + 3 * (col // 3)):
rect_3x3.append(input[i][j])
return list(set(list(range(1, 10))) - set(input[row]) - col_values - set(rect_3x3))
def make_move(a, level, input, c):
a.append(c)
input[level // 9][level % 9] = c
def unmake_move(a, level, input, c):
a.pop()
input[level // 9][level % 9] = 0
sudoku_solver = BackTracker(input=input, is_solution=is_solution, process_solution=process_solution, get_candidates=get_candidates, make_move=make_move, unmake_move=unmake_move)
i = 0
for sol in sudoku_solver.solutions():
print(f'solution number: {i+1}')
for row in sol:
print(row)
print()
i+=1
if i > 3:
break
Contributions to enhance BackTracker are welcome. Please adhere to the standard Python coding guidelines.
This project is open-source and available under the MIT License.