def isSafe(k, i):
    for j in range(1, k):
        if x[j] == i or abs(x[j] - i) == abs(j - k):
            return False
    return True


def NQueen(k, n):
    for i in range(1, n + 1):
        if isSafe(k, i):
            x[k] = i

            if k == n:
                print(x[1:n + 1])
            else:
                NQueen(k + 1, n)


# Example
n = int(input("Enter n: "))
x = [0] * (n + 1)

NQueen(1, n)