Você não. Uma tabela de banco de dados relacional não é uma estrutura de dados adequada para resolver esse problema com a eficiência necessária.
Em vez disso, você cria uma trie estrutura de dados fora do dicionário (ou, se você for realmente fã, você cria um dawg -- um grafo de palavras acíclicas direcionadas -- que é uma espécie de trie compactado.)
Uma vez que você tenha um teste/dawg, torna-se muito barato testar todo palavra no dicionário contra um determinado rack, porque você pode "cortar" grandes ramos inteiros do dicionário que o rack não pode corresponder.
Vejamos um pequeno exemplo. Suponha que você tenha o dicionário "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS" A partir disso você constrói este trie:(Nós com $ são aqueles marcados como "a palavra pode terminar aqui" .
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ S$ T$ P$ O
| | | |
S$ S$ S$ P$
|
S$
e você tem o rack "OPS" - o que você faz?
Primeiro você diz "posso descer o ramo O?" Sim você pode. Então agora o problema está combinando "PS" com o ramo O. Você pode descer o sub-ramo P? Sim. Tem marcador de fim de palavra? Sim, então OP é um jogo. Agora o problema está combinando "S" com a ramificação OP. Você pode descer o ramo T? Não. Você pode descer o ramo S? Sim. Agora você tem o rack vazio e precisa combiná-lo com o branch OPS. Tem marcador de fim de palavra? Sim! Portanto, o OPS também combina. Agora volte até a raiz.
Você pode descer o ramo P? Sim. Agora o problema é combinar o SO com o ramo P. Desça o ramo PO e combine S -- isso falha. Retroceder à raiz.
E novamente, você vê como isso acontece. Eventualmente, descemos o ramo SOP e encontramos um final de palavra no SOP, então "SOP" corresponde a este rack. Não descemos o ramo ST porque não temos um T.
Tentamos todas as palavras possíveis no dicionário e descobrimos que OP, OPS e SOP correspondem. Mas nunca tivemos que investigar OPTS, POTS, STOP ou STOP porque não tínhamos um T.
Você vê como essa estrutura de dados o torna muito eficiente? Depois de determinar que você não tem as letras no rack para fazer o início de uma palavra, você não precisa investigar nenhuma palavras do dicionário que começam com esse início. Se você tem PO, mas não T, você não precisa investigar POTSHERD ou POTATO ou POTASH ou POTLATCH ou POTABLE; todas essas pesquisas caras e infrutíferas desaparecem muito rapidamente.
Adaptar o sistema para lidar com tiles "selvagens" é bastante simples; se você tiver OPS?, basta executar o algoritmo de pesquisa 26 vezes, em OPSA, OPSB, OPSC ... Deve ser rápido o suficiente para que fazê-lo 26 vezes seja barato (ou fazê-lo 26 x 26 vezes se você tiver dois espaços em branco. )
Este é o algoritmo básico que os programas profissionais de Scrabble AI usam, embora, é claro, eles também tenham que lidar com coisas como posição da placa, gerenciamento de rack e assim por diante, o que complica um pouco os algoritmos. Esta versão simples do algoritmo será rápida o suficiente para gerar todas as palavras possíveis em um rack.
Não esqueça que é claro que você só precisa calcular o trie/dawg uma vez se o dicionário não está mudando ao longo do tempo. Pode ser demorado construir o trie a partir do dicionário, então você pode querer fazer isso uma vez e, em seguida, descobrir uma maneira de armazenar o trie no disco de uma forma que possa reconstruí-lo rapidamente a partir do disco.
Você pode otimizar o uso de memória construindo um DAWG a partir do trie. Observe como há muita repetição porque em inglês, muitas palavras terminam o mesmo, assim como muitas palavras começam o mesmo. O trie faz um ótimo trabalho de compartilhamento de nós no início, mas um péssimo trabalho de compartilhá-los no final. Você pode notar, por exemplo, que o padrão "S$ sem filhos" é extremamente comum, e transformar o trie em:
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ | T$ P$ O
| \ | | |
\ \| / P$
\ |/ |
\ | /
\ | /
\ | /
\| /
|/
|
S$
Salvando uma pilha inteira de nós. E então você pode notar que duas palavras agora terminam em O-P$-S$, e duas palavras terminam em T$-S$, então você pode comprimir ainda mais para:
^root^
/ | \
O P S
| | / \
P$ O \ T
/ \| \ |
| | \|
| | O
| T$ |
\ | P$
\ | /
\| /
| /
|/
S$
E agora temos o DAWG mínimo para este dicionário.
Leitura adicional:
http://dl.acm.org/citation.cfm?id=42420
http://archive.msdn.microsoft.com/dawg1
http://www.gtoal.com/wordgames/scrabble.html
