# nqueens.py
# Andrew Davison, Dec 2023, ad@coe.psu.ac.th

# Fig 46.2 
# https://en.wikipedia.org/wiki/Eight_queens_puzzle
# inputs: 8 or 9 or 10

import time, tracemalloc


def examineColumn(i):
  global count
  for j in range(n):
    if isValid(i,j): 
      queens[i] = j  # column i queen is placed in row j

      # this queen attacks these squares
      uprIdx = (i-j) + (n-1)
      row[j] = False
      upl[i+j] = False
      upr[uprIdx] = False

      if i < n-1:
        examineColumn(i+1)
      else:  # found a new solution
        count += 1
        # printBoard(queens, count) # comment out for speed

      # undo state changes for backtracking
      row[j] = True
      upl[i+j] = True
      upr[uprIdx] = True


def isValid(i, j):
  return row[j] and upl[i+j] and upr[(i-j) + (n-1)]


def printBoard(board, count):
  print("Board", count)
  for r in range(n):
    col = queens[r]
    for c in range(n):
      if c == col:
        print("Q", end = ' ')
      else:
        print(".", end = ' ')
    print()
  print()


# ----------------- ma1n ------------------------

n = int(input("n=? "))

start_time = time.time()
tracemalloc.start()

queens = [-1 for i in range(n)]  # dummy values
row = [True]*n
upl = [True]*(2*n)
upr = [True]*(2*n)

count = 0
examineColumn(0)
print("No. of solns:", count)

elapsed_time = time.time() - start_time
_, peakMem = tracemalloc.get_traced_memory()
tracemalloc.stop()

print(f"Duration: {elapsed_time:.3f} secs")
print("Peak memory:", peakMem, "bytes")