二维数组单词最优放置算法求解及全可行方案获取需求

数据老陈

2026-7-6

最优单词放置算法设计与问题修复

目标

开发可在二维数组中放置一组单词的代码，单词可水平、垂直、左到右对角线、右到左对角线排列，必要时可反转。

输入

二维数组尺寸（如8x8）；
单词集合（如"DATE", "DAY", "FIRST", "YEAR", "SECOND", "YOU", "ZONE"）。

完整输入示例：

OptimalWordPlacement(SizeOfTwoDimensionalArray=[8, 8],
                     collectionOfWords=["DATE", "DAY", "FIRST", "YEAR", "SECOND", "YOU", "ZONE"])

规则

单词长度不能超出数组维度；
字母可交叉，但每个单元格仅允许一次交叉（即一个单元格最多被一个单词的字母占据，或与一个其他单词的同字母交叉）；
未使用单元格设为_。

输出要求

程序需返回所有满足最优放置的二维数组，最优放置指在遵守规则的前提下放置最多单词的排列，若有多个最优解需全部返回（按最优到次优排序）。

现有问题

已实现的回溯法代码仅能找到一种解且存在bug，无法获取所有可行的最优解，请求设计对应算法。

现有代码

def place_words(board, words):
    def is_valid(board, word, x, y, dx, dy):
        for i in range(len(word)):
            nx, ny = x + i * dx, y + i * dy
            if nx < 0 or nx >= len(board) or ny < 0 or ny >= len(board[0]):
                return False
            if board[nx][ny] not in (0, word[i]):
                return False
        return True

    def place_word(board, word, x, y, dx, dy):
        for i in range(len(word)):
            nx, ny = x + i * dx, y + i * dy
            board[nx][ny] = word[i]

    def remove_word(board, word, x, y, dx, dy):
        for i in range(len(word)):
            nx, ny = x + i * dx, y + i * dy
            board[nx][ny] = 0

    def backtrack(board, words, index, tried_positions):
        if index == len(words):
            return True
        word = words[index]
        for x in range(len(board)):
            for y in range(len(board[0])):
                for dx, dy in ((0, 1), (1, 0), (1, 1), (-1, -1), (0, -1), (-1, 0), (-1, 1), (1, -1)):
                    if (word, x, y, dx, dy) not in tried_positions and is_valid(board, word, x, y, dx, dy):
                        place_word(board, word, x, y, dx, dy)
                        tried_positions.add((word, x, y, dx, dy))
                        if backtrack(board, words, index + 1, tried_positions):
                            return True
                        remove_word(board, word, x, y, dx, dy)
        return False

    if not words:
        return board
    tried_positions = set()
    if not backtrack(board, words, 0, tried_positions):
        print("No solution found")
    return board

i = 6
j = 6
board = [[0]*i for _ in range(j)]
words = ['DATE', 'DAY', 'FIRST', 'YEAR', 'SECOND', 'YOU', 'ZONE']


result = place_words(board, words)
for row_of_result in result:
    row_of_result = ['_' if x == 0 else x for x in row_of_result]
    print(row_of_result)

现有代码输出

['D', 'A', 'T', 'E', 'F', 'Y']
['A', 'Y', 'O', 'U', 'I', 'E']
['Y', 'Z', '_', '_', 'R', 'A']
['_', 'O', '_', '_', 'S', 'R']
['_', 'N', '_', '_', 'T', '_']
['S', 'E', 'C', 'O', 'N', 'D']

解决方案

问题分析

原代码核心问题：

找到第一个可行解后直接返回，终止了后续解的探索；
全局tried_positions限制了不同回溯分支的位置尝试；
未处理单词反转的需求；
直接修改原棋盘，无法保存多个独立解；
未统计放置单词数量，无法筛选最优解。

改进思路

追踪已放置单词数量，维护全局最优值，仅收集达到最优数量的解；
移除全局位置记录，改为动态检查每个位置的有效性；
为每个单词添加反转版本，支持反向放置；
每次找到有效解时拷贝棋盘状态，避免状态污染；
遍历所有回溯分支，不提前终止，收集全部可能的最优解；
按单词长度降序排列，优先放置长单词，减少无效回溯。

