Người giải câu đố Python

Tôi đã nhận được câu đố này như một món quà vào dịp Giáng sinh, và tôi đã ngây thơ ném tất cả các mảnh ghép ra khỏi bảng ngay khi mở nó ra. Một người thông minh hơn có lẽ đã chụp một bức ảnh về giải pháp ban đầu, đề phòng. Tôi sẽ vô cùng hối tiếc về sự sơ suất này trong những giờ sau đó, vì tôi đã nhiều lần cố gắng và thất bại trong việc đặt tất cả các mảnh trở lại vị trí của chúng. Tôi đã đến rất gần nhiều lần, đặt 12 trong số 13 mảnh trước khi nhận ra rằng mảnh cuối cùng sẽ không thể khớp được

Ngay sau tất cả những điều này, tôi đã tranh thủ sự giúp đỡ của bạn bè và gia đình, nhưng ngay cả những nỗ lực kết hợp của họ cũng không phù hợp với câu đố trông có vẻ đơn giản. Cuối cùng, một người bạn đã tìm thấy một cấu hình hoạt động, nhưng chiến thắng cảm thấy trống rỗng. Câu đố này đã đánh bại nhiều người trong chúng ta, lãng phí thời gian của mọi người. Bị thúc đẩy bởi sự tò mò và thất vọng, tôi quyết định xây dựng một thuật toán để phá vỡ hoàn toàn câu đố này. Linh tính mách bảo tôi rằng câu đố khó vì có lẽ chỉ có một cách giải duy nhất. Tôi không thể loại trừ khả năng có hàng chục hoặc hàng trăm giải pháp, nhưng dường như không thể. Với một thuật toán, tôi có thể chứng minh nó bằng cách này hay cách khác

Câu đố

Chỉ sau khi tôi hoàn thành thuật toán của mình và bắt đầu nghiên cứu bài viết này, tôi mới biết trò chơi mà tôi nhận được là phiên bản của một thứ gọi là “câu đố pentomino. ” Rõ ràng, pentomino là tên của một hình được tạo thành từ năm hình vuông có kích thước bằng nhau

Quy ước đặt tên cho 12 ngũ giác. Bởi R. Một. Nonenmacher — Công việc riêng, CC BY-SA 4. 0, https. // chung. wikimedia. tổ chức/w/chỉ mục. php?curid=4412149

Trong một trò chơi xếp hình ngũ giác điển hình, các quân cờ duy nhất trên bàn cờ là các quân ngũ giác. Câu đố của chúng tôi hơi độc đáo vì nó bao gồm thêm một mảnh hình vuông 2x2. Để tuân theo quy ước đặt tên của hình trên, từ bây giờ tôi sẽ gọi tác phẩm này là “O quadromino. ”

Các mảnh khác nhau thêm mức độ phức tạp khác nhau cho câu đố. Ví dụ, O quadromino chỉ có một hướng. Bất kể chúng ta xoay hoặc lật nó như thế nào, biên dạng thực tế của hình vẫn giữ nguyên. Ở đầu kia của quang phổ, F pentomino có tám hướng có thể

Tất cả các vị trí tiềm năng cho F pentomino

Để tìm mọi giải pháp khả thi cho câu đố, chúng ta cần xem xét mọi khả năng lật và xoay có thể có cho mọi mảnh ghép. Để đại diện cho các trạng thái phức tạp này, chúng tôi sẽ chuyển đổi đại diện bảng của chúng tôi từ thế giới vật chất sang kỹ thuật số

hội đồng quản trị

Tôi đã chọn một danh sách các danh sách làm cấu trúc dữ liệu cho cả bàn cờ và quân cờ. Bàn cờ được khởi tạo với các giá trị 0 để tượng trưng cho các ô trống. Mỗi quân cờ có giá trị từ 1–13, giúp bạn có thể phân biệt giữa chúng khi chúng được đặt trên bàn cờ. Tôi cũng đã viết hai hàm để thao tác hướng của các mảnh. một để xoay các mảng quân cờ 90 độ theo chiều kim đồng hồ và một để phản chiếu quân cờ qua trục Y của nó. Kết hợp với nhau, chúng có thể tạo mọi vị trí có thể cho một quân cờ nhất định

