Thuật toán tìm kiếm từ

Question

Tôi đang cố gắng tìm ra cách tiếp cận tốt hơn so với phương pháp "sức mạnh vũ phu", nhưng ở phần nào mất mát.

Đây là một trường hợp đơn giản:

Cho một số hữu hạn các chữ trước lựa chọn, và một nở (như một sự chồng chéo ô chữ) Tôi đang cố gắng để tìm thấy tất cả các tổ hợp chữ cái có thể được sử dụng. (Từ vựng được lấy ra từ một cơ sở dữ liệu từ điển.)

Ví dụ:

Với các chữ cái:
a, c, r, e, t, u, p, l, m, o
bao nhiêu kết hợp các từ có thể phù hợp với câu đố ô chữ sau đây?

_ 
_ _ _ _ 
    _ 
    _ 
    _ _ _ 

Một ví dụ:

c 
t r e e 
    e 
    e 
    p o t 

Tất nhiên thời gian tìm kiếm tăng đáng kể với mỗi chữ cái, bổ sung các hatch ô chữ. Bất kỳ đề xuất cho một cách tốt hơn để tìm kiếm?

Answer 1

Kiểm tra mã nguồn mở arccc, điền vào lưới ô chữ bằng cách coi chúng là constraint satisfaction problem. Nếu bạn muốn làm điều này cho mình như là một bài tập học tập, đọc lên trên CSP nên là một điểm khởi đầu tốt.

Để giới hạn bảng chữ cái, tốt nhất nên thực hiện như là bước tiền xử lý trên từ điển nguồn.