CSCI 485 --- Fall 2023

Lab 4

Below is the algorithm of the basic backtracking:

function BacktrackingSearch(CSP problem)
    returns a solution or failure
  Begin
    Assignment assignment = emptySet;
    return RecursiveBacktracking(assignment, problem);
  End

function RecursiveBacktracking(Assigngment assignment, CSP problem)
    returns a solution or failure
  Begin
    if problem.isComplete(assignment) then
        return assignment;
    end if
    var = Select_Unassigned_Variable(problem.variables(assignment));
    for each value in problem.Available_Values(var) do
        assignment.add(var, value);
        make a copy of the problem;
        problem.update_available_values(assignment);
        result = Recursive_Backtracking(assignment, problem);
        if result <> failure then
            return result;
        end if
        remove {var = value} from assignment;
        restore the problem copy back to problem;
    end for
    return failure;
  End

Your task:

• Implement an AI agent to solve N-Queen problem.
• (Optional) Use at least two CSP heuristics in your AI agent.
• Test your AI agent using 4-Queen problem, then 8-Queen problem.