Build a checkers solving program to help the user find the best possible move in
checkers using backtracking recursion
create a 2d list for the board
assume all pieces are kings
B for black pieces
W for white pieces
” ” space for empty spaces
init method should accept a board, ensure it’s a valid checker board or raise an exception
for every white piece, calculate the maximum number of jumps it can go
class CheckersSolver:
def __init__(self, board):
self.board = board
self.ROW, self.COL = len(board), len(board[0])
self.WHITE, self.BLACK = “W”, “B”
def is_valid_move(self, x, y, dx, dy):
if x + dx < 0 or x + dx >= self.ROW or y + dy < 0 or y + dy >= self.COL:
return False
if self.board[x + dx][y + dy] != ” “:
return False
return True
def solve(self, x, y, move_count):
max_moves = move_count
for dx in [–1, 1]:
for dy in [–1, 1]:
if self.is_valid_move(x, y, dx, dy):
self.board[x + dx][y + dy] = self.WHITE
self.board[x][y] = ” ”
curr_moves = self.solve(x + dx, y + dy, move_count + 1)
self.board[x][y] = self.WHITE
self.board[x + dx][y + dy] = ” ”
max_moves = max(max_moves, curr_moves)
return max_moves
def find_best_move(self):
max_moves = 0
for i in range(self.ROW):
for j in range(self.COL):
if self.board[i][j] == self.WHITE:
curr_moves = self.solve(i, j, 0)
max_moves = max(max_moves, curr_moves)
return max_moves
Main.py
from project_1 import CheckersSolver
board = [[“B”, ” “, “B”, ” “, “B”],
[” “, “W”, ” “, “W”, ” “],
[“B”, ” “, “B”, ” “, “B”],
[” “, “W”, ” “, “W”, ” “],
[“B”, ” “, “B”, ” “, “B”]]
solver = CheckersSolver(board)
print(“Max moves:”, solver.find_best_move())