Làm thế nào để tạo ra lưới thư với nhiều lời

Question

Câu hỏi đặt ra về cơ bản là "làm thế nào để tôi tạo ra một tốt lưới cho các trò chơi 'Boggle' với rất nhiều chữ" nơi tốt được định nghĩa là có rất nhiều lời của 5 hoặc nhiều chữ cái hơn.

Boggle là trò chơi mà bạn xúc xắc với các chữ cái trên chúng, chúng được đặt trong lưới 4x4. Ví dụ:

H S A V 
E N I S 
K R G I 
S O L A 

Từ có thể được thực hiện bằng cách kết nối chữ cái theo chiều ngang, chiều dọc hoặc theo đường chéo. Trong ví dụ tốt ví dụ lưới trên, bạn có thể tạo từ "VANISHERS", "VANISHER", "KNAVISH", "ALIGNERS", "SAVINGS", "SINKERS" và khoảng 271 từ khác tùy thuộc vào từ điển được sử dụng, ví dụ " AS", "tôi", "AIR", "SIN", "lÀ", vv ...

là một xấu dụ lưới này

O V W C 
T K Z O 
Y N J H 
D E I E 

chỉ có ~ 44 từ chỉ 2 dài hơn 4 chữ cái. "TYNED" và "HINKY".

Có rất nhiều similar questions nhưng AFAICT không phải là câu hỏi chính xác này. Điều này rõ ràng là một tham chiếu đến trò chơi "Tranh giành với bạn bè".

Giải pháp đầu tiên, chọn các chữ cái ngẫu nhiên, có vấn đề nếu bạn vô tình chọn tất cả các phụ âm sẽ không có từ nào. Thêm một vài nguyên âm ngẫu nhiên là không đủ để đảm bảo một bộ từ tốt. Bạn chỉ có thể nhận được từ 1 đến 4 chữ cái trong khi một thuật toán tốt sẽ chọn một tập hợp các chữ cái có> 200 từ có nhiều từ> 7 chữ cái.

Tôi đang mở cho bất kỳ thuật toán nào. Rõ ràng tôi có thể viết mã cho các giải pháp bạo lực để tìm mọi lưới có thể và sau đó phân loại chúng bằng lưới với nhiều từ nhất nhưng giải pháp đơn giản đó sẽ mất nhiều thời gian để chạy.

Tôi có thể tưởng tượng nhiều chẩn đoán khác nhau như chọn từ dài (8-16 chữ cái), đặt các chữ cái đó vào lưới ngẫu nhiên nhưng theo cách thực sự vẫn có thể tạo từ và sau đó điền vào dấu cách bên trái. Tôi nghi ngờ điều đó cũng không đủ để đảm bảo một bộ từ tốt mặc dù tôi chưa thử.

Có thể giải pháp yêu cầu tiền xử lý từ điển để biết các phần phổ biến của từ. Ví dụ: tất cả các từ kết thúc bằng "ing" hoặc "ers" hoặc "ght" hoặc "tion" hoặc "land". Hoặc bằng cách nào đó tổ chức chúng thành một biểu đồ của các chữ cái được chia sẻ. Có thể trọng số các bộ chữ nhất định để "ing" hoặc "ers" được chèn thường xuyên.

Ý tưởng?