逆ボーグル問題を解こうとしています。簡単に言えば、単語のリストが与えられた場合、リスト内の単語と同じ数の単語が隣接する文字のシーケンスで見つかる 4x4 の文字グリッドを作成します (文字は直交方向と斜め方向の両方で隣接しています)。
既知のボードを使用して解決したくありません。これは簡単な TRIE 問題であり、人々の CS プロジェクトのためにここで議論/解決されています。
単語リストの例:
margays, jaguars, cougars, tomcats, margay, jaguar, cougar, pumas, puma, toms
解決：
ATJY
CTSA
OMGS
PUAR
この問題は（私にとって）難しいです。私がこれまでに持っているアルゴリズム:
- 入力の各単語について、それ自体が合法的にボードに表示される可能性のあるすべての方法のリストを作成します。
- これらのボードに単語 #2 を配置するすべての可能な組み合わせを試し、競合のないものを保持します。
- リストの最後まで繰り返します。
- ...
- 利益！！！（/を読んでいる人向け）
明らかに、実装の詳細があります。最初に最も長い単語から始めます。他の単語の部分文字列である単語を無視します。
約 0.4 秒で、7 文字の単語に対して 68,000 の可能なすべてのボードを生成できます。その後、さらに 7 文字のボードを追加すると、68k x 68k のボード x 7 の比較が必要になります。解決時間が氷河になります。
これを行うためのより良い方法があるはずです!!!!
いくつかのコード:
BOARD_SIDE_LENGTH = 4
class Board:
def __init__(self):
pass
def setup(self, word, start_position):
self.word = word
self.indexSequence = [start_position,]
self.letters_left_over = word[1:]
self.overlay = []
# set up template for overlay. When we compare boards, we will add to this if the board fits
for i in range(BOARD_SIDE_LENGTH*BOARD_SIDE_LENGTH):
self.overlay.append('')
self.overlay[start_position] = word[0]
self.overlay_count = 0
@classmethod
def copy(boardClass, board):
newBoard = boardClass()
newBoard.word = board.word
newBoard.indexSequence = board.indexSequence[:]
newBoard.letters_left_over = board.letters_left_over
newBoard.overlay = board.overlay[:]
newBoard.overlay_count = board.overlay_count
return newBoard
# need to check if otherboard will fit into existing board (allowed to use blank spaces!)
# otherBoard will always be just a single word
@classmethod
def testOverlay(self, this_board, otherBoard):
for pos in otherBoard.indexSequence:
this_board_letter = this_board.overlay[pos]
other_board_letter = otherBoard.overlay[pos]
if this_board_letter == '' or other_board_letter == '':
continue
elif this_board_letter == other_board_letter:
continue
else:
return False
return True
@classmethod
def doOverlay(self, this_board, otherBoard):
# otherBoard will always be just a single word
for pos in otherBoard.indexSequence:
this_board.overlay[pos] = otherBoard.overlay[pos]
this_board.overlay_count = this_board.overlay_count + 1
@classmethod
def newFromBoard(boardClass, board, next_position):
newBoard = boardClass()
newBoard.indexSequence = board.indexSequence + [next_position]
newBoard.word = board.word
newBoard.overlay = board.overlay[:]
newBoard.overlay[next_position] = board.letters_left_over[0]
newBoard.letters_left_over = board.letters_left_over[1:]
newBoard.overlay_count = board.overlay_count
return newBoard
def getValidCoordinates(self, board, position):
row = position / 4
column = position % 4
for r in range(row - 1, row + 2):
for c in range(column - 1, column + 2):
if r >= 0 and r < BOARD_SIDE_LENGTH and c >= 0 and c < BOARD_SIDE_LENGTH:
if (r*BOARD_SIDE_LENGTH+c not in board.indexSequence):
yield r, c
class boardgen:
def __init__(self):
self.boards = []
def createAll(self, board):
# get the next letter
if len(board.letters_left_over) == 0:
self.boards.append(board)
return
next_letter = board.letters_left_over[0]
last_position = board.indexSequence[-1]
for row, column in board.getValidCoordinates(board, last_position):
new_board = Board.newFromBoard(board, row*BOARD_SIDE_LENGTH+column)
self.createAll(new_board)
そして、次のように使用します。
words = ['margays', 'jaguars', 'cougars', 'tomcats', 'margay', 'jaguar', 'cougar', 'pumas', 'puma']
words.sort(key=len)
first_word = words.pop()
# generate all boards for the first word
overlaid_boards = []
for i in range(BOARD_SIDE_LENGTH*BOARD_SIDE_LENGTH):
test_board = Board()
test_board.setup(first_word, i)
generator = boardgen()
generator.createAll(test_board)
overlaid_boards += generator.boards