board = [[0, 0, 0, 0, 0, 0, 0, 0] for _ in range[8]]

pieces = [

    [[1, 1],
     [1, 1]],

    [[2, 0, 0],
     [2, 0, 0],
     [2, 2, 2]],

    [[0, 3, 0],
     [3, 3, 3],
     [0, 3, 0]],

    [[4, 4, 4, 4, 4]],
    ...
    ]

def rotate_piece[piece]:
    return [list[row[::-1]] for row in zip[*piece]]

def reflect_piece[piece]:
    return [row[::-1] for row in piece]

Bây giờ chúng ta cần một phương pháp để đặt các quân cờ lên bàn cờ mà không vi phạm bất kỳ luật chơi nào. Trước khi đặt quân cờ xuống, chúng ta cần kiểm tra hai tiêu chí

1. Mảnh sẽ không treo ra khỏi cạnh của bảng
2. Quân cờ sẽ không trùng với bất kỳ quân cờ nào đã có trên bàn cờ

Miễn là cả hai quy tắc được đáp ứng, việc đặt mảnh là hợp pháp

def add_piece[board, piece, start_row, start_col]:
    piece_width = len[piece[0]]
    piece_height = len[piece]
    legal_move = True

# check if piece is hanging off the edge of the board
    if [start_row + piece_height > len[board]] or 
       [start_col + piece_width > len[board[0]]]:
        legal_move = False
        return board, legal_move

changed_squares = []
    for i, row in enumerate[piece]:
        for j, val in enumerate[row]:
            # only add filled spaces, never take away
            if val:
                # don't overwrite existing pieces on the board
                if board[start_row + i][start_col + j]:
                    legal_move = False
                    return board, legal_move
                else:
                    changed_squares.append[[start_row + i, start_col + j, val]]

    new_board = [[val for val in row] for row in board]
    for changed_row, changed_col, val in changed_squares:
        new_board[changed_row][changed_col] = val

return new_board, legal_move

Tại thời điểm này, chúng ta có một bảng trò chơi hoạt động chính xác như bảng ngoài đời thực. Chỉ bây giờ, thay vì tôi phải kiểm tra hàng chục kết hợp mỗi phút, chúng tôi có thể viết phần mềm để tạo ra hàng nghìn kết hợp mỗi giây. Để biến điều này thành hiện thực, chúng ta cần một thuật toán có khả năng tạo ra tất cả các trạng thái bảng có thể đó

thuật toán

Tôi quyết định thực hiện một phương pháp thử và đúng được gọi là quay lui. Ý tưởng cơ bản của phương pháp này là đưa ra lựa chọn, sau đó hủy bỏ lựa chọn đó sau nếu nó không chính xác. Đối với câu đố ngũ giác, chúng tôi muốn đặt các quân cờ xuống bàn cờ cho đến khi không thể đặt thêm quân cờ nào nữa. Khi điều này xảy ra, đó là bởi vì chúng ta đã hết quân cờ và giải được câu đố hoặc [rất có thể] đã đặt các quân cờ vào một cấu hình không vừa với bàn cờ. Chúng ta phải bắt đầu hoàn tác một số lựa chọn trước đó khi chúng ta đi vào ngõ cụt này

Đầu tiên, chúng tôi rút quân được đặt gần đây nhất ra khỏi bàn cờ. Nếu nó có thể khớp theo cách chưa được thử, chúng tôi đặt quân cờ trở lại bảng theo hướng mới này và tiếp tục đặt thêm quân cờ. Nếu tất cả các hướng của quân cờ đã hết, chúng tôi quay lại lần nữa và thử điều tương tự với quân cờ được đặt gần đây nhất tiếp theo. Lặp lại quy trình này sẽ tạo ra mọi trạng thái bàn cờ có thể có trong câu đố pentomino

