我正试图写一个程序来检查一个特定的单词是否可以使用给定的“boggle board”生成。挑战的全部细节如下:Boggle Word Checker
基本上,程序应该在电路板上找到单词的第一个字母,然后检查电路板上与其相邻的任何字母是否与单词的下一个字母匹配
这就是我到目前为止得到的(我知道不是很漂亮):
def pos(board, x, y):
# function to get value from a grid, but return None if not on grid,to
# prevent wraparound
if x >= 0 and y >= 0 and x < len(board[0]) and y < len(board):
return board[y][x]
else:
return None
def surrounds(board, x, y):
# make a dictionary which to store the positions and values of adjacent
# letters on board, given a single postision as input
return {
(x-1,y-1) : pos(board,x-1,y-1), #aboveLeft
(x,y-1) : pos(board,x,y-1), #aboveMiddle etc...
(x+1,y-1) : pos(board,x+1,y-1),
(x-1,y) : pos(board,x-1,y),
(x+1,y) : pos(board,x+1,y),
(x-1,y+1) : pos(board,x-1,y+1),
(x,y+1) : pos(board,x,y+1),
(x+1,y+1) : pos(board,x+1,y+1)
}
def find_word(board, word):
# initialise
listOfCoords = []
# find all occurrences of the first letter, and store their board
# position in a list
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0]:
listOfCoords.append([j,i])
print('list of ' + word[0] + 's on board:')
print(listOfCoords)
print()
# if word is only 1 letter long then we can return True at this point
if listOfCoords and len(word) == 1:
return True
# otherwise we move on to look for the second letter
return findnext(board,word,listOfCoords)
def findnext(board, word, mylist):
for x, y in mylist:
print("Current coords: {},{}\n".format(x,y))
surroundings = surrounds(board,x,y)
listFounds = []
for k, v in surroundings.items():
if v == word[1]:
print("{} found at {}".format(v,k))
print()
if len(word) == 2:
print()
return True
listFounds.append(k)
if findnext(board, word[1:], listFounds) == True:
return True
return False
testBoard = [
["E","A","R","A"],
["N","L","E","C"],
["I","A","I","S"],
["B","Y","O","R"]
]
print(find_word(testBoard, "CEREAL"))
然而,我遇到了一个问题,因为挑战规定董事会上的任何职位都不能被多次使用。因此,在上面的示例中,程序应该为“谷物”返回False,而我的程序返回True
我在想,解决这个问题的一种方法是使用一个集合,一旦找到下一个字母,它就会将坐标添加到集合中。然而,我有点不知道我需要在哪里创建空集,以及它如何与所有循环和递归一起工作
例如,假设我们在另一块板上寻找“谷物”,它有两个E与C相邻。假设第一条路径只通向CER,另一条通向谷物。如果我们先沿着CER路径走,它的位置将被添加到集合中,在它沿着谷物路径走之前,我需要以某种方式再次移除它们
我正在努力思考如何在我的程序中实现这一点
你需要有一个与电路板大小相同的布尔数组,所有这些都设置为False。当您使用字母并递归调用函数时,请将所用字母的单元格设置为True。从递归调用返回时,将单元格值设置回False。您应该只使用带有假值的字母,表示以前未使用过这些字母
或者,您可以在将已使用的字母保留在临时变量中后,将其替换为None,然后执行递归调用。从递归调用返回时,从temp变量返回单元格的值
步骤:
这个解决方案也适用于
NxM
板相关问题 更多 >
编程相关推荐