Sinh hoán vị và đặt hậu bằng quay lui

Lan xếp ba thẻ mang số 1, 1, 2 thành một hàng để tạo mã. Hai thẻ ghi 1 nhìn giống nhau, nên đổi chỗ chúng không tạo mã mới. Sau đó, Lan muốn đặt bốn quân hậu lên bàn cờ mà không quân nào ăn quân khác. Hai việc đều cần thử thứ tự, nhưng mỗi việc có quy tắc loại lựa chọn riêng.

Thứ tự tạo ra các hoán vị khác nhau

Hoán vị (permutation) của các phần tử là một cách sắp xếp dùng mỗi phần tử đúng một lần. Với ba thẻ khác nhau A, B, C, hàng A B C khác hàng B A C. Ngược lại, khi chỉ chọn một nhóm mà không xét thứ tự, hai cách ghi đó cùng một nhóm. Xem Bài 24 để ôn cách chọn nhóm.

Chương trình sau liệt kê các cách xếp ba thẻ khác nhau. Hàm permutations trong thư viện chuẩn tạo các bộ theo thứ tự của đầu vào:

from itertools import permutations

for order in permutations([1, 2, 3]):
    print(*order)

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Kết quả có sáu dòng. Có ba lựa chọn cho vị trí đầu, hai cho vị trí tiếp và một cho vị trí cuối. Quy tắc nhân cho 3 * 2 * 1 = 6 cách. Với n phần tử phân biệt, số cách là giai thừa (factorial) n! = n * (n - 1) * ... * 1. Theo quy ước, 0! = 1: có một cách tạo hàng rỗng.

Chi phí tăng nhanh ngay cả khi kiểm tra từng kết quả mất rất ít thời gian. Đoạn sau tính số cách, chưa kể công in từng phần tử:

from math import factorial

for n in [0, 4, 8, 10]:
    print(n, factorial(n))

0 1
4 24
8 40320
10 3628800

Với mười thẻ khác nhau có 3.628.800 hàng. Nếu phải in đủ mười số trong mỗi hàng, riêng dữ liệu xuất đã gồm hơn 36 triệu lượt ghi số. Giới hạn đầu ra và thời gian có thể khiến việc in tất cả không khả thi. Trước khi chọn quay lui, bạn cần xem đề yêu cầu in, đếm hay chỉ tìm một cách.

Mỗi tầng chọn một phần tử chưa dùng và hoàn tác

Giả sử bạn tự sinh thứ tự thay vì dùng thư viện. Ta giữ path là các giá trị đã chọn theo thứ tự, và used[i] cho biết thẻ ở chỉ số i đã được chọn hay chưa. Ở mỗi tầng, vòng lặp xét tất cả chỉ số, kể cả những chỉ số nhỏ hơn lần chọn trước. Lựa chọn đã dùng bị bỏ qua; các lựa chọn còn lại tạo các nhánh riêng.

Hình sau theo dõi một nhánh rồi quay lại. Các chỉ số trong hình bắt đầu từ 0:

Đoạn mã sau in các hoán vị và dùng biến used để không đặt một thẻ hai lần:

a = [1, 2, 3]
used = [False] * len(a)
path = []

def visit():
    if len(path) == len(a):
        print(*path)
        return
    for i in range(len(a)):
        if used[i]:
            continue
        used[i] = True
        path.append(a[i])
        visit()
        path.pop()
        used[i] = False

visit()

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Ở đầu mỗi lời gọi, path gồm đúng các thẻ có chỉ số đã đánh dấu. Khi chọn một chỉ số chưa dùng, cả hai trạng thái cùng thay đổi. Sau lời gọi con, pop() và phép gán False trả chúng về như trước. Vì vậy nhánh kế tiếp không bị ảnh hưởng bởi nhánh vừa xét.

Khi path đủ dài, mỗi chỉ số đã dùng đúng một lần nên kết quả là một hoán vị. Mọi hoán vị đều có một chuỗi lựa chọn tương ứng trong vòng lặp, nên không cách nào bị bỏ sót. Với các giá trị phân biệt, mỗi chuỗi chỉ số cho một kết quả khác nhau. Đó là lý do thuật toán vừa đầy đủ vừa không lặp kết quả trong trường hợp này.

Bạn có thể theo dõi riêng nhánh bắt đầu bằng 2. Lúc đầu, path rỗng và cả ba dấu đều tắt. Sau khi chọn chỉ số 1, path là [2] và chỉ dấu tại chỉ số đó bật. Nhánh con có thể chọn 1 hoặc 3, nhưng không thể chọn lại thẻ 2.

