logiche di cruciverba

Question

Ho un compito di creare un cruciverba, uno specifico. Tutte le risposte sono date, ma i loro posti sono sconosciuti. Programma deve leggere un file con lo schema di bordo in questo modo:

0 1 0 0 0 0 0 0 1 0 0
0 1 0 1 1 1 1 1 1 1 1
0 1 0 1 0 0 1 0 1 0 1
0 S 1 1 0 1 1 1 1 0 1
0 1 0 0 1 0 1 0 1 0 0
1 1 1 1 1 1 1 S 1 1 0
0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0

trattando ogni colonna / fila di quelli come una possibile risposta. C'è un modo per analizzare attraverso questo file e le risposte di marcatura senza utilizzare gazilion se di per ogni campo? Resto delle logiche è il seguente:
- sulla base del cruciverba file analizzato viene creato
. - risposte utente sceglie da elenchi di possibilità
- utente fa clic sul primo blocco di risposta e se la lunghezza e le lettere di risposta selezionata and match risposta - campi vengono aggiornati

scheda di gioco deve essere conservato in array 2D immagino, e ogni risposta dovrebbe avere indici di campi in esso?

Answer 1

Crossword costruzione puzzle è NP-completo in generale (cioè nxn consiglio di 1 e 0 e un dato insieme da cui scegliere le risposte). Guardate: http://en.wikipedia.org/wiki/List_of_NP-complete_problems che ha appena menziona questo. Garey e Johnson del classico libro ha anche una menzione di questo, dicendo copertura esatta per 3 set può essere ridotto ad esso.

Quindi, probabilmente dovrà utilizzare alcuni backtracking / euristica per riempire la griglia.

Forse questa relazione di progetto di due studenti al Dartmouth College sarà di qualche aiuto: cruciverba Generator . Esso contiene alcune euristiche che si potrebbe essere in grado di utilizzare.

Naturalmente, ti sembra implicare v'è coinvolto un essere umano, ma non è chiaro se è possibile sfruttare questa persona per riempire la griglia e se il vostro problema è fondamentalmente qualche problema di programmazione interfaccia utente per aiutare l'utente fuori.