logics for crossword

Question

I have a task to create a crossword, a specific one. All the answers are given, but their places are unknown. Program must read a file with board scheme like this :

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

treating each column/row of ones as one possible answer. Is there any way to parse through this file and marking answers without using gazilion if's for each field ? Rest of the logics is as follows :
- on the base of the parsed file crossword is created.
- user selects answers from lists of possibilities
- user clicks on the first block of Answer and if length and letters of selected answer and Answer match - fields are updated

Game board should be stored in 2d array I guess, and each Answer should have indexes of fields in it ?

Answer 1

Crossword puzzle construction is NP-Complete in general (i.e nxn board of 1s and 0s and a given set from which to pick answers). Look at: http://en.wikipedia.org/wiki/List_of_NP-complete_problems which just mentions this. Garey and Johnson's classic book also has a mention of this, saying Exact cover by 3 sets can be reduced to it.

So, you probably will have to use some backtracking/heuristic to fill the grid.

Perhaps this project report of two students from Dartmouth college will be of some help: Crossword Puzzle Generator. It contains some heuristics which you might be able to use.

Of course, you seem to imply there is a human involved, but it is not clear if you can leverage that person to fill the grid and whether your problem is basically some UI programming problem in helping the user out.