Thuật toán nào phù hợp nhất để giải quyết trò chơi tìm kiếm từ "Boggle" với Python

Question

Tôi đang mã hóa trò chơi tương tự như Boggle nơi người chơi nên tìm các từ bên trong một chuỗi lớn được tạo thành từ các chữ cái ngẫu nhiên.

Ví dụ: có năm mảng có chuỗi bên trong như thế này. Năm hàng, làm từ sáu ký tự mỗi người:

AMSDNS 
MASDOM 
ASDAAS 
DSMMMS 
OAKSDO 

Vì vậy, những người sử dụng của trò chơi nên làm cho các từ sử dụng các chữ cái có sẵn với các hạn chế sau và các quy tắc trong tâm trí:

• của nó không thể lặp lại cùng một chữ cái để tạo một từ. Im nói về lá thư "vật lý", trong trò chơi là một con xúc xắc. Nó không thể sử dụng cùng một con xúc xắc hai lần hoặc nhiều hơn để làm cho từ đó.
• Không thể "nhảy" bất kỳ chữ cái nào để tạo thành từ. Các chữ cái làm từ phải liền kề nhau.
• Người dùng có thể di chuyển theo bất kỳ hướng nào cô ấy muốn mà không có bất kỳ hạn chế nào ngoài hai giới hạn nêu trên. Vì vậy, nó có thể đi đến đỉnh, sau đó phía dưới, sau đó sang bên phải, sau đó lại một lần nữa, và như vậy. Vì vậy, các chuyển động để tìm kiếm các từ có thể bằng cách nào đó thất thường.

Tôi muốn biết cách thực hiện tất cả các chuỗi để tạo từ. Để biết các từ Im sẽ sử dụng một tập tin txt với các từ.

Tôi không biết cách thiết kế một thuật toán có khả năng thực hiện tìm kiếm, đặc biệt suy nghĩ về các chuyển động thất thường cần thiết để tìm các từ và tôn trọng các hạn chế.

Tôi đã triển khai UX, logic để ném xúc xắc và điền vào bảng trò chơi, và tất cả logic cho xúc xắc sáu chữ cái.

Nhưng phần này không dễ dàng và tôi muốn đọc đề xuất của bạn cho thử thách thú vị này.

Im sử dụng Python cho trò chơi này vì ngôn ngữ tôi sử dụng để viết mã và ngôn ngữ tôi thích nhất. Nhưng một lời giải thích hoặc gợi ý của một thuật toán chính nó, nên được tốt đẹp quá, độc lập của ngôn ngữ.

Answer 1

Thuật toán cơ bản rất đơn giản.

• Đối với mỗi ô, hãy làm như sau.
  • Bắt đầu với từ trống, sau đó truy cập vào ô hiện tại.
  • Ghé thăm một ô bằng cách làm theo các bước sau.
    • Thêm chữ của vị trí của ô vào từ ứng cử viên.
    • Từ ứng cử viên có phải là từ đã biết không? Nếu có, hãy thêm nó vào danh sách từ tìm thấy.
    • Từ ứng viên có phải là tiền tố cho bất kỳ từ nào đã biết không?
      • Nếu vậy, đối với mỗi ô liền kề chưa được truy cập để tạo thành từ ứng viên, hãy truy cập vào từ đó (nghĩa là, recurse).
      • Nếu không, hãy quay lại (dừng xem xét các ô mới cho từ ứng cử viên này).

Để làm cho mọi việc diễn ra trôi chảy khi đặt ra câu hỏi "là từ này một tiền tố của bất kỳ từ trong từ điển của tôi", hãy xem xét đại diện cho từ điển của bạn như một trie. Tries cung cấp thời gian tra cứu nhanh cho cả hai từ và tiền tố.

Answer 2

Bạn có thể tìm thấy một Trie hữu ích - đặt tất cả các từ trong từ điển vào một Trie, sau đó tạo một Trie khác từ lưới Boggle, chỉ khi bạn kết hợp từ điển Trie.

I.e. Trie điển:

S->T->A->C->K = stack 
     \->R->K = stark 
     \->T = start 

Lưới: (giản thể)

STARKX 
XXXTXX 
XXXXXX 

Lưới Trie: (chỉ được hiển thị bắt đầu từ S - cũng bắt đầu từ A cho ART, vv)

S->X (no matches in dict Trie, so it stops) 
\->T->X 
    \->A-R->K (match) 
     | |->T (match) 
     | \->X 
     \->C->K (match) 
     \->X  

Bạn có thể hình dung Tries của bạn với GraphViz như this.