Boggle游戏n长度合法单词路径查找函数返回不全问题修复

问题描述 #

• 需求：实现Boggle拼字游戏功能函数，入参为二维字母棋盘、合法单词集合、整数n，返回棋盘上所有长度为n、路径拼接结果属于合法单词的坐标移动轨迹
• 异常表现：指定测试用例仅返回1条符合要求的路径，预期应返回3条

测试用例输入 #

board1 = [['Q', 'O', 'Q', 'Q'],
          ['D', 'O', 'G', 'Q'],
          ['Q', 'O', 'Q', 'Q'],
          ['Q', 'Q', 'Q', 'Q']]
word_dict = {'DOG': True}
n = 3
board = Board(board1)
length_n_paths(3, board, word_dict)

当前错误输出 #

[((1, 0), (1, 1), (1, 2))]

预期正确输出 #

[[(1, 0), (0, 1), (1, 2)], [(1, 0), (1, 1), (1, 2)], [(1, 0), (2, 1), (1, 2)]]

原实现思路 #

原方案先通过组合方法生成所有长度为n的字母组合，逐对校验相邻坐标是否符合8邻接移动规则，最后校验坐标序列拼接的字符串是否属于合法单词，符合则加入结果集返回。

原实现代码 #

direct_lst=['Up','Down','Right','Left','Up_right','Up_left','Down_right','Down_left']

class Board:
    def __init__(self, board):
        self.board = board

    def get_board_coordinate(self):
        cord_lst = []
        row = len(self.board)
        col = len(self.board[0])
        for i in range(row):
            for j in range(col):
                cord_lst.append((i, j))
        return cord_lst

    def possible_directions(self, coordinate, next_coordinate):
        y, x = coordinate
        directions_funcs = {
            # 方向与坐标偏移映射字典
            'Up': (y - 1, x),
            'Down': (y + 1, x),
            'Right': (y, x + 1),
            'Left': (y, x - 1),
            'Up_right': (y - 1, x + 1),
            'Up_left': (y - 1, x - 1),
            'Down_right': (y + 1, x + 1),
            'Down_left': (y + 1, x + 1)
        }
        it_ok = False
        for direction in direct_lst:
            if directions_funcs[direction] == next_coordinate:
                it_ok = True
        return it_ok

def is_valid_path(board, path, words):
    word = board.board[path[0][0]][path[0][1]]
    board_coordinates = board.get_board_coordinate()
    for cord in range(len(path)-1):
        if path[cord] in board_coordinates and path[cord+1] in board_coordinates:
            if not board.possible_directions(path[cord], path[cord + 1]):
                return None
            else:
                word += board.board[path[cord + 1][0]][path[cord + 1][1]]
        else:
            return None
    if word in set(words):
        return word
import itertools

def create_dict(board, n):
    new_dict = dict()
    row = len(board.board)
    col = len(board.board[0])
    for i in range(row):
        for j in range(col):
            new_dict[(i, j)] = board.board[i][j]
        result_list = list(map(list, itertools.combinations(new_dict.items(), n)))
    return result_list

def coordinates_lst_and_str_lst(board, n):
    combine = create_dict(board, n)
    all_cord_dic = dict()
    for lst in combine:
        is_it_ok = True
        cord_lst = []
        str_l = ""
        for i in range(n):
            cord_lst.append(lst[i][0])
            str_l += lst[i][1]
            try:
                if not board.possible_directions(lst[i][0], lst[i + 1][0]):
                    is_it_ok = False
                    break
            except IndexError:
                break
        if is_it_ok:
            all_cord_dic[tuple(cord_lst)] = str_l
            all_cord_dic[tuple(cord_lst)[::-1]] = str_l[::-1]
    return all_cord_dic

def length_n_paths(n, board, words):
    possible_words = coordinates_lst_and_str_lst(board, n)
    my_dict = {key:val for key, val in possible_words.items() if val in words}
    return list(my_dict.keys())

根因定位 #

代码存在3个核心问题：

1. 8邻接方向映射写错：Down_left方向的偏移量写成了和Down_right一致的(y+1, x+1)，正确左下偏移应为(y+1, x-1)，直接漏判左下方向的合法移动。
2. 组合生成逻辑完全错误：itertools.combinations生成的是无序不重复坐标集合，丢失路径顺序信息，相同坐标集的不同排列顺序不会被覆盖，比如三点(1,0)、(0,1)、(1,2)的组合默认顺序不满足路径相邻校验规则，直接被过滤。
3. 路径校验逻辑漏洞：用try...except IndexError跳过边界判断，会把长度不足的非法路径误判为合法；手动添加逆序路径的逻辑多余，还会引入反向错误路径。

修复方案 #

放弃全量组合+校验的低效率思路，改用深度优先搜索(DFS)从每个格子出发遍历所有长度为n的合法路径，边遍历边校验，不会漏路径且执行效率更高。

修复后完整代码 #

# 直接存储8方向偏移量，减少字典查询开销
direct_lst = [(-1,0), (1,0), (0,1), (0,-1), (-1,1), (-1,-1), (1,1), (1,-1)]

class Board:
    def __init__(self, board):
        self.board = board
        self.rows = len(board)
        self.cols = len(board[0]) if self.rows > 0 else 0

    def is_in_bound(self, y, x):
        """校验坐标是否在棋盘范围内"""
        return 0 <= y < self.rows and 0 <= x < self.cols

def length_n_paths(n, board, words):
    result = []
    word_set = set(words.keys())

    def dfs(y, x, current_path, current_str):
        # 路径长度达到n时校验是否为合法词
        if len(current_path) == n:
            if current_str in word_set:
                result.append(tuple(current_path.copy()))
            return
        # 遍历8个邻接方向
        for dy, dx in direct_lst:
            ny, nx = y + dy, x + dx
            # 校验坐标合法，且未在当前路径中重复经过（Boggle规则不允许重复走格子）
            if board.is_in_bound(ny, nx) and (ny, nx) not in current_path:
                current_path.append((ny, nx))
                dfs(ny, nx, current_path, current_str + board.board[ny][nx])
                current_path.pop() # 回溯

    # 以每个格子为起点启动搜索
    for i in range(board.rows):
        for j in range(board.cols):
            dfs(i, j, [(i,j)], board.board[i][j])
    return result

# 测试用例验证
board1 = [['Q', 'O', 'Q', 'Q'],
          ['D', 'O', 'G', 'Q'],
          ['Q', 'O', 'Q', 'Q'],
          ['Q', 'Q', 'Q', 'Q']]
word_dict = {'DOG': True}
board = Board(board1)
print(length_n_paths(3, board, word_dict))

修复后输出 #

[((1, 0), (0, 1), (1, 2)), ((1, 0), (1, 1), (1, 2)), ((1, 0), (2, 1), (1, 2))]

和预期结果完全一致。

内容的提问来源于stack exchange，提问作者user19095412