Bài toán kinh điển N-Queen với Python

NỘI DUNG

Giới thiệu

Bài toán N-Queen là một bài toán cổ điển trong lĩnh vực trí tuệ nhân tạo và toán học, đặt ra vấn đề đặt N quân hậu lên một bàn cờ kích thước N x N sao cho không có hai quân hậu nào đang chiếm cùng một hàng, cột hoặc đường chéo của bàn cờ.

Mục tiêu của bài toán là tìm ra tất cả các cách đặt N quân hậu lên bàn cờ sao cho không có hai quân hậu nào đang chiếm cùng một hàng, cột hoặc đường chéo của bàn cờ.

Bài toán có nguồn gốc từ trò chơi xếp hậu của vua trong cờ vua, trong đó mục tiêu của trò chơi là đặt 8 quân hậu lên bàn cờ sao cho không có hai quân hậu nào đang chiếm cùng một hàng, cột hoặc đường chéo của bàn cờ.

Tuy nhiên, bài toán N-Queen không giới hạn số quân hậu và kích thước bàn cờ, do đó bài toán có thể được áp dụng cho bất kỳ kích thước bàn cờ và số quân hậu nào. Bài toán có ứng dụng trong nhiều lĩnh vực như trong việc tối ưu hóa phân bổ tài nguyên, giải quyết các vấn đề phân loại và tìm kiếm, và trong lĩnh vực phát triển trò chơi và ứng dụng thực tế khác.

Thuật toán N-Queen

Các bước của thuật toán N-Queen để giải quyết bài toán đặt N quân hậu lên bàn cờ kích thước N x N sao cho không có hai quân hậu nào đang chiếm cùng một hàng, cột hoặc đường chéo của bàn cờ có thể được mô tả như sau:

Khởi tạo một bàn cờ kích thước N x N.
Bắt đầu từ hàng đầu tiên, đặt lần lượt các quân hậu vào các ô của hàng đó. Để đơn giản hóa, ta có thể đặt quân hậu từ trái sang phải.
Với mỗi ô đã đặt quân hậu, kiểm tra xem có thỏa mãn yêu cầu không. Nếu không, quay lại bước 2 và đặt quân hậu vào ô tiếp theo. Nếu có, chuyển sang hàng tiếp theo và bắt đầu từ bước 2.
Nếu đã đặt N quân hậu trên bàn cờ mà không có quân hậu nào đang chiếm cùng một hàng, cột hoặc đường chéo, ta sẽ có một giải pháp. Lưu giữ giải pháp này và tiếp tục tìm kiếm các giải pháp khác bằng cách quay lại hàng trước đó và đặt quân hậu vào ô tiếp theo.
Nếu đã thử tất cả các ô trên bàn cờ mà không tìm được giải pháp, quay lại bước trước đó và thử các ô khác.
Khi đã thử tất cả các ô trên bàn cờ và lưu giữ được tất cả các giải pháp, kết thúc thuật toán và trả về các giải pháp đã tìm được.

Thuật toán N-Queen có thể được cải tiến bằng cách sử dụng các kỹ thuật tối ưu hóa như backtracking, pruning hoặc thậm chí sử dụng phương pháp giải quyết bài toán tham lam.

Thuật toán quy hoạch động với bài toán N-Queen

Thuật toán quy hoạch động (dynamic programming) có thể được sử dụng để giải quyết bài toán N-Queen với các bước như sau:

Khởi tạo một mảng 2 chiều dp kích thước N x N và giá trị ban đầu của tất cả các phần tử đều là 0.
Đối với mỗi hàng của bàn cờ từ hàng 1 đến hàng N, thực hiện các bước sau:

a. Đối với mỗi ô của hàng đó, kiểm tra xem có thể đặt quân hậu vào ô đó không (tức là không có quân hậu nào đang chiếm cùng một hàng, cột hoặc đường chéo với ô đó).

b. Nếu có thể đặt quân hậu vào ô đó, thực hiện các bước sau:

i. Nếu đó là hàng đầu tiên (tức là đặt được quân hậu vào ô đó trên hàng đầu tiên), gán giá trị 1 cho ô đó trong mảng dp.

