def searchSubsets(k, n, subset):
  if k == n+1:
    # process subset
    print(subset)
  else:
    # include k in the subset
    subset.append(k)
    searchSubsets(k+1,n,subset)
    subset.pop()
    # don’t include k in the subset
    searchSubsets(k+1, n, subset)
    
def searchPermutations(n,permutation,chosen):
  if len(permutation) == n:
    print(permutation)
  else:
    for i in range (1,n+1):
        if chosen[i]:
          continue
        chosen[i] = True
        permutation.append(i)
        searchPermutations(n,permutation,chosen)
        chosen[i] = False
        permutation.pop()

def searchQueens(y, n, col, diag1, diag2):
    if y == n:
        return 1  # Return 1 to count a valid arrangement
    count = 0
    for x in range(n):
        if col[x] or diag1[x + y] or diag2[x - y + n - 1]:
            continue
        col[x] = diag1[x + y] = diag2[x - y + n - 1] = True
        count += searchQueens(y + 1, n, col, diag1, diag2)
        col[x] = diag1[x + y] = diag2[x - y + n - 1] = False
    return count

if __name__ == "__main__":
  searchSubsets(1,4,list[int]())
  searchPermutations(4,list[int](),[False]*5)
  n = 16  # Replace with the size of the board
  col = [False] * n
  diag1 = [False] * (2 * n - 1)
  diag2 = [False] * (2 * n - 1)
  solution_count = searchQueens(0, n, col, diag1, diag2)
  print(solution_count)