Giải thuật vét cạn python
Bài toán xếp hậu là một bài toán kinh điển thường được giới thiệu trong các cuốn sách về thuật toán. Ở đây, chúng ta sẽ giải quyết bài toán bằng các sử dụng giải thuật đệ quy và thuật toán quay lui (vét cạn). Show Xem thêm: Thuật toán giải sudoku bằng quay lui backtracking Xét bàn cờ tổng quát kích thước Ví dụ một cách xếp với 1. Giải bài toán xếp hậu sử dụng đệ quyĐể giải quyết bài toán
xếp 8 quân hậu này, chúng ta sử dụng list (mảng) 1.1. Tạo danh sách để lưu vị trí các quân hậuĐể khởi tạo mảng n = 8 a = n*[0] Lưu ý rằng các list danh sách trong Python được đánh chỉ số từ Ví dụ 1.2. Viết hàm in vị trí các quân hậu dạng ma trậnChúng ta sẽ viết một hàm 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 Hàm in vị trí các quân hậu như sau: def print_board(b): l = len(b) for i in range(l): for j in range(l): if j == a[i]: print(1, end = " ") else: print(0, end = " ") print() 1.3. Viết hàm kiểm tra vị trí (d,c) có còn đặt được quân hậu mới không?Chúng ta quy ước Rõ ràng, ta chỉ cần kiểm tra xem trong các dòng từ Chúng ta viết hàm
Lưu ý rằng các đường chéo sẽ song song hoặc trùng với các tia phân giác của góc phần tư trong hệ tọa độ a[i] == c or c - d == a[i] - i or c + d == a[i] + i Mã nguồn của hàm kiểm tra vị trí có thể đặt hậu như sau: def possible(x, y): for i in range(x): if a[i] == y or y - x == a[i] - i or y + x == a[i] + i: return False return True 1.4. Hàm đệ quy để sinh ra các vị trí đặt quân hậudef gen(i, n): for j in range(n): if possible(i,j): a[i] = j if i == n - 1: print(a) gen(i+1, n) Chương trình bắt đầu với lời gọi Mã nguồn hoàn chỉnh bằng Python của bài toán xếp hậu như sau: n = 8 a = n*[0] def print_board(b): l = len(b) for i in range(l): for j in range(l): if j == a[i]: print(1, end = " ") else: print(0, end = " ") print() def possible(d, c): for i in range(d): # if a[i] == y or abs(i - x) == abs(a[i] - y): if a[i] == c or c - d == a[i] - i or c + d == a[i] + i: return False return True def gen(i, n): for j in range(n): if possible(i,j): a[i] = j if i == n - 1: print(a) gen(i+1, n) gen(0, n) Kết quả trả về là tất cả các phương án mỗi phương án là một danh sách chứa vị trí các quân hậu. Nếu muốn in một phương án nào đó, chúng ta sử dụng hàm 2. Bài toán xếp hậu quay luiChúng tôi giới thiệu thêm bài toán xếp hậu sử dụng thuật toán quay lui để bạn đọc tham khảo. Cách làm này có thời gian chạy khá chậm, và mỗi lần chỉ in ra một phương án xếp các quân hậu. Muốn tìm được phương án khác, chúng ta cần thay đổi giá trị của mảng board ban đầu. Cách giải này tôi có tham khảo từ bài viết này. board = [ [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0] ] def print_board(bo): for d in bo: for c in d: print(c, end = " ") print() def solve(bo): l = len(bo) for d in range(l): for c in range(l): if bo[d][c] == 0: if possible(bo, d, c): bo[d][c] = 1 solve(bo) if sum(sum(a) for a in bo) == l: return bo else: bo[d][c] = 0 return bo def possible(bo, d, c): l = len(bo) for i in range(l): if bo[i][c] == 1: return False for i in range(l): if bo[d][i] == 1: return False for i in range(l): for j in range(l): if bo[i][j] == 1: if c-d == j-i or c+d == i+j: return False return True solve(board) print_board(board) |