ii. Nếu không phải hàng đầu tiên, ta cần tính toán giá trị của ô đó dựa trên các giá trị của các ô đã đặt quân hậu ở các hàng trước đó. Để đơn giản hóa, ta chỉ cần xét các ô đã đặt quân hậu ở các hàng trước đó trên cùng một cột hoặc đường chéo với ô đang xét. Ta cộng tổng các giá trị của các ô đã đặt quân hậu đó và gán tổng đó cho ô đang xét trong mảng dp.
Sau khi đã duyệt hết tất cả các hàng của bàn cờ, ta sẽ có giá trị của tất cả các ô trong mảng dp. Giá trị của ô ở hàng N và cột N trong mảng dp sẽ là số lượng giải pháp của bài toán N-Queen.
Trả về giá trị số lượng giải pháp của bài toán N-Queen.

Việc tính toán giá trị của mỗi ô trong mảng dp dựa trên các giá trị đã được tính toán trước đó cho phép ta tối ưu thời gian tính toán so với cách giải truyền thống bằng backtracking.

Cài đặt thuật toán quy hoạch động với N-Queen

Đây là code Python để giải quyết bài toán N-Queen bằng phương pháp quy hoạch động:

def n_queen(n):
    # Khởi tạo mảng dp
    dp = [[0 for _ in range(n)] for _ in range(n)]

    # Đặt giá trị 1 cho các ô của hàng đầu tiên
    for i in range(n):
        dp[0][i] = 1

    # Duyệt qua các hàng từ hàng thứ 2 đến hàng cuối cùng
    for i in range(1, n):
        # Duyệt qua các ô của hàng đó
        for j in range(n):
            # Duyệt qua các hàng trước đó trên cùng một cột hoặc đường chéo với ô đang xét
            for k in range(i):
                if dp[k][j] == 1 or (j-i+k >= 0 and dp[k][j-i+k] == 1) or (j+i-k < n and dp[k][j+i-k] == 1):
                    dp[i][j] += dp[k][j]

    # Tổng số lượng giải pháp của bài toán N-Queen là tổng các giá trị ở hàng cuối cùng
    return sum(dp[-1])

Giải thích code:

Dòng 2-3: Khởi tạo mảng dp với giá trị ban đầu của tất cả các phần tử đều là 0.
Dòng 6-8: Đặt giá trị 1 cho các ô của hàng đầu tiên trong mảng dp.
Dòng 11-18: Duyệt qua các hàng từ hàng thứ 2 đến hàng cuối cùng và các ô của hàng đó, và tính giá trị của mỗi ô dựa trên các giá trị của các ô đã đặt quân hậu ở các hàng trước đó.
Dòng 21: Tổng số lượng giải pháp của bài toán N-Queen là tổng các giá trị ở hàng cuối cùng của mảng dp.
Dòng 23: Trả về giá trị số lượng giải pháp của bài toán N-Queen.

Độ phức tạp của thuật toán quy hoạch động với bài toán N-Queen là O(n^3), trong đó n là kích thước bàn cờ và cũng là số lượng quân hậu cần đặt trên bàn cờ. Thuật toán này sử dụng 3 vòng lặp lồng nhau để tính giá trị của từng ô trong mảng dp, do đó có độ phức tạp tuyến tính theo n. Vì vậy, thuật toán này có thể giải quyết được bài toán N-Queen với các giá trị n nhỏ và vừa. Tuy nhiên, với các giá trị lớn của n, thuật toán này có thể trở nên chậm chạp và tốn nhiều thời gian tính toán.

Có một thuật toán khác có độ phức tạp thấp hơn để giải quyết bài toán N-Queen được gọi là thuật toán backtracking. Thuật toán này dựa trên việc tìm kiếm đệ quy và lựa chọn các phương án có thể để giải quyết bài toán. Cụ thể, thuật toán sẽ đệ quy để tìm các cách đặt quân hậu trên từng hàng của bàn cờ, và sau đó lựa chọn cách đặt tiếp theo cho đến khi đặt được n quân hậu. Nếu không thể tìm ra cách đặt nào cho phù hợp thì thuật toán sẽ quay trở lại và thử cách khác. Khi tìm ra một cách đặt hợp lệ, thuật toán sẽ trả về kết quả.

