A fill-in puzzle (sometimes called a fill-it-in) is like a crossword puzzle, except that instead of being given obscure clues telling us which words go where, you are given a list of all the words to place in the puzzle, but not told where they go.
The puzzle consists of a grid of squares, most of which are empty, into which letters or digits are to be written, but some of which are filled in solid, and are not to be written in. You are also given a list of words to place in the puzzle.
You must place each word in the word list exactly once in the puzzle, either left-to-right or top-to-bottom, filling a maximal sequence of empty squares. Also, every maximal sequence of non-solid squares that is more than one square long must have one word from the word list written in it. Many words cross one another, so many of the letters in a horizontal word will also be a letter in a vertical word. For a properly constructed fill-in puzzle, there will be only one way to fill in the words (in some cases, the puzzle is symmetrical around a diagonal axis, in which case there will be two symmetrical solutions).
Here is an example 7 by 7 fill-in puzzle, together with its solution, taken from https://en.wikipedia.org/wiki/Fill-In_(puzzle). In this example, one word is already written into the puzzle, but this is not required.
You will write Prolog code to solve fillin puzzles. Your program should supply a predicate puzzle_solution(Puzzle, WordList) that holds when Puzzle is the representation of a solved fillin puzzle for the given list of words, WordList.
A fillin puzzle will be represented as a list of lists, each of the same length and each representing a single row of the puzzle. Each element in each of these lists is either a: ‘#’, denoting a solid, unfillable square; an underscore (_), representing a fillable square; or a single, lower case letter (e.g., h), denoting a pre-filled square.
For example, suppose you have a 3 by 3 puzzle with the four corners filled in solid and one pre-filled letter. This would be represented by the Puzzle argument:
?- Puzzle = [[‘#’,h,’#’],[_,_,_],[‘#’,_,’#’]]A word list will be represented as a list of lists. Each list is a list of characters, spelling a word. For the above puzzle, the accompanying word list may be:
?- WordList = [[h,a,t], [b,a,g]]You can assume that when your puzzle_solution/2 predicate is called, both arguments will be a proper list of proper lists, and its second argument will be ground. You may assume your code will only be tested with proper puzzles, which have at most one solution. Of course, if the puzzle is not solvable, the predicate should fail, and it should never succeed with a puzzle argument that is not a valid solution. For example, your program would solve the above puzzle as below:
?- Puzzle = [[‘#’,h,’#’],[_,_,_],[‘#’,_,’#’]], WordList = [[h,a,t], [b,a,g]], puzzle_solution(Puzzle, WordList).
Puzzle = [[#, h, #], [b, a, g], [#, t, #]],
WordList = [[h, a, t], [b, a, g]] ;
false.Your puzzle_solution/2 predicate, and all supporting code, should be written in the file proj2.pl. You may also use Prolog library modules supported by SWI Prolog as installed on the server, which is version 7.2.3.