N-Queens · Nhóm: Đệ quy
Đặt N quân hậu lên bàn cờ N·N sao cho không hai hậu nào ăn nhau, giải bằng vét cạn có quay lui theo từng hàng.
Đặt hậu theo từng hàng, mỗi hàng đúng một hậu; tại mỗi hàng thử lần lượt từng cột.
Kiểm tra an toàn: không cùng cột và không cùng đường chéo với các hậu đã đặt (lệch cột đúng bằng lệch hàng là cùng chéo).
Ô an toàn thì đặt hậu rồi đệ quy xuống hàng dưới; bế tắc thì gỡ hậu, quay lui thử cột khác của hàng trên.
Ràng buộc theo cột và chéo cho phép cắt tỉa sớm ngay khi vừa đặt, nên cây tìm kiếm nhỏ hơn nhiều so với xét đủ mọi cách xếp; quay lui chỉ giữ một trạng thái bàn cờ và lần ngược khi hỏng.
def solve(row, cols, board, n):
if row == n: # all queens placed
return True
for col in range(n): # try each column
if safe(cols, board, row, col):
board[row] = col # place queen
if solve(row + 1, cols, board, n):
return True
# conflict or dead end: backtrack
return False # no column works here
Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.