 # n-queen problem

Sep 18th, 2023
601
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # Eight queens problem
2. # we implement a backtracking algorithm to solve the problem
3. # we use a two-dimensional array to represent the chessboard
4. # 0 stands for an empty cell, 1 stands for a queen
5.
6. sz = 8 # size of the board
7.
8. def main():
9.     a = [[0 for i in range(sz)] for j in range(sz)] # 1 stands for a queen
10.     search(a, 0)
11.
12. def isLegal(a, k, i): # can put a queen at a[k][i]?
13.     # check row
14.     for j in range(0, sz):
15.         if a[k][j] == 1:
16.             return False
17.     # check column
18.     for j in range(0, sz):
19.         if a[j][i] == 1:
20.             return False
21.     # check diagonal
22.     for x in range(0, sz):
23.         for y in range(0, sz):
24.             if x + y == k + i and a[x][y] == 1:
25.                 return False
26.             if x - y == k - i and a[x][y] == 1:
27.                 return False
28.
29.     return True
30.
31. def search(a, k): # search for a solution starting from row k in a existing chessboard a
32.     if k == sz: # we have found a solution
33.         printFormated(a)
34.         return
35.     for i in range(0, sz):
36.         if isLegal(a, k, i):
37.             a[k][i] = 1 # put a queen at a[k][i]
38.             search(a, k + 1) # search for a solution starting from row k + 1
39.             a[k][i] = 0 # remove the queen at a[k][i]
40.
41. kase = 0
42. def printFormated(a):
43.     global kase
44.     kase += 1
45.     print("Case", kase, ":")
46.     for i in range(0, sz):
47.         for j in range(0, sz):
48.             if a[i][j] == 1:
49.                 print("Q", end = " ")
50.             else:
51.                 print("*", end = " ")
52.         print('')
53.     print('')
54.
55. main()
56. print("Total:", kase)