def _backtracking(problem, assignment, domains, variable_chooser, values_sorter, inference=True):
    '''
    Internal recursive backtracking algorithm.
    '''
    from arc import arc_consistency_3
    if len(assignment) == len(problem.variables):
        return assignment

    pending = [v for v in problem.variables
               if v not in assignment]
    variable = variable_chooser(problem, pending, domains)

    values = values_sorter(problem, assignment, variable, domains)

    for value in values:
        new_assignment = deepcopy(assignment)
        new_assignment[variable] = value

        if not _count_conflicts(problem, new_assignment):  # TODO on aima also checks if using fc
            new_domains = deepcopy(domains)
            new_domains[variable] = [value]

            if not inference or arc_consistency_3(new_domains, problem.constraints):
                result = _backtracking(problem,
                                       new_assignment,
                                       new_domains,
                                       variable_chooser,
                                       values_sorter,
                                       inference=inference)
                if result:
                    return result

    return None
dataset/ETHPy150Open simpleai-team/simpleai/simpleai/search/csp.py/_backtracking/original