Algoritmo per cruciverba con data grid

Question

Prima di scrivere qualcosa per il problema, ho bisogno di farvi sapere:

1. questo problema è il mio dovere (avevo circa 1 settimana per tornare programma di lavoro)
2. Stavo lavorando a questo problema per circa una settimana, ogni giorno, cercando di capire la mia soluzione
3. Non sto chiedendo il programma completo; Ho bisogno un'idea generale sull'algoritmo

Problema:

Dato: un dizionario e di una "griglia", ad esempio:

griglia (X qualsiasi lettera):

X X 
XXXX 
X X 
XXXX 

lista di parole:

ccaa 
baca 
baaa 
bbbb 

Devi trovare l'esempio "soluzione" - è possibile inserire parole dalla lista di parole in una griglia data? Se esiste almeno una soluzione, stampane una (a seconda di quale è corretta). Se no - stampa messaggio, che non vi è alcuna soluzione possibile. Ad esempio dato, c'è una soluzione:

b c 
baca 
b a 
baaa 

E 'difficile per me di scrivere tutto quello che ho già provato (perché l'inglese non è la mia lingua madre e ho anche un sacco di carte con sbagliate idee).

mio ingenuo algoritmo funziona in questo modo:

1. Primo canale ha bisogno di lunghezza appena adeguata, in modo da trovare qualsiasi (prima?) Parola con corretta lunghezza (ho intenzione di usare dato esempio griglia e vocabolario per dimostrare quello credo):

   c X 
   cXXX 
   a X 
   aXXX 
   

2. per prima comune lettera (all'incrocio di 2 word s) trova una qualsiasi (prima) parola, che si adatti alla griglia (quindi, avere la lunghezza corretta e comune lettera sulla posizione corretta). Se non ci sono tali parole, tornare a (1) e prendere un'altra prima parola. Nell'esempio originale non c'è una parola che inizia con "c", quindi torniamo a (1) e selezioniamo le parole successive (questo passaggio si ripete alcune volte finché non abbiamo "bbbb" per la 1a parola). Ora abbiamo:

   b X 
   bXXX 
   b X 
   bXXX 
   

   E stiamo cercando una parola (s), che inizia con "b", per esempio:

   b X 
   baca 
   b X 
   bXXX 
   

3. processo generale: cercare di trovare coppie di parole che misura alla griglia data. Se non ci sono tali parole, tornare al passaggio precedente e utilizzare un'altra combinazione - se non esiste tale - non c'è soluzione.

Tutto sopra è caotico, spero che tu capisca almeno la descrizione del problema.Ho scritto una bozza di un algoritmo, ma non sono sicuro che funzioni e come codificarlo correttamente (nel mio caso: C++). Inoltre, ci sono casi (anche nell'esempio sopra) che dobbiamo trovare una parola che dipenda da su 2 o più altre parole.

Forse non riesco a vedere qualcosa di ovvio, forse sono troppo stupido, forse ... Beh, ho davvero provato a risolvere questo problema. Non conosco abbastanza bene l'inglese per descrivere con precisione cosa penso di questo problema, quindi non posso mettere qui tutti i miei appunti (ho cercato di descrivere un'idea ed è stato difficile). Credi o no, ho passato molte lunghe ore cercando di capire la soluzione e non ho quasi nulla ...

Se puoi descrivere una soluzione, o dare un suggerimento su come risolvere questo problema, apprezzerei molto questo .

Answer 1

Il problema del corssword è NP-Complete, quindi il tuo colpo migliore è la forza bruta: prova tutte le possibilità e fermati quando una possibilità è valida. Restituzione fallita quando hai esaurito tutte le possibili soluzioni.

di riduzione che dimostrano che questo problema è NP-completo può essere trovato in this article sezione 3.3

soluzione forza bruta utilizzando backtracking potrebbe essere: [pseudo code]:

solve(words,grid): 
    if words is empty: 
     if grid.isValudSol(): 
      return grid 
     else: 
      return None 
    for each word in words: 
     possibleSol <- grid.fillFirst(word) 
     ret <- solve(words\{word},possibleSol) 
     if (ret != None): 
      return ret 
    return None 

qui assumiamo fillFirst() è una funzione che riempie il primo spazio che non era già stato riempito [in primo luogo può essere qualsiasi ordinamento coerente degli spazi vuoti, ma dovrebbe essere coerente!], e restituisce un valore booleano che indica se la griglia data è una soluzione valida.

Answer 2

Ho scritto un programma stamattina. Ecco una versione leggermente più efficiente in pseudocodice:

#pseudo-code 
solve (words , grid) : solve (words , grid , None) 

solve (words , grid , filledPositions) : 
    if words is empty : 
     if grid is solved : 
      return grid 
     else : 
      raise (no solution) 
    for (current position) as the first possible word position in grid 
      that is not of filledPositions : 
     # note : a word position must have no letters before the word 
      # 'before the word' means, eg, to the left of a horizontal word 
      # no letters may be placed over a ' ' 
      # no letters may be placed off the grid 
     # note : a location may have two 'positions' : one across , one down 
     for each word in words : 
      make a copy of grid 
      try : 
       fill grid copy, with the current word, at the current position 
      except (cannot fill position) : 
       break 
      try : 
       return solve (words\{word} , grid copy , 
         filledPositions+{current position}) 
      except (no solution) : 
       break 
     raise (no solution) 

Ecco il mio codice per il montaggio di una parola in senso orizzontale nella griglia: http://codepad.org/4UXoLcjR

Qui ci sono alcune cose che ho usato dal STL:

http://www.cplusplus.com/reference/algorithm/remove_copy/

http://www.cplusplus.com/reference/stl/vector/