Nếu nhánh con chọn tiếp 1, thẻ 3 hoàn tất hàng [2, 1, 3]. Sau khi ghi nhận hàng này, thẻ 3 được bỏ khỏi path và dấu của nó được tắt. Nhánh con kết thúc, rồi thẻ 1 cũng được hoàn tác. Khi ấy path lại là [2], cho phép thử thẻ 3 ngay sau thẻ 2.

Hình sau minh họa các nhánh của lựa chọn đầu tiên. Các nút là trạng thái hàng đã chọn, không phải các thẻ còn lại:

Sau khi thử hết hai lựa chọn tiếp theo của 2, ta hoàn tác cả thẻ 2. Hàng rỗng được phục hồi, nên lựa chọn đầu tiên kế tiếp có thể là 3. Nếu thiếu một dấu hoàn tác, một thẻ bị xem là đã dùng dù không còn trong hàng. Khi đó các kết quả thiếu không dễ phát hiện chỉ bằng cách nhìn một vài dòng đầu.

Với n giá trị phân biệt, có n! lá. Mỗi nút kiểm tra tối đa n chỉ số, nên chặn trên đơn giản là O(n * n!) thời gian. In đầy đủ cũng cần O(n * n!) ký tự số theo số phần tử. Ngoài phần đầu ra, path, used và các lời gọi dùng O(n) bộ nhớ. Tại n = 8, có 40.320 lá; tại n = 10, có 3.628.800 lá.

Một lỗi kín đáo xuất hiện khi lưu path để dùng sau. Danh sách có thể thay đổi, nên phải lưu một bản sao thay vì giữ cùng một đối tượng:

path = [1, 2]
saved = [path[:]]
path.pop()
print("Đang chọn:", path)
print("Đã lưu:", saved)

Đang chọn: [1]
Đã lưu: [[1, 2]]

Danh sách đã lưu vẫn chứa hai số, còn path chỉ còn một số. Nếu dùng saved.append(path), hai tên cùng trỏ đến một danh sách. Những lần hoàn tác sau đó cũng làm thay đổi dữ liệu tưởng như đã lưu.

Sắp xếp và ưu tiên bản sao bên trái để tránh kết quả trùng

Với các thẻ 1, 1, 2, chỉ số của hai thẻ 1 khác nhau nhưng giá trị hiển thị như nhau. Hàm thư viện xem các phần tử ở vị trí khác nhau là khác nhau. Vì vậy, đổi chỗ hai thẻ 1 tạo hai lượt sinh có cùng dãy giá trị:

from itertools import permutations

rows = list(permutations([1, 1, 2]))
print("Số lượt sinh:", len(rows))
print("Số dãy giá trị khác nhau:", len(set(rows)))

Số lượt sinh: 6
Số dãy giá trị khác nhau: 3

Để chỉ sinh mỗi dãy một lần, ta sắp xếp đầu vào. Nếu a[i] bằng a[i - 1] và bản trước chưa được chọn trong nhánh hiện tại, ta bỏ qua i. Nói cách khác, giữa các thẻ bằng nhau, bản ở chỉ số nhỏ hơn phải được chọn trước. Điều kiện này chỉ bỏ bản sao tương đương tại cùng tầng; nó vẫn cho phép đặt cả hai thẻ 1 trong cùng hàng.

Chương trình dưới đây in trực tiếp các hàng khác nhau của Lan:

a = sorted([1, 1, 2])
used = [False] * len(a)
path = []

def visit():
    if len(path) == len(a):
        print(*path)
        return
    for i in range(len(a)):
        if used[i]:
            continue
        if i > 0 and a[i] == a[i - 1] and not used[i - 1]:
            continue
        used[i] = True
        path.append(a[i])
        visit()
        path.pop()
        used[i] = False

visit()

1 1 2
1 2 1
2 1 1

Khi nhánh bắt đầu bằng bản 1 bên trái, bản bên phải vẫn có thể được chọn tiếp. Khi nhánh chưa dùng bản bên trái, chọn bản bên phải sẽ tạo đúng các dãy đã có ở nhánh kia. Mỗi dãy giá trị có đúng một cách gán các chỉ số bằng nhau theo thứ tự tăng. Vì vậy quy tắc giữ lại một đại diện và không loại mất dãy hợp lệ.

