pour mots croisés logiques

Question

j'ai une tâche de créer des mots croisés, un spécifique. Toutes les réponses sont données, mais leurs places sont inconnues. Le programme doit lire un fichier avec le schéma de la carte comme ceci:

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 

de traiter chaque colonne/rangée de uns comme une réponse possible. Existe-t-il un moyen d'analyser ce fichier et de marquer les réponses sans utiliser gazilion si c'est pour chaque champ? Reste la logique est la suivante:
- sur la base des mots croisés de fichier créé parser est.
- utilisateur sélectionne des réponses à partir des listes de possibilités
- l'utilisateur clique sur le premier bloc de réponse et si la longueur et les lettres de réponse sélectionnée et réponses match - les champs sont mis à jour

carte de jeu doit être stocké dans le tableau 2d je suppose , et chaque réponse devrait avoir des index de champs dedans?

Answer 1

La construction d'un jeu de mots croisés est NP-Complète en général (c'est-à-dire un tableau nxn de 1 et de 0 et un ensemble donné à partir duquel choisir les réponses). Regardez: http://en.wikipedia.org/wiki/List_of_NP-complete_problems qui mentionne juste cela. Garey et Johnson livre classique a aussi une mention, en disant couverture exacte de 3 ensembles peut être réduit à elle.

Ainsi, vous devrez probablement utiliser certains retours en arrière/heuristique pour remplir la grille.

Peut-être que ce rapport de projet de deux étudiants de l'université de Dartmouth sera de l'aide: Crossword Puzzle Generator. Il contient des heuristiques que vous pourriez utiliser. Bien sûr, vous semblez impliquer qu'il y a un humain impliqué, mais il n'est pas clair si vous pouvez tirer parti de cette personne pour remplir la grille et si votre problème est fondamentalement un problème de programmation de l'interface utilisateur pour aider l'utilisateur.