代码拉取完成,页面将自动刷新
# https://www.geeksforgeeks.org/solve-crossword-puzzle/
def is_valid(
puzzle: list[list[str]], word: str, row: int, col: int, vertical: bool
) -> bool:
"""
Check if a word can be placed at the given position.
>>> puzzle = [
... ['', '', '', ''],
... ['', '', '', ''],
... ['', '', '', ''],
... ['', '', '', '']
... ]
>>> is_valid(puzzle, 'word', 0, 0, True)
True
>>> puzzle = [
... ['', '', '', ''],
... ['', '', '', ''],
... ['', '', '', ''],
... ['', '', '', '']
... ]
>>> is_valid(puzzle, 'word', 0, 0, False)
True
"""
for i in range(len(word)):
if vertical:
if row + i >= len(puzzle) or puzzle[row + i][col] != "":
return False
elif col + i >= len(puzzle[0]) or puzzle[row][col + i] != "":
return False
return True
def place_word(
puzzle: list[list[str]], word: str, row: int, col: int, vertical: bool
) -> None:
"""
Place a word at the given position.
>>> puzzle = [
... ['', '', '', ''],
... ['', '', '', ''],
... ['', '', '', ''],
... ['', '', '', '']
... ]
>>> place_word(puzzle, 'word', 0, 0, True)
>>> puzzle
[['w', '', '', ''], ['o', '', '', ''], ['r', '', '', ''], ['d', '', '', '']]
"""
for i, char in enumerate(word):
if vertical:
puzzle[row + i][col] = char
else:
puzzle[row][col + i] = char
def remove_word(
puzzle: list[list[str]], word: str, row: int, col: int, vertical: bool
) -> None:
"""
Remove a word from the given position.
>>> puzzle = [
... ['w', '', '', ''],
... ['o', '', '', ''],
... ['r', '', '', ''],
... ['d', '', '', '']
... ]
>>> remove_word(puzzle, 'word', 0, 0, True)
>>> puzzle
[['', '', '', ''], ['', '', '', ''], ['', '', '', ''], ['', '', '', '']]
"""
for i in range(len(word)):
if vertical:
puzzle[row + i][col] = ""
else:
puzzle[row][col + i] = ""
def solve_crossword(puzzle: list[list[str]], words: list[str]) -> bool:
"""
Solve the crossword puzzle using backtracking.
>>> puzzle = [
... ['', '', '', ''],
... ['', '', '', ''],
... ['', '', '', ''],
... ['', '', '', '']
... ]
>>> words = ['word', 'four', 'more', 'last']
>>> solve_crossword(puzzle, words)
True
>>> puzzle = [
... ['', '', '', ''],
... ['', '', '', ''],
... ['', '', '', ''],
... ['', '', '', '']
... ]
>>> words = ['word', 'four', 'more', 'paragraphs']
>>> solve_crossword(puzzle, words)
False
"""
for row in range(len(puzzle)):
for col in range(len(puzzle[0])):
if puzzle[row][col] == "":
for word in words:
for vertical in [True, False]:
if is_valid(puzzle, word, row, col, vertical):
place_word(puzzle, word, row, col, vertical)
words.remove(word)
if solve_crossword(puzzle, words):
return True
words.append(word)
remove_word(puzzle, word, row, col, vertical)
return False
return True
if __name__ == "__main__":
PUZZLE = [[""] * 3 for _ in range(3)]
WORDS = ["cat", "dog", "car"]
if solve_crossword(PUZZLE, WORDS):
print("Solution found:")
for row in PUZZLE:
print(" ".join(row))
else:
print("No solution found:")
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。