Lecture "Backtracking algorithms", exercise 1
essepuntato opened this issue · 6 comments
Propose some variation to the implementation of the peg solitaire exercise in order to make it more efficient – in particular, avoiding unsuccessful configurations if they have been already encountered previously while looking for a solution.
I created a bad moves dictionary in order to store the wrong cases, and the test runs True. However, I'm not sure that it improved the algorithm's efficiency, is there a way I can measure that? Here I paste the new solve
function? I used the given test function and it returns True
#badmoves_dict
bad_moves=set()
# Code of the algorithm
def solve(pegs, holes, last_move, d):
result = None
if last_move not in d:
if len(pegs)== 1 and (5, 1) in pegs: # leaf-win base case; there is one peg left and it is in the right place
result = last_move
else:
last_move.children = valid_moves(pegs, holes) #create valid moves
if len(last_move.children) == 0: # leaf-lose base case; no more moves left and not in win case
bad_moves.add(last_move)
undo_move(last_move, pegs, holes) # backtracking
else: # recursive step
possible_moves = deque(last_move.children)
while result is None and len(possible_moves) > 0:
current_move = possible_moves.pop()
apply_move(current_move, pegs, holes)
result = solve(pegs, holes, current_move, d)
if result is None:
bad_move.add(last_move)
undo_move(last_move, pegs, holes) # backtracking
else:
undo_move(last_move, pegs, holes)
return result
import time
from pprint import pprint
from anytree import Node
from collections import deque
# Test case for the algorithm
def test_solve(pegs, holes, last_move, expected):
result = solve(pegs, holes, last_move)
if expected == result.name["in"] and len(pegs) == 1:
return True
else:
return False
# Code of the algorithm
def solve(pegs, holes, last_move):
result = None
if last_move not in bad_moves:
if len(pegs) == 1 and (5, 1) in pegs: # leaf-win base case
result = last_move
else:
last_move.children = valid_moves(pegs, holes) # set valid moves given current state as children of last move
if len(last_move.children) == 0: # leaf-lose base case
bad_moves.add(last_move) # improving the process of computing results
undo_move(last_move, pegs, holes) # backtracking
else: # recursive step
possible_moves = deque(last_move.children)
for i in possible_moves: # improving the process of computing results
if i in bad_moves:
possible_moves.remove(i)
while result is None and len(possible_moves) > 0:
current_move = possible_moves.pop()
apply_move(current_move, pegs, holes)
result = solve(pegs, holes, current_move)
if result is None:
bad_moves.add(last_move) # improving the process of computing results
undo_move(last_move, pegs, holes) # backtracking
else:
undo_move(last_move, pegs, holes)
return result
pegs, holes = create_board()
bad_moves = set()
start_time = time.time()
print(test_solve(pegs, holes, Node("start"), (5, 1)))
print("--- %s seconds ---" % (time.time() - start_time))
# time with set: 0.1843252182006836 seconds
# time without set: 0.18454599380493164 seconds
Gabriele Fiorenza, Samuele Spotti and I reached this solution together.
# Code of the algorithm
def solve(pegs, holes, last_move, error_list):
result = None
if len(pegs) == 1 and (5, 1) in pegs: # leaf-win base case
result = last_move
else:
if list(pegs) not in error_list:
last_move.children = valid_moves(pegs, holes)
if len(last_move.children) == 0: # leaf-lose base case
a = list(pegs)
error_list.append(a)
undo_move(last_move, pegs, holes) # backtracking
else: # recursive step
possible_moves = deque(last_move.children)
while result is None and len(possible_moves) > 0:
current_move = possible_moves.pop()
apply_move(current_move, pegs, holes)
result = solve(pegs, holes, current_move, error_list)
if result is None:
a = list(pegs)
error_list.append(a)
undo_move(last_move, pegs, holes) # backtracking
else:
undo_move(last_move, pegs, holes)
return result
wrong_moves = set()
def solve(pegs, holes, last_move):
result = None
if len(pegs) == 1 and (5, 1) in pegs: # leaf-win base case
result = last_move
else:
last_move.children = valid_moves(pegs, holes)
if len(last_move.children) == 0: # leaf-lose base case
wrong_moves.add(last_move)
undo_move(last_move, pegs, holes) # backtracking
else: # recursive step
possible_moves = deque(last_move.children)
for child in last_move.children:
if child in wrong_moves:
break
else:
while result is None and len(possible_moves) > 0:
current_move = possible_moves.pop()
apply_move(current_move, pegs, holes)
result = solve(pegs, holes, current_move)
if result is None:
wrong_moves.add(last_move)
undo_move(last_move, pegs, holes) # backtracking
return result
Without dynamic check, the recursion happens 7832 times.
With the preliminary dynamic check of the wrong moves, the recursion happens only 767 times.
from anytree import Node
from collections import deque
# Test case for the algorithm
def test_solve(pegs, holes, last_move, wrong_conf, expected):
result = solve(pegs, holes, last_move, wrong_conf)
if expected == result.name["in"] and len(pegs) == 1:
return True
else:
return False
# Code of the algorithm
def solve(pegs, holes, last_move, wrong_conf):
global counter # To store the number of times the function has been called
result = None
counter+=1
# del wrong_conf[:] # Uncomment to bypass the dynamic check again and see the difference in counter
if pegs not in wrong_conf:
if len(pegs) == 1 and (5, 1) in pegs: # leaf-win base case
result = last_move
else:
last_move.children = valid_moves(pegs, holes)
if len(last_move.children) == 0: # leaf-lose base case
wrong_conf.append(set(pegs))
undo_move(last_move, pegs, holes) # backtracking
else: # recursive step
possible_moves = deque(last_move.children)
while result is None and len(possible_moves) > 0:
current_move = possible_moves.pop()
apply_move(current_move, pegs, holes)
result = solve(pegs, holes, current_move,wrong_conf)
if result is None:
wrong_conf.append(set(pegs))
undo_move(last_move, pegs, holes) # backtracking
else:
undo_move(last_move, pegs, holes) # backtracking
return result
# pegs, holes = create_6x6_square_board()
pegs, holes = create_board()
wrong_conf=list() # List of the peg sets that lead to leaf-lose cases
counter=0 # Counter of the recursion times (global variable)
print(test_solve(pegs, holes, Node("start"), wrong_conf, (5, 1)))
print("Solve function called " + str(counter) + " times.")
# test case function
def test_solve(pegs, holes, last_move, failed_moves, expected):
return solve(pegs,holes,last_move,failed_moves) == expected
# function:
def solve(pegs, holes, last_move, failed_moves):
result = None
if len(pegs) == 1 and (5, 1) in pegs: # leaf-win base case
result = last_move
else:
if tuple(pegs) in failed_moves:
undo_move(last_move, pegs, holes) # backtracking
else:
last_move.children = valid_moves(pegs, holes)
if len(last_move.children) == 0: # leaf-lose base case
failed_moves[tuple(pegs)] = []
undo_move(last_move, pegs, holes) # backtracking
else: # recursive step
possible_moves = deque(last_move.children)
while result is None and len(possible_moves) > 0:
current_move = possible_moves.pop()
apply_move(current_move, pegs, holes)
result = solve(pegs, holes, current_move, failed_moves)
if result is None:
failed_moves[tuple(pegs)] = []
undo_move(last_move, pegs, holes) # backtracking
return result