tab = 2


def print_board_state(n, solution, indent=1):
    if len(solution) != n:
        return

    # print(" "*indent, "Solution: ", solution, ", move: ", move, sep = "", end = "\n\n")
    indent += tab
    for i in range(n):
        if i == 0:                  # printing the top of the board
            print(" "*indent, " ", "_"*((4*n)-1), sep="")

        print(" "*indent, "|", sep="", end="")
        if solution[n-(i+1)] != -1:  # queen placed in this row in the solution
            for j in range(n):
                print("_X_|" if solution[n-(i+1)] == j else "___|", end="")
        else:                       # no queen in solution in this row, move not in this row
            print("___|"*n, end="")   # so print an empty row
        print("")


def print_solution_on_board(n, solution, move, indent=1):
    if len(solution) != n:
        return

    # print(" "*indent, "Solution: ", solution, ", move: ", move, sep = "", end = "\n\n")
    indent += tab
    for i in range(n):
        if i == 0:                  # printing the top of the board
            print(" "*indent, " ", "_"*((4*n)-1), sep="")

        print(" "*indent, "|", sep="", end="")
        if solution[n-(i+1)] != -1:  # queen placed in this row in the solution
            for j in range(n):
                print("_X_|" if solution[n-(i+1)] == j else "___|", end="")
        elif n-(i+1) == move[0]:   # move is made in this row
            for j in range(n):
                print("_?_|" if move[1] == j else "___|", end="")
        else:                       # no queen in solution in this row, move not in this row
            print("___|"*n, end="")   # so print an empty row
        print("")

# this method determines if a queen can be placed at proposed_row, proposed_col
# with current solution i.e. this move is valid only if no queen in current
# solution may attack the square at proposed_row and proposed_col


def is_valid_move(proposed_row, proposed_col, solution):
    temptab = tab
    temptab += 1
    print("\n", temptab*"  ", "Proposed row: ", proposed_row, sep="")
    print(temptab*"  ", "Proposed column: ", proposed_col, sep="")
    # we need to check if any queen on the board in this solution can attack the proposed cell
    print_solution_on_board(len(solution), solution, [
                            proposed_row, proposed_col], temptab+3)

    for i in range(0, proposed_row):
        old_row = i
        old_col = solution[i]
        diagonal_offset = proposed_row - old_row
        print(temptab*"  ", f"{i + 1}. Old row: ", i, sep="")
        print((temptab + 1)*"  ", " Old column: ", solution[i], sep="")
        print((temptab + 1)*"  ", " Diagonal offset to check: ",
              diagonal_offset, sep="")
        if (old_col == proposed_col or
            old_col == proposed_col - diagonal_offset or
                old_col == proposed_col + diagonal_offset):
            print((temptab + 1)*"  ",
                  f" Invalid move: the proposed cell is vulnerable to attack from the queen at [{i}, {solution[i]}].", sep="")
            return False
        else:
            print((temptab + 1)*"  ",
                  f" The proposed cell is safe from the queen at [{i}, {solution[i]}].", sep="")
    print("\n", (temptab + 1)*"  ",
          "Valid move: the proposed cell is safe.", sep="")
    return True

# Recursive worker function


def solve_n_queens_rec(n, solution, row, results):
    global tab
    for i in range(0, n):
        print(tab*"  ", "Placing queen ", i+1, " in row ", row, sep="")
        tab += 1
        print(tab*"  ", "Checking if the move is valid", sep="")
        valid = is_valid_move(row, i, solution)
        if valid:
            temp = tab + 1
            # Add this valid move to the current solution
            print(
                temp*"  ", "Since the move is valid, we'll add it to the current solution", sep="")
            print(temp*"  ", solution, " ⟶ ", end="", sep="")
            solution[row] = i
            print(solution)
            print_board_state(n, solution, temp+2)
            print("")
            solution = [-1]*n  # reseting the solution for printing

# Function to solve N-Queens problem


def solve_n_queens(n):
    print("\n Initialising variables")
    results = []
    solution = [-1] * n
    print("  Results: ", results, sep="")
    print("  Solution: ", solution, sep="")
    print_board_state(n, solution, 2)
    print("\n Placing the queens")
    solve_n_queens_rec(n, solution, 0, results)
    return len(results)


def main():
    n = [4, 5, 6, 7, 8]
    for i in range(len(n)):
        print(i+1, ". Queens: ",
              n[i], ", Chessboard: (", n[i], "x", n[i], ")", sep="")
        res = solve_n_queens(n[i])
        global tab
        tab = 2
        print("-"*100, "\n", sep="")


if __name__ == '__main__':
    main()