def solve_n_queens(N):

# Mảng đánh dấu các cột và đường chéo đã có quân Hậu

col = [False] * (N + 1)

diag1 = [False] * (2 * N + 1) # Đường chéo chính (i - j + N)

diag2 = [False] * (2 * N + 1) # Đường chéo phụ (i + j)

pos = [0] * (N + 1) # pos[i] = j: quân Hậu hàng i đặt tại cột j

solutions = []

def backtrack(i):

for j in range(1, N + 1):

if not col[j] and not diag1[i - j + N] and not diag2[i + j]:

# Đặt quân Hậu vào vị trí (i, j)

pos[i] = j

col[j] = diag1[i - j + N] = diag2[i + j] = True

if i == N:

# Đã đặt xong N quân Hậu

solutions.append(pos[1:].copy())

else:

backtrack(i + 1)

# Bỏ quân Hậu ra để thử vị trí khác (Quay lui)

col[j] = diag1[i - j + N] = diag2[i + j] = False

backtrack(1)

return solutions

# Main

if __name__ == "__main__":

N = int(input("Nhập N: "))

solutions = solve_n_queens(N)

if not solutions:

print(f"Không có cách đặt nào cho N = {N}")

else:

# a) Tìm MỘT cách đặt N quân Hậu

print(f"--- Câu a: Một cách đặt {N} quân Hậu ---")

print("Cột đặt quân Hậu từ hàng 1 đến hàng N:", solutions[0])

# b) Ghi TẤT CẢ các cách đặt vào tệp N_HAU.OUT

with open("N_HAU.OUT", "w", encoding="utf-8") as f:

f.write(f"Tổng số cách đặt: {len(solutions)}\n\n")

for idx, sol in enumerate(solutions, 1):

f.write(f"Cách {idx}: " + " ".join(map(str, sol)) + "\n")

print(f"\n--- Câu b: Đã ghi tất cả {len(solutions)} cách đặt vào tệp N_HAU.OUT ---")