Write in C only, creating a header file as indicated.

Your task is to create a crossword solver. A crossword is a puzzle where there are multiple blank horizontal and vertical lines with specified lengths in a grid. These blank lines are to be filled by distinct dictionary words. Usually, there are clues given with each word that provide hints as to which word is the correct answer. However, in this lab, you will create a crossword solver that generates all possible solutions by filling the blank spaces without using any clues.

You are provided with a dictionary.txt file that contains a list of words (one in a line), and a crossword.txt file that contains a square crossword board of dimension n x n (n is included in the first line of the crossword.txt file). Your task is to find all combinations of words from dictionary.txt that would complete the crossword correctly, and to fill out the crossword board. This means that all horizontal and vertical blank lines (represented by lines of 0 in the diagram below) are replaced with words that are present in the dictionary; these words contain the same numbers of letters, and match any existing letters in the lines.

8

* * * * 0 * * *

* * * * b 0 0 0

* * * * 0 * * *

* 0 0 0 0 * * *

* * * * 0 * * *

* * * * 0 * * *

* * * * 0 * * *

* * * * * * * * 

The crossword.txt board is formatted like the example above (different from the one provided in lab14.tar), rules:

- 0 indicates room for letters that will be filled to form dictionary words by your program.

- * indicates spots that cannot be filled.

- Some of the lines cross over — this means that you must find words with the same letter in that position

Any number of pre-existing letters may be included in the crossword.txt; the words to be filled must be compatible with these pre-existing letters. The letter b indicates a pre-existing letter in the provided crossword above.

An example of a correct solution to the above crossword.txt is:

* * * * a * * *

* * * * b u r n

* * * * a * * *

* b e l l * * *

* * * * o * * *

* * * * n * * *

* * * * e * * *

* * * * * * * * 

Note that none of the * characters were changed, and both abalone and burn have the pre-existing b in the position shown in the crossword.txt. The lengths of the 0-lines in the crossword.txt and the word lengths in the solved crossword are the same.

You are expected to find all possible solutions to the crossword given the dictionary. Note that some solutions may be only slightly different from the others. For example, two solutions can share all but one word, which is expected. The restriction is that you cannot use the same word more than once in a solution (this is what distinct means).

The required source file ex14q1.c should contain the main() function. You are allowed to have other source files, and if so, name them as ex14q11.c, ex12q12.c, and so on. You are required to compose a header file lab14.h and a makefile. Using the command make, the program called ex14q1 should be compiled without any warning messages or notes. Your program should be run in the following way:

./ex14q1 dictionary.txt crossword.txt k m

where dictionary.txt and crossword.txt are the files described above and supplied to your program, k is the number of solutions to be produced, and m specifies the first m words in the dictionary that can be used in any solutions (that is, if dictionary.txt contains more than m words, then the remaining words should not be used).

Note that we will use different crossword puzzles for marking, and so your program must accept command line arguments and deal with file I/O. Your k crossword solutions should be output as unique solved crossword grids written into separate .txt files in a folder titled Solutions under the current directory, which, if non-existing, your program should create for. The solution files should use the filenames sol1.txt, sol2.txt, ..., solk.txt. When there are less than k unique solutions, your program produces the maximum number possible. Please keep in mind we will set the time limit for your program to run.

Your program should not alter the two files dictionary.txt and crossword.txt (should be read-only in your program), which should be packed into the submit.tar. Feel free to create a dictionary and different puzzles out of them for your programming purpose (so that the testing takes a shorter time).