def solve_board[board, pieces]:
    # piece_positions contains all possible orientations for a given piece
    piece_positions = pieces[0]
    for position in piece_positions:
        # find every place a piece can fit into the board
        legal_squares = get_legal_squares[board, position]
        for row, col in legal_squares:
            # place the piece, repeat with new board
            new_board, _ = add_piece[board, position, row, col]
            solve_board[new_board, pieces[1:]]

Vâng, đó là khá đơn giản. Bây giờ chúng ta có thể ngồi lại và để thuật toán thực hiện, phải không? . Có hàng tỷ cấu hình bảng khả thi và phần lớn áp đảo thậm chí không gần với giải pháp. Nếu chúng ta hình dung những gì thuật toán đang làm ngay bây giờ, thì dễ dàng nhận thấy rằng nó đang lãng phí phần lớn thời gian vào các cấu hình bảng bất khả thi. Ví dụ: khi X pentomino được đặt ở góc trên cùng bên trái của bàn cờ, bất kỳ công việc nào mà thuật toán thực hiện đều vô ích cho đến khi X pentomino được di chuyển vì không thể lấp đầy ô vuông trên cùng bên trái

Một triển khai ngây thơ của quay lui đệ quy. Rất tiếc. tối ưu hóa

Hóa ra giải pháp cho vấn đề này nằm ngay từ vấn đề Leetcode. Trong trường hợp của chúng ta, chúng ta có thể coi các ô trống được bao quanh bởi các quân cờ là “đảo. ” Chúng tôi muốn ngăn thuật toán tạo ra các bảng trong đó một pentomino không thể vừa với một hòn đảo

Để đếm kích thước của từng hòn đảo, chúng tôi sẽ sử dụng tìm kiếm theo chiều sâu. đệ quy hơn. Thuật toán “bộ đếm đảo” này quét qua bàn cờ cho đến khi nó tìm thấy một hình vuông có giá trị bằng 0. Nó đánh dấu hình vuông đó là đã truy cập, tăng một biến đếm và tự gọi đệ quy chính nó trên tất cả các hàng xóm của hình vuông. Hòn đảo đã được khám phá đầy đủ khi thuật toán hết ô vuông hàng xóm có giá trị bằng 0 để kiểm tra. Bộ đếm hiện chứa kích thước của hòn đảo. Nếu hòn đảo có ít hơn bốn ô vuông, cấu hình không thể giải được, vì vậy chúng tôi ném cấu hình bảng đó đi

Chúng ta phải cho phép các hòn đảo có bốn hình vuông vì O quadromino, là mảnh duy nhất thực sự có thể vừa với đó. Chúng ta có thể khắc phục hạn chế này bằng cách luôn đặt O quadromino trước. Vì nó luôn ở trên bảng nên chúng ta sẽ không bao giờ phải lo lắng về việc tìm chỗ cho nó. Bây giờ chúng ta có thể chuyển thuật toán sang chỉ cho phép đảo nếu chúng là bội số của năm

def legal_islands[board]:
    board = [[elem for elem in row] for row in board]
    board_height = len[board]
    board_width = len[board[0]]
    island_size = 0

# depth first search on island squares
    def island_dfs[row, col]:
        # break if square is out of bounds or nonzero
        if row < 0 or col < 0 or 
           row >= board_height or col >= board_width or 
           board[row][col] != 0:
            return
        island_cells += 1
        board[row][col] = "#"
        island_dfs[row - 1, col]
        island_dfs[row + 1, col]
        island_dfs[row, col - 1]
        island_dfs[row, col + 1]

for row in range[board_height]:
        for col in range[board_width]:
            if board[row][col] == 0:
                island_dfs[row, col]
                # only allow islands if they're multiples of five
                if len[island_cells] % 5 != 0:
                    return False
                island_cells = []
    return True

Việc tính toán bổ sung có thể làm chậm thuật toán tổng thể xuống một chút, nhưng nó bù đắp nhiều hơn cho số lượng đường dẫn không chính xác không còn được khám phá

Tối ưu hóa quay lui trong hành động. Các giải pháp

