C Language

The problem is to develop an efficient program that solves crosswords. We assume a crossword defined by its shape and a list of words to be filled. The crossword is of a rectangular shape, with a nice ANSI-graphics border (see below). Inside the border, there are spaces (where individual characters are to be placed) and stars. The stars and the border rectangle delimit runs of spaces, where words of the corresponding length are to be placed. The words to place into the runs are listed later in the input. A word may be placed either in a horizontal run (read from left to the right) or into a vertical run (read from top to bottom). The crossword is limited by 16x16 characters in size (the limit applies to the inside of the border, thus, its up to 18x18 including the border), moreover, there is at most 60 words used in the crossword. The words consist of lowercase English alphabet letters only. The input of the program is the crossword. The list of words is terminated when the EOF condition in the standard input is active. The exact format is shown below. The output of the program is the solution of the input crossword. The program shall distinguish three answers: the input crossword has exactly one solution. The solution is shown in this case. the input crossword cannot be filled with the input words (no solution exists). The program just displays the no solution answer. the input crossword can be filled with the input words and there exists more than one combination to do it. Thus, the crossword is ambiguous. The program shall count all possible unique solutions. Two crossword solutions are considered unique if they differ in at least one character (cell). The program must validate the input data. If there are invalid, or inconsistent data in the input, the program shall detect it, display error message, and terminate. The format of the error message is shown in the sample run below. The following is considered invalid: missing, incomplete, or irregular crossword border, the contents of the crossword is different from spaces and asterisks, the crossword exceeds 16x16 in size, there is more than 60 words in the input, the input word contains characters different from a-z (English lowercase), there is a mismatch in the crossword shape and the words in the input. For instance, let there are 5 runs of length 3 in the crosswords. Then there must be exactly 5 words of length 3 in the input. If there are not, the input is considered invalid. The program is tested in a limited environment. The program is limited in both time and memory space. Both limits are shown in the reference solution testing log. In general, the program does not need much memory. On the other hand, the program may require a lot of CPU time to test all possible permutations, especially if there are many solutions of the crossword. An efficient algorithm and careful implementation is required to pass the time limits. In particular, design the algorithm to avoid unnecessary branches which do not lead to the solution. The problem is a contest problem. It means it is more complicated than the regular problems. The solution requires both programming and algorithmic skills. The problem is intended for gifted students who understand programming and who are bored by the simplicity of the regular problems. The assessment will consist of two parts. There are some points awarded once your program passes the non-contest tests. The remaining points will be awarded at the end of the contest, based on the speed and efficiency of your solution compared to the other submitted solutions. Sample program run:

Sample program run: Enter the crossword: | +--+ +--+ ab a b There is one solution of the crossword: +--+ | ab +--+ Enter the crossword: +-----+ +-----+ a ababa bb CC ba bb ca cb Unique solutions: 2 Enter the crossword: cdi zobxzst tdxic r SC 2ro rgfvaca oikf df r xvf ogish za sh fc hh h bfkh There is one solution of the crossword: +----+ zro*h| ogish bfkh |xvfor za c# sc df tdxic +-----+ Enter the crossword: +-----+ ! * aa aa aa aa aa aa aa aa one solution of the crossword: There +-----+ aa* aa aaaa ---+ Enter the crossword: +-----+ * +-- ab ba aa aa aa aa Unique solutions: 4 : Enter the crossword: ab ba abc abc aa aa bc cb No solution. Enter the crossword: +-----+ 1 1 Invalid input. Enter the crossword: +---- ab ba abc ab aa aa aa aa Invalid input