Xét hai thẻ 1 ở chỉ số 0 và 1. Ở tầng đầu, thử chỉ số 0 là đủ để đại diện cho việc bắt đầu bằng giá trị 1. Sau đó, vì chỉ số 0 đã được chọn, chỉ số 1 có thể tạo tiền tố [1, 1]. Khi quay về tầng đầu, chỉ số 0 chưa dùng nên nhánh bắt đầu bằng chỉ số 1 bị bỏ. Quy tắc này phụ thuộc trạng thái của nhánh hiện tại, không phụ thuộc số kết quả đã in.

Nếu các thẻ là [-2, -2, 0], việc so sánh và đánh dấu hoạt động y hệt với số âm. Nếu đề phân biệt từng thẻ theo mã riêng, chẳng hạn hai bạn cùng tên, hai thẻ bằng tên vẫn có thể là hai đối tượng khác nhau. Khi đó không được khử trùng chỉ dựa vào tên. Bạn phải làm rõ đề yêu cầu thứ tự của giá trị hay thứ tự của từng đối tượng.

Hãy so sánh với điều kiện đảo ngược: bỏ qua khi bản trước đã dùng. Điều kiện này cũng sinh đúng mỗi dãy một lần, vì nó buộc các bản sao được chọn theo thứ tự ngược lại. Nhưng nó chỉ phát hiện nhánh thừa ở tầng sâu hơn, nên phải đi vào nhiều nhánh cụt rồi mới bị loại. Điều kiện not used[i - 1] loại bản sao ngay ở tầng đang chọn nên duyệt ít trạng thái hơn.

Khi chỉ cần đếm, có thể không sinh dãy nào. Chương trình sau dùng Counter cho một trường hợp biên: cả ba thẻ đều giống nhau.

from collections import Counter
from math import factorial

cards = [5, 5, 5]
ways = factorial(len(cards))
for count in Counter(cards).values():
    ways //= factorial(count)
print(ways)

1

Công thức chia n! cho giai thừa của số lần xuất hiện từng giá trị. Nó đếm các dãy khác nhau, nhưng không tự sinh các dãy đó. Khi cần liệt kê và kiểm tra thêm điều kiện theo vị trí, cách dùng used vẫn hữu ích. Chi phí sinh không vượt chặn O(n * n!); số kết quả thực tế có thể nhỏ hơn nhiều khi có nhiều giá trị trùng.

Mỗi hàng của bàn cờ chọn một cột

Một quân hậu tấn công quân khác nếu chúng cùng hàng, cùng cột hoặc cùng đường chéo. Bài toán N-Queens yêu cầu đặt n quân hậu trên bàn n × n sao cho không đôi nào tấn công nhau. Ta đánh số hàng và cột từ 0 đến n - 1.

Đặt đúng một quân ở mỗi hàng sẽ tự ngăn xung đột hàng. Danh sách path lưu cột đã chọn cho từng hàng. Chẳng hạn path = [1, 3, 0, 2] nghĩa là hàng 0 đặt ở cột 1, hàng 1 đặt ở cột 3, và tiếp tục như vậy. Nếu mỗi cột chỉ dùng một lần, path là hoán vị của các cột.

Bảng sau do mã tạo từ chính danh sách đó. Ký hiệu Q là quân hậu, dấu . là ô trống:

Mỗi dòng có đúng một quân và mỗi cột cũng có một quân. Hai điều đó chưa đủ: hai quân ở (0, 0) và (1, 1) khác hàng, khác cột nhưng vẫn chung đường chéo. Vì thế ta cần thêm kiểm tra cho hai hướng chéo.

Hai phép tính nhận diện hai hướng đường chéo

Trên đường chéo \, đi xuống một hàng và sang phải một cột làm cả hai chỉ số tăng một. Hiệu row - col vì vậy không đổi. Trên đường chéo /, đi xuống một hàng và sang trái một cột làm tổng row + col không đổi. Hai ô có cùng hiệu hoặc cùng tổng tương ứng nằm trên cùng đường chéo.

Đoạn mã sau tính hai giá trị cho các ô cụ thể:

cells = [(0, 1), (1, 2), (0, 2), (1, 1)]
for row, col in cells:
    print((row, col), row - col, row + col)

(0, 1) -1 1
(1, 2) -1 3
(0, 2) -2 2
(1, 1) 0 2

