Lecture "Backtracking algorithms", exercise 1

[essepuntato]

Propose some variation to the implementation of the peg solitaire exercise to make it more efficient – in particular, avoiding unsuccessful configurations if they have been previously encountered while looking for a solution.

[MaddaGh]

def solve(pegs, holes, last_move, losing_board):        
    result = None

    if len(pegs) == 1 and (5, 1) in pegs: 
        result = last_move
    else:
        last_move.children = valid_moves(pegs, holes)

        if len(last_move.children) == 0: 
            losing_board.append(last_move)
            undo_move(last_move, pegs, holes)         

        else:  
            possible_moves = deque(last_move.children)         

            while result is None and len(possible_moves) > 0:                
                current_move = possible_moves.pop() 
                if current_move in losing_board:
                    result = None 
                else:                                       
                    apply_move(current_move, pegs, holes)
                    result = solve(pegs, holes, current_move, losing_board)                   

            if result is None: 
                if current_move not in losing_board:
                    losing_board.append(current_move)              
                undo_move(last_move, pegs, holes)  

    return result

losing_board = []
print(test_solve(pegs, holes, Node("start"), losing_board, (5, 1)))

[Postitisnt]

We (me and Tommaso Battisti) have tried to solve the problem without adding the set part in (set(pegs)), so appending the pegs only with .append(pegs) and always resulting in an error, so we looked at the solution proposed in the CTBook finding out that we were missing that set part. We didn't understand why there is the need of adding that set inside the append method.

To see the efficiency of the function we have used a list rec in which we inserted an "a" at every backtracking step, to compare the length of the list of this function (that is the number of times in which the backtracking occurred) with the length of the list in the original one. We find out that for the original function the backtracking has occurred 8517 times, while in our solution it occurs only 364 times.

def solve(pegs, holes, last_move, memo, rec):
    result = None

    if pegs not in memo:

        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

                memo.append(set(pegs))
                undo_move(last_move, pegs, holes)  # backtracking
                rec.append("a") 

            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, memo, rec)

                if result is None:
                    memo.append(set(pegs))
                    undo_move(last_move, pegs, holes)
                    rec.append("a")  # backtracking
    else:
        undo_move(last_move, pegs, holes)

    print(len(rec))
    return result

[chloeppd]

I tried to implement a similar logic to that of dynamic programming algorithms using a dictionary. I could not test its efficiency accurately and therefore I suppose it's probably incorrect but I thought I would post it anyway.

# 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):
    bad_cases_dict={}
    result = None

    if len(pegs) == 1 and (5, 1) in pegs:  # leaf-win base case
        result = last_move
    elif last_move not in bad_cases_dict:
            last_move.children = valid_moves(pegs, holes)

            if len(last_move.children) == 0:  # leaf-lose base case
                bad_cases_dict=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)

                if result is None:

                    undo_move(last_move, pegs, holes)  # backtracking
                    bad_cases_dict=current_move

    return result

[essepuntato]

@Postitisnt you have to do set(pegs) necessarily to create a copy of the original set instead of passing a reference of the current pegs that will be modified in future recursive passages. Remember that a set, in Python, is a mutable object.

@chloeppd, it is correct to follow the dynamic programming approach, but you have to change the signature of the function by passing your "notebook" to it, avoiding creating it every time at the beginning of the function, otherwise it will be always overwritten with a new object at every recursive step.