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):
XXXXXXXXXXself.board = board
XXXXXXXXXXself.ROW, self.COL = len(board), len(board[0])
XXXXXXXXXXself.WHITE, self.BLACK = "W", "B"
def is_valid_move(self, x, y, dx, dy):
XXXXXXXXXXif x + dx < 0 or x + dx >= self.ROW or y + dy < 0 or y + dy >= self.COL:
XXXXXXXXXXreturn False
XXXXXXXXXXif self.board[x + dx][y + dy] != " ":
XXXXXXXXXXreturn False
XXXXXXXXXXreturn True
def solve(self, x, y, move_count):
XXXXXXXXXXmax_moves = move_count
XXXXXXXXXXfor dx in [-1, 1]:
XXXXXXXXXXfor dy in [-1, 1]:
XXXXXXXXXXif self.is_valid_move(x, y, dx, dy):
XXXXXXXXXXself.board[x + dx][y + dy] = self.WHITE
XXXXXXXXXXself.board[x][y] = " "
XXXXXXXXXXcu
_moves = self.solve(x + dx, y + dy, move_count + 1)
XXXXXXXXXXself.board[x][y] = self.WHITE
XXXXXXXXXXself.board[x + dx][y + dy] = " "
XXXXXXXXXXmax_moves = max(max_moves, cu
_moves)
XXXXXXXXXXreturn max_moves
def find_best_move(self):
XXXXXXXXXXmax_moves = 0
XXXXXXXXXXfor i in range(self.ROW):
XXXXXXXXXXfor j in range(self.COL):
XXXXXXXXXXif self.board[i][j] == self.WHITE:
XXXXXXXXXXcu
_moves = self.solve(i, j, 0)
XXXXXXXXXXmax_moves = max(max_moves, cu
_moves)
XXXXXXXXXXreturn max_moves
Main.py
from project_1 import CheckersSolve
oard = [["B", " ", "B", " ", "B"],
[" ", "W", " ", "W", " "],
["B", " ", "B", " ", "B"],
[" ", "W", " ", "W", " "],
["B", " ", "B", " ", "B"]]
solver = CheckersSolver(board)
print("Max moves:", solver.find_best_move())
Explore the time required to remove an item from a given index and graph the results.
You could try having the x axis be the size of the list and the y axis be the time required
to remove index 0
Explore the time required to insert an item at the beginning of a list of N size and graph
the results
The x axis could be the size of the list and the y axis be the time required
(install the matplotlib module)
def compute_time_to_add(list_to_add_to, item):
start = time.perf_counter()
list_to_add_to.append(item)
end = time.perf_counter()
return end-start
timings = []
some_list = []
values = range(10_000_000)
for n in values:
timings.append(compute_time_to_add(some_list, n))
plt.plot(values, timings)
plt.show()