实现代码

def optimal_word_placement(size, words):
    rows, cols = size
    max_words_placed = 0
    optimal_solutions = []
    
    # 预处理：每个单词保留原词和反转词
    processed_words = []
    for word in words:
        processed_words.append(word)
        if word != word[::-1]:
            processed_words.append(word[::-1])
    
    def is_valid(board, word, x, y, dx, dy):
        """检查单词能否放置在指定位置和方向"""
        word_len = len(word)
        for i in range(word_len):
            nx = x + i * dx
            ny = y + i * dy
            # 越界检查
            if nx < 0 or nx >= rows or ny < 0 or ny >= cols:
                return False
            # 单元格已有不同字母，放置无效
            if board[nx][ny] != '_' and board[nx][ny] != word[i]:
                return False
        return True
    
    def place_word(board, word, x, y, dx, dy):
        """放置单词并记录原始字符，用于回溯"""
        original_chars = []
        for i in range(len(word)):
            nx = x + i * dx
            ny = y + i * dy
            original_chars.append(board[nx][ny])
            board[nx][ny] = word[i]
        return original_chars
    
    def remove_word(board, original_chars, x, y, dx, dy):
        """回溯恢复原始字符"""
        for i in range(len(original_chars)):
            nx = x + i * dx
            ny = y + i * dy
            board[nx][ny] = original_chars[i]
    
    def backtrack(board, remaining_words, placed_count):
        nonlocal max_words_placed, optimal_solutions
        
        # 更新最优解集合
        if placed_count > max_words_placed:
            max_words_placed = placed_count
            optimal_solutions = [ [row.copy() for row in board] ]
        elif placed_count == max_words_placed:
            optimal_solutions.append( [row.copy() for row in board] )
        
        if not remaining_words:
            return
        
        current_word = remaining_words[0]
        remaining = remaining_words[1:]
        
        # 尝试所有位置和方向
        for x in range(rows):
            for y in range(cols):
                for dx, dy in [(0,1), (1,0), (1,1), (-1,1), (0,-1), (-1,0), (-1,-1), (1,-1)]:
                    if is_valid(board, current_word, x, y, dx, dy):
                        original = place_word(board, current_word, x, y, dx, dy)
                        backtrack(board, remaining, placed_count + 1)
                        remove_word(board, original, x, y, dx, dy)
        
        # 尝试不放置当前单词，直接处理剩余单词
        backtrack(board, remaining, placed_count)
    
    # 初始化空棋盘，按单词长度降序排列以优化回溯效率
    initial_board = [ ['_' for _ in range(cols)] for _ in range(rows) ]
    sorted_words = sorted(processed_words, key=lambda w: len(w), reverse=True)
    backtrack(initial_board, sorted_words, 0)
    
    # 去重：不同单词组合可能生成相同棋盘
    unique_solutions = []
    seen = set()
    for sol in optimal_solutions:
        sol_str = str(sol)
        if sol_str not in seen:
            seen.add(sol_str)
            unique_solutions.append(sol)
    
    return unique_solutions

# 示例调用
if __name__ == "__main__":
    solutions = optimal_word_placement([6,6], ["DATE", "DAY", "FIRST", "YEAR", "SECOND", "YOU", "ZONE"])
    print(f"找到{len(solutions)}个最优解：")
    for idx, sol in enumerate(solutions, 1):
        print(f"\n解{idx}:")
        for row in sol:
            print(row)

代码说明

单词预处理：自动生成每个单词的反转版本，满足反向放置需求；
排序优化：优先放置长单词，减少回溯分支数量，提升效率；
状态管理：放置单词时记录原始字符，回溯时精准恢复，避免状态污染；
最优解收集：实时更新全局最优放置数，仅保留达到最优数量的解，并自动去重；
全分支探索：既尝试放置当前单词，也尝试跳过当前单词，确保不会遗漏任何最优组合。

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

二维数组单词最优放置算法求解及全可行方案获取需求

目标 #

输入 #

规则 #

输出要求 #

现有问题 #

现有代码 #

现有代码输出 #

解决方案 #

问题分析 #

改进思路 #

实现代码 #

代码说明 #

目标

输入

规则