# 8 皇后问题

## 8-Queens Problem (recursion)

Posted by xuepro on May 5, 2018

## 8 皇后问题(递归算法)

BOARD_SIZE = 4

class BailOut(Exception):
pass

def validate(queens):
left = right = col = queens[-1]
for r in reversed(queens[:-1]):
left, right = left-1, right+1
if r in (left, col, right):
raise BailOut

for i in range(BOARD_SIZE):
test_queens = queens + [i]
try:
validate(test_queens)
if len(test_queens) == BOARD_SIZE:
return test_queens
else:
except BailOut:
pass
raise BailOut

print(queens)
print("\n".join(". "*q + "Q " + ". "*(BOARD_SIZE-q-1) for q in queens))

print("\n\n---all solution-------\n")
if row==(BOARD_SIZE):
print(queens)
print("\n".join(". "*q + "Q " + ". "*(BOARD_SIZE-q-1) for q in queens))
print("\n")

for col in range(BOARD_SIZE):
test_queens = queens + [col]
try:
validate(test_queens)
except BailOut:
continue



[1, 3, 0, 2]
. Q . .
. . . Q
Q . . .
. . Q .

---all solution-------

[1, 3, 0, 2]
. Q . .
. . . Q
Q . . .
. . Q .

[2, 0, 3, 1]
. . Q .
Q . . .
. . . Q
. Q . .


N皇后问题的两个最高效的算法

The eight queens puzzle in Python