Backtracking e pilhas em C

[Karpov1]

Interessado em fazer um dinheirinho extra, certo professor resolveu passar aos alunos o seguinte exercıcio. Ele deseja montar desafios de palavras cruzadas (que revender´a aos jornais). Para isso, ele monta um tabuleiro e uma lista de palavras que ele deseja que esteja na matriz. A tarefa de vocˆes ´e encontrar um jeito de preencher o tabuleiro com as palavras, se existir. Neste caso o professor poder´a vender o desafio aos jornais (e ficar´a rico). 

S˜ao dadas v´arias instˆancias. Cada instˆancia ´e composta pelo n´umero m de linhas e de n colunas do tabuleiro de palavras cruzadas e, a seguir, por m linhas compostas cada uma por n 0’s ou -1’s (o -1 indica uma posi¸c˜ao “preta” e o 0 indica uma posi¸c˜ao branca. Depois do tabuleiro ´e dado o n´umero p de palavras, que seguem nas p linhas seguintes. A entrada termina com uma matriz 0 × 0.

Exemplo: 5 4

-1 0 0 0

0 0 0 0

0 0 -1 0

0 0 0 0

0 -1 0 0

10

ad antas carn casa do lado lua os soda ur

3 3 -1 0

0 0 0 0

0 -1 0 5

ab au bug la lua

0 0

 

Você deve resolver o seguinte problema:

ab, adido, ai, al, am, atice, banc, bo, boca, cao, dam, dm, enaltecedor, es, et, indo, it, itamaraca,
mito, mo, moa, ms, mud, naus, neonato, permitir, remessa, res, robustecida, toast, trem, tri

 

[Karpov1]

Sim. Eu quero um algoritmo em C que a partir de uma lista de palavras faça uma palavra cruzada, ou seja, posicionar as palavras na matriz. Eu até achei esse link: http://www.codeproject.com/Articles/530853/Creating-a-crossword-generator

 

Ele parece que resolve boa parte da questão, mas eu não entendi e não sei terminar, você saberia terminar?

[Karpov1]

Hm..o tabuleiro já está dado, é o que eu postei no meu primeiro post, e eu tenho que por as palavras que estão la no tabuleiro. Isso é gerar palavra cruzada?