backtracking_sort.py

def backtracking_sort(input_list, output_list, level):

    print(level * '  ', input_list, output_list);

    # Reject - this path doesn't lead to any solution
    if len(output_list) > 1 and output_list[-2] > output_list[-1]:
        return False

    # Accept - one solution
    if not input_list:
        print("Solution: ", output_list)
        return True

    # Step - go over all the possible options in the input
    for n in input_list:
        clone_input_list = input_list[:]
        clone_input_list.remove(n)
        clone_output_list = output_list[:]
        clone_output_list.append(n)
        test = backtracking_sort(clone_input_list,
                clone_output_list, level + 1)
        if test:
            return True

    # No solution
    return False

if __name__ == '__main__':
    input_list = [4, 1, 3]
    output_list = []

    # First call
    backtracking_sort(input_list, output_list, 0);