Tôi nhấn run trên bộ giải của mình và dán mắt vào đầu ra của thiết bị đầu cuối. Không có gì xảy ra trong khoảng 30 giây, rồi đột nhiên, nó phun ra ba giải pháp duy nhất cùng một lúc. Năm phút sau, nó lên đến 34. Trực giác của tôi đã hoàn toàn tan vỡ. Rõ ràng là số lượng giải pháp ít nhất là hàng nghìn, nếu không muốn nói là nhiều hơn. Tôi cảm thấy muốn cười khi máy tính ngày càng tìm ra nhiều lời giải cho một câu đố mà tôi thậm chí không giải được một lần

Tôi đã tiến xa đến mức này và chỉ cần biết chính xác có bao nhiêu giải pháp hiện có. May mắn thay, tôi có quyền truy cập vào một máy chủ không sử dụng, nơi tôi có thể chạy mô phỏng giải đố. Ngay cả khi đa xử lý được triển khai, phải mất ít nhất vài ngày để chạy xong, điều này thật đáng tiếc. Nhưng cuối cùng, tôi đã có câu trả lời của mình. Có 129.168 lời giải cho câu đố ngũ giác

Một vài lời giải ngẫu nhiên cho câu đố ngũ giác Nhiều Tối ưu hơn, Ít Giải pháp hơn

Một ngày sau, tôi nhận ra rằng chắc chắn không có 129.168 lời giải cho câu đố này. Nhiều bảng đã giải chỉ là phép quay hoặc phản chiếu của các bảng đã giải khác, điều đó có nghĩa là chúng không thực sự độc đáo. Để loại bỏ các bản sao, chúng ta cần "bình thường hóa" từng bảng để hoàn tác tất cả các phép biến đổi đó

Đây là tất cả các phiên bản của cùng một bảng, chỉ xoay 90˚

Giải pháp của tôi là chọn một hướng tiêu chuẩn cho F pentomino và xoay/phản chiếu mọi bảng cho đến khi F pentomino ở hướng tiêu chuẩn đó. Điều này giúp loại bỏ bất kỳ sự khác biệt nào giữa các bảng do xoay hoặc phản xạ và cho phép chúng tôi so sánh chúng trực tiếp

Sau khi loại bỏ tất cả các bản sao theo cách này, tôi còn lại 16.146 giải pháp thực sự độc đáo. Đáng chú ý, đây mới bằng đúng 1/8 lượng dung dịch ban đầu. Tôi đã có linh cảm rằng đây sẽ là trường hợp, nhưng thật tuyệt khi chứng minh được điều đó

Cách tiếp cận này khiến tôi nhận ra một tối ưu hóa cuối cùng để tạo ra các giải pháp. Chúng tôi có thể hạn chế chỉ tạo các bảng có F pentomino theo hướng tiêu chuẩn của nó. Điều này ngăn chúng tôi tạo các bảng trùng lặp và thời gian chạy của thuật toán chỉ còn 1/8 so với thời gian tốt nhất trước đó

Suy nghĩ cuối cùng

Tôi chắc chắn rằng có rất nhiều tối ưu hóa bổ sung cho mã của tôi. Ví dụ: thuật toán tìm đảo có thể được sửa đổi để không cho phép các đảo có hình quân cờ đã có trên bàn cờ. Tôi thậm chí có thể thử giải câu đố theo cách mà Donald Knuth đã làm. Đây không phải là lần đầu tiên tôi triển khai một trong những thuật toán của anh ấy. Tuy nhiên, hiện tại, tôi hài lòng với những gì mình có

Nếu bạn thích chơi câu đố pentomino hoặc chỉ loay hoay với mã, thì phần triển khai của tôi có sẵn miễn phí trên GitHub. Cảm ơn vì đã đọc

Làm cách nào để tạo một trò chơi giải đố bằng Python?

Có ứng dụng nào giúp giải câu đố không?

Cách nhanh nhất để giải một câu đố là gì?

Sự xuất hiện của mã có đáng không?