단어 검색 알고리즘

Question

"brute force"방법보다 나은 접근 방법을 찾으려고합니다. 그러나 다소 손실이 있습니다. 내가 사용할 수있는 모든 단어 조합을 찾기 위해 시도하고 미리 선택된 문자의 유한 수를 감안할 때

및 (크로스 워드 중복 등) 해치 :

다음은 간단한 경우입니다. (단어는 사전 데이터베이스로부터 검색된다.)

예 : 문자 주어

:
A, C, R, E, T, U, P, L, m,
얼마나 조합 O를 단어가 다음 십자말 풀이에 적합 할 수 있습니까?

_ 
_ _ _ _ 
    _ 
    _ 
    _ _ _ 

한 예 : 검색 시간이 증가 극적으로 낱말 해치 각 문자 또는 추가와 함께 물론

c 
t r e e 
    e 
    e 
    p o t 

. 더 나은 검색 방법에 대한 제안이 있으십니까?

Answer 1

오픈 소스 arccc을 확인하십시오.이 소스는 십자말 표 형식으로 채우고 constraint satisfaction problem으로 처리합니다. 학습 과제로 직접하고 싶다면 CSP를 읽는 것이 좋은 출발점이되어야합니다.

알파벳을 제한하는 데는 소스 사전에서 사전 처리 단계로 수행하는 것이 가장 좋습니다.