如何生成满足邻值不重复规则的1-4值正方形二维数组？

核心思路 #

放弃暴力遍历所有组合的低效方式，采用伪随机增量生成+即时规则校验的方案：每生成一个元素就立刻验证所有约束，不合法就直接更换候选值，仅在极端冲突时做局部回溯，同时通过随机种子和局部扰动避免出现可观测的重复图案。

明确约束规则 #

生成的数组需满足以下所有条件：

• 任意元素的上下左右相邻有效值（非x的元素）不能与当前元素重复
• 任意元素的对角相邻元素不能与当前元素相同
• 任意元素上下左右方向隔一个位置的有效值（如果存在）不能与当前元素相同

Lua 实现代码 #

-- 初始化随机种子，每次运行生成不同数组，避免重复规律
math.randomseed(os.time())

-- 生成指定大小的符合规则的数组，size为正方形边长，fillX为是否填充x（可选，默认false）
function generateValidArray(size, fillX)
    local arr = {}
    -- 初始化空数组
    for i = 1, size do
        arr[i] = {}
        for j = 1, size do
            arr[i][j] = nil
        end
    end

    -- 获取当前位置(i,j)的所有禁止值
    local function getForbiddenValues(i, j)
        local forbidden = {}
        -- 规则2：对角邻居不能相同
        local diagonals = {{-1,-1}, {-1,1}, {1,-1}, {1,1}}
        for _, d in ipairs(diagonals) do
            local ni, nj = i + d[1], j + d[2]
            if ni >=1 and ni <= size and nj >=1 and nj <= size and arr[ni][nj] then
                forbidden[arr[ni][nj]] = true
            end
        end

        -- 规则1：相邻有效值不能重复；规则3：隔一个位置的有效值不能相同
        local directions = {{-1,0}, {1,0}, {0,-1}, {0,1}}
        for _, dir in ipairs(directions) do
            -- 检查相邻（距离1）
            local ni, nj = i + dir[1], j + dir[2]
            if ni >=1 and ni <= size and nj >=1 and nj <= size and arr[ni][nj] then
                forbidden[arr[ni][nj]] = true
            end
            -- 检查隔一个（距离2）
            ni, nj = i + dir[1]*2, j + dir[2]*2
            if ni >=1 and ni <= size and nj >=1 and nj <= size and arr[ni][nj] then
                forbidden[arr[ni][nj]] = true
            end
        end
        return forbidden
    end

    -- 生成单个位置的有效值
    local function generateValue(i, j)
        local forbidden = getForbiddenValues(i, j)
        local candidates = {}
        -- 收集1-4中未被禁止的值
        for v = 1,4 do
            if not forbidden[v] then
                table.insert(candidates, v)
            end
        end
        -- 如果没有候选值，返回nil表示需要回溯
        if #candidates == 0 then
            return nil
        end
        -- 随机选一个候选值
        return candidates[math.random(#candidates)]
    end

    -- 逐行逐列生成元素，遇到冲突则回溯前一个位置
    local i, j = 1, 1
    while i <= size do
        while j <= size do
            -- 如果是需要填充x的位置（示例中的x位置，可自定义规则，比如奇偶位置）
            if fillX and ((i % 2 == 1 and j % 2 == 1) or (i % 2 == 0 and j % 2 == 0)) then
                arr[i][j] = 'x'
                j = j + 1
            else
                local val = generateValue(i, j)
                if val then
                    arr[i][j] = val
                    j = j + 1
                else
                    -- 回溯到前一个位置，重置当前位置
                    arr[i][j] = nil
                    j = j - 1
                    -- 如果当前行第一个位置冲突，回溯到上一行最后一个位置
                    if j == 0 then
                        i = i - 1
                        j = size
                        -- 如果回溯到第一行之前，说明当前size下无法生成（理论上1-4值足够，不会出现）
                        if i == 0 then
                            error("无法生成符合规则的数组，请调整size")
                        end
                    end
                end
            end
        end
        j = 1
        i = i + 1
    end

    -- 打印数组（可选）
    for _, row in ipairs(arr) do
        local line = {}
        for _, val in ipairs(row) do
            table.insert(line, tostring(val))
        end
        print(table.concat(line, " "))
    end

    return arr
end

-- 示例：生成5x5的数组，填充x（对应示例中的x位置规则）
generateValidArray(5, true)

代码说明 #

1. 随机化：通过os.time()初始化随机种子，每次运行生成的数组都不同，彻底避免可观测的重复图案
2. 即时校验：每个元素生成前先收集所有被禁止的值，从合法候选值中随机选择，无需遍历所有组合
3. 局部回溯：仅在当前位置无合法值时回溯到前一个位置，相比全组合遍历效率提升几个数量级
4. 自定义x填充：fillX参数可控制是否填充x，示例中采用奇偶位置填充规则，可根据需求修改

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