|
|
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) |