python.py
# Pentru n=4, cate solutii de plasare a reginelor exista?
# (Indiciune: gandeste-te la simetrie)
3.4 Backtracking: probleme clasice (permutari, regine)
Citește și prezice
Predicție
python
def regine(n):
solutii = []
sol = []
def valid(lin, col):
for i in range(lin):
if sol[i] == col or abs(sol[i] - col) == lin - i:
return False
return True
def bk(lin):
if lin == n:
solutii.append(sol[:])
return
for col in range(n):
if valid(lin, col):
sol.append(col)
bk(lin + 1)
sol.pop()
bk(0)
return len(solutii)
print(regine(4))