Độ phức tạp của thuật toán backtracking trong trường hợp xấu nhất là O(n!), vì số lượng cách đặt quân hậu trên bàn cờ là n!. Tuy nhiên, thuật toán này thường chạy nhanh hơn so với thuật toán quy hoạch động, đặc biệt là khi giá trị của n lớn.

Thuật toán backtracking với bài toán N-Queen

Các bước thực hiện thuật toán backtracking với bài toán N-Queen như sau:

Khởi tạo một bàn cờ rỗng với kích thước n, đánh dấu tất cả các ô trên bàn cờ là chưa đặt quân hậu.
Bắt đầu từ hàng đầu tiên, đặt quân hậu vào từng ô trên hàng đó. Với mỗi ô, kiểm tra xem nó có bị tấn công bởi quân hậu nào đã đặt trên bàn cờ hay không. Nếu không, đánh dấu ô đó là đã đặt quân hậu và tiếp tục đệ quy để đặt quân hậu trên hàng tiếp theo.
Nếu không tìm được ô trống nào trên hàng đó để đặt quân hậu, quay trở lại hàng trước đó và thử đặt quân hậu vào ô tiếp theo trên hàng đó.
Nếu đã đặt được n quân hậu trên bàn cờ, lưu trữ kết quả và thoát khỏi đệ quy.
Nếu đã kiểm tra tất cả các ô trên bàn cờ nhưng không tìm được cách đặt quân hậu hợp lệ, quay trở lại và thử cách đặt quân hậu khác.

Thuật toán sử dụng kỹ thuật backtracking để tìm kiếm tất cả các cách đặt quân hậu trên bàn cờ và chỉ trả về kết quả khi đã tìm thấy cách đặt hợp lệ.

Cài đặt thuật toán backtracking với bài toán N-Queen

def is_safe(board, row, col, n):
    # Kiểm tra hàng và cột
    for i in range(n):
        if board[row][i] == 1 or board[i][col] == 1:
            return False
    # Kiểm tra đường chéo chính
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    for i, j in zip(range(row, n, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    # Nếu không có xung đột nào, trả về True
    return True

def solve_n_queens_util(board, col, n, solutions):
    # Nếu tất cả các quân hậu đã được đặt, lưu trữ bàn cờ và thoát khỏi đệ quy
    if col == n:
        solutions.append([row[:] for row in board])
        return
    # Đặt quân hậu trên mỗi hàng của cột hiện tại
    for row in range(n):
        # Nếu ô hiện tại là an toàn, đặt quân hậu và đệ quy tiếp tục trên cột tiếp theo
        if is_safe(board, row, col, n):
            board[row][col] = 1
            solve_n_queens_util(board, col + 1, n, solutions)
            # Quay lại trạng thái trước đó và thử đặt quân hậu trên hàng khác
            board[row][col] = 0

def solve_n_queens(n):
    board = [[0 for _ in range(n)] for _ in range(n)]
    solutions = []
    solve_n_queens_util(board, 0, n, solutions)
    return solutions

Trong đó, hàm is_safe kiểm tra xem một ô trên bàn cờ có thể đặt quân hậu hay không, và solve_n_queens_util là hàm đệ quy sử dụng kỹ thuật backtracking để thử tất cả các cách đặt quân hậu trên bàn cờ. Hàm solve_n_queens tạo một bàn cờ rỗng và lưu trữ tất cả các giải pháp hợp lệ.

Kết luận

Trong bài toán N-Queen, thuật toán quy hoạch động có độ phức tạp thời gian là O(n!), tuy nhiên nó lại không đáp ứng được cho các giá trị n lớn do sử dụng quá nhiều bộ nhớ để lưu trữ kết quả của các trường hợp con. Trong khi đó, thuật toán backtracking có độ phức tạp thời gian cũng là O(n!), tuy nhiên nó chỉ lưu trữ kết quả của một trường hợp con tại một thời điểm và không sử dụng quá nhiều bộ nhớ. Vì vậy, với bài toán N-Queen, thuật toán backtracking sẽ là lựa chọn tốt hơn trong trường hợp n lớn.

Tuy nhiên, cần lưu ý rằng thuật toán backtracking có thể tốn nhiều thời gian hơn thuật toán quy hoạch động nếu không có cách cải tiến phù hợp. Vì vậy, việc lựa chọn thuật toán phù hợp với từng bài toán là rất quan trọng./.

Lập trình Python