Hai ô đầu có cùng hiệu -1, nên cùng đường chéo \. Hai ô cuối có cùng tổng 2, nên cùng đường chéo /. Trên bàn n × n, hiệu nằm từ -(n - 1) đến n - 1. Cộng n - 1 đưa hiệu vào khoảng chỉ số 0 đến 2 * n - 2. Tổng cũng nằm trong khoảng này, nên mỗi hướng cần 2 * n - 1 ô đánh dấu.

Với n = 4, ô (0, 1) dùng chỉ số hiệu 2 và chỉ số tổng 1. Ô (1, 2) cũng dùng chỉ số hiệu 2, do đó bị loại nếu quân đầu đã đặt. Dùng chỉ số đã dịch cũng tránh nhầm chỉ số âm của Python với ô tính từ cuối danh sách.

Đánh dấu cột và đường chéo để đếm cách đặt hậu

Ta tạo ba danh sách Boolean: cols cho cột, diag1 cho hiệu đã dịch và diag2 cho tổng. Ở hàng đang xét, một ô hợp lệ khi cả ba dấu tương ứng đều chưa bật. Chọn ô sẽ bật cả ba dấu, rồi xử lý hàng tiếp theo. Sau khi lời gọi con kết thúc, ta tắt đúng ba dấu để thử cột khác.

Chương trình đọc kích thước bàn và in số cách. Nó đếm các cách theo vị trí thực tế, kể cả hai cách đối xứng:

4

n = int(input())
cols = [False] * n
diag1 = [False] * (2 * n - 1)
diag2 = [False] * (2 * n - 1)

def count(row):
    if row == n:
        return 1
    total = 0
    for col in range(n):
        d1 = row - col + n - 1
        d2 = row + col
        if cols[col] or diag1[d1] or diag2[d2]:
            continue
        cols[col] = diag1[d1] = diag2[d2] = True
        total += count(row + 1)
        cols[col] = diag1[d1] = diag2[d2] = False
    return total

print(count(0))

2

Kết quả là hai cách. Với nhánh bắt đầu ở cột 1, hàng 1 chỉ còn cột 3 hợp lệ. Tiếp đó hàng 2 chọn cột 0 và hàng 3 chọn cột 2. Nhánh đối xứng bắt đầu ở cột 2 tạo cách còn lại. Những nhánh bị kẹt đóng góp không cách nào vì vòng lặp không tìm được ô hợp lệ.

Chứng minh dựa trên trạng thái trước mỗi lời gọi count(row). Các dấu biểu diễn đúng các quân ở những hàng trước và những quân ấy không tấn công nhau. Điều kiện kiểm tra giữ tính chất đó khi thêm một quân. Khi row == n, mỗi hàng có một quân và mọi cặp đều an toàn, nên trả về một. Ngược lại, mọi cách hợp lệ đều đi qua lựa chọn cột của nó tại từng hàng, nên được đếm đúng một lần.

Vì cột không lặp, độ sâu r có nhiều nhất n! / (n-r)! trạng thái. Mỗi trạng thái thử tối đa n cột; một chặn trên gọn là O(n * n!), với bộ nhớ phụ O(n). Các đường chéo loại thêm nhánh, nhưng không bảo đảm thời gian nhỏ cho mọi n. Ví dụ n = 8 có nhiều nhất 40.320 hoán vị cột đầy đủ trước khi xét chéo. Với kích thước lớn hơn, hãy đo trên môi trường chấm và cân nhắc giới hạn cụ thể.

Trường hợp n = 1 có một cách. Với n = 2 hoặc n = 3, không có cách đặt đủ hậu. Điều kiện dừng vẫn trả kết quả đúng mà không cần gán sẵn một bảng đáp án. Mã mẫu nhận n >= 1; nếu đề cho bàn rỗng, phải thống nhất trước rằng nó có được tính là một cách hay không.

Lỗi thường gặp

Tóm tắt

• Hoán vị xét thứ tự và dùng mỗi phần tử một lần.
• Trạng thái được chọn phải được hoàn tác trước khi xét nhánh khác.
• Sắp xếp và ưu tiên bản sao bên trái giúp sinh dãy giá trị không trùng.
• Với hậu, mỗi hàng chọn một cột; hiệu và tổng nhận diện hai hướng chéo.
• Số nhánh tăng rất nhanh, nên giới hạn đầu vào và đầu ra quyết định cách làm.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về itertools.permutations giải thích thứ tự sinh và cách phân biệt phần tử theo vị trí.
• Google OR-Tools: bài toán N-Queens trình bày các ràng buộc hàng, cột và đường chéo.