Lecture "Backtracking algorithms", exercise 1

[essepuntato]

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.

[dbrembilla]

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 solvefunction? 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

[fcagnola]

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

[AlessandroBertozzi]

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

[ConstiDami]

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

[diegochillo]

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.")

[AlessandraFa]

# 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