Crossword puzzle

题目

Given an empty (or almost empty) framework of a crossword puzzle and a set of words. The problem is to place the words into the framework.

Crossword puzzle

The particular crossword puzzle is specified in a text file which first lists the words (one word per line) in an arbitrary order. Then, after an empty line, the crossword framework is defined. In this framework specification, an empty character location is represented by a dot (.). In order to make the solution easier, character locations can also contain predefined character values. The puzzle opposite is defined in the file p7_09a.dat, other examples are p7_09b.dat and p7_09d.dat. There is also an example of a puzzle (p7_09c.dat) which does not have a solution.

Words are strings (character lists) of at least two characters. A horizontal or vertical sequence of character places in the crossword puzzle framework is called a site. Our problem is to find a compatible way of placing words onto sites.

Hints:

  1. The problem is not easy. You will need some time to thoroughly understand it. So, don't give up too early! And remember that the objective is a clean solution, not just a quick-and-dirty hack!
  2. Reading the data file is a tricky problem for which a solution is provided in the file p7_09-readfile.pl. Use the predicate read_lines/2.
  3. For efficiency reasons it is important, at least for larger puzzles, to sort the words and the sites in a particular order. For this part of the problem, the solution of 1.28 may be very helpful.

解题

空白方格框是二维的，但如果把每一组连续的空格（应由一个单词填充的一组空格）作为一个单元，则整个方格框可以表示为一个列表，列表中每个元素都是一组连续空格。

再使用回溯法从后选单词集中取出单词填充每一组连续空格。符合要求（同一个位置填充的字母一定是相同的）的填充组合即为解。

代码实现

def doCrossword(puzzle, solution, words): if len(puzzle) == 0: return [[]] firstPuzzle = puzzle[0] remainPuzzle = puzzle[1:] availableWords = [word for word in words if len(word) == len(firstPuzzle)] return [[(firstPuzzle, word)] + remain for word in availableWords for remain in doCrossword(remainPuzzle, solution + [(firstPuzzle, word)], [e for e in words if e != word]) if isNotViolate(solution + [(firstPuzzle, word)])] def isNotViolate(solution): filledDict = {} for fill in solution: puzzle = fill[0] word = fill[1] for index, pos in enumerate(puzzle): letter = word[index] if pos in filledDict and filledDict[pos] != letter: return False filledDict[pos] = letter return True

使用回溯法列出所有的组合。在列出组合的同时，可以判断排除不符合要求的组合。按照规则，有些单词的字母位置是重叠的。这就要求填充在这些位置的字母是相同的。

def crossword(puzzle, width, height, words): solutions = doCrossword(puzzle, [], words) filledSolutions = [] for solution in solutions: table = [[' ' for h in range(0, width)] for v in range(0, height)] for wordSolution in solution: for index, pos in enumerate(wordSolution[0]): letter = wordSolution[1][index] table[pos//width][pos%width] = letter filledSolutions.append(table) return filledSolutions

最后，将解转换成字迷表格形式，方便人类阅读。

results matching ""

    No results matching ""