面向游戏的待排序色块生成算法设计与难度递进方案问询

开发者阿泽

2026-7-1

问题描述

我们要设计一款色块排序游戏，核心规则如下：

每个色块包含6个颜色单元，例如：Block = [Red,Red,Red,Red,Red,Red]
需要生成一组待排序的色块列表，这些色块最终可通过重新分配颜色单元，组合成全单一颜色的色块（每个目标色块为6个相同颜色单元）

示例合法输入与对应可整理的目标状态：
输入色块：

Block1 = [Red,Red,Red,Blue,Blue,Blue]
Block2 = [Yellow,Yellow,Yellow,Yellow,Blue,Blue]
Block3 = [Blue, Blue, Blue, Blue, Yellow, Yellow]
Block4 = [Blue, Blue, Blue, Red, Red, Red]

可整理为：

Block1 = [Red * 6]
Block2 = [Yellow* 6]
Block3 = [Blue* 6]
Block4 = [Blue* 6]

核心算法思路

推荐采用反向构造法（从目标状态倒推生成待排序色块），这是此类排序谜题生成的通用可靠方案，可避免正向生成出现无解的情况：

确定目标状态：先定义最终要得到的全单色色块集合，允许存在重复颜色的目标色块（如示例中的两个蓝色色块）
统计颜色总量：每种颜色的总单元数必须是6的整数倍（因为每个目标色块对应6个同色单元）
拆分与打乱：将每个目标色块的6个颜色单元随机拆分到多个待生成色块中，确保每个待生成色块恰好包含6个单元。拆分时可控制每个色块的颜色种类数，以此调节难度
合法性校验（可选）：移除生成结果中存在的全单色块，避免出现 trivial 解，适配不同难度需求

难度递进方案

可从以下维度逐步提升游戏难度：

颜色种类递增：
- 初始关卡：仅用2种颜色，每个待排序色块最多包含2种颜色
- 中期关卡：增加至3-4种颜色，允许部分色块包含3种颜色
- 后期关卡：5+种颜色，大部分色块含2-3种颜色，少量色块含4种颜色
色块数量递增：
- 初始：3-4个色块
- 中期：5-6个色块
- 后期：7+个色块
颜色分布复杂度提升：
- 初始：色块内颜色单元集中分布（如前3个红、后3个蓝）
- 中期：颜色单元随机打乱分布
- 后期：同一颜色的单元分散在更多色块中，增加跨块调整的操作次数
操作规则限制（可选）：比如限制每次只能移动连续的N个颜色单元，初始N=3，后期逐步降低到N=1，进一步提升难度

C# 实现示例

以下是反向构造法的核心实现代码：

using System;
using System.Collections.Generic;
using System.Linq;

public enum Color { Red, Blue, Yellow, Green, Purple }

public class Block
{
    public List<Color> Units { get; set; }

    public Block(List<Color> units)
    {
        Units = units;
    }

    public override string ToString()
    {
        return $"[{string.Join(", ", Units.Select(c => c.ToString()))}]";
    }
}

public class PuzzleGenerator
{
    /// <summary>
    /// 生成待排序色块列表
    /// </summary>
    /// <param name="targetBlocks">目标全单色色块集合</param>
    /// <param name="maxColorsPerBlock">每个待生成色块允许的最大颜色种类数</param>
    /// <returns></returns>
    public List<Block> GeneratePuzzle(List<Block> targetBlocks, int maxColorsPerBlock)
    {
        // 统计所有颜色单元，按颜色分组
        var colorPool = new Dictionary<Color, Queue<Color>>();
        foreach (var targetBlock in targetBlocks)
        {
            foreach (var color in targetBlock.Units)
            {
                if (!colorPool.ContainsKey(color))
                    colorPool[color] = new Queue<Color>();
                colorPool[color].Enqueue(color);
            }
        }

        var puzzleBlocks = new List<Block>();
        var totalUnits = targetBlocks.Sum(b => b.Units.Count);
        var random = new Random();

        // 逐个生成待排序色块（每个色块6个单元）
        while (totalUnits > 0)
        {
            var newBlockUnits = new List<Color>();
            var usedColors = new HashSet<Color>();

            // 填充当前色块的6个单元
            while (newBlockUnits.Count < 6)
            {
                var availableColors = colorPool.Where(kv => kv.Value.Count > 0).Select(kv => kv.Key).ToList();
                Color selectedColor;

                // 优先选择新颜色（控制颜色种类数不超过上限）
                if (usedColors.Count < maxColorsPerBlock && random.NextDouble() < 0.7)
                {
                    selectedColor = availableColors[random.Next(availableColors.Count)];
                    usedColors.Add(selectedColor);
                }
                else
                {
                    // 从当前已用颜色中选择
                    selectedColor = usedColors.ElementAt(random.Next(usedColors.Count));
                }

                // 从颜色池取出单元并添加到当前色块
                newBlockUnits.Add(colorPool[selectedColor].Dequeue());
                totalUnits--;
            }

            // 打乱当前色块的单元顺序
            newBlockUnits.Shuffle(random);
            puzzleBlocks.Add(new Block(newBlockUnits));
        }

        // 移除全单色块（可选，根据难度需求调整）
        puzzleBlocks.RemoveAll(b => b.Units.Distinct().Count() == 1);

        return puzzleBlocks;
    }
}

// 扩展方法：打乱列表元素顺序
public static class ListExtensions
{
    public static void Shuffle<T>(this IList<T> list, Random random)
    {
        int n = list.Count;
        while (n > 1)
        {
            n--;
            int k = random.Next(n + 1);
            (list[k], list[n]) = (list[n], list[k]);
        }
    }
}

使用示例

// 定义目标全单色色块集合
var targetBlocks = new List<Block>
{
    new Block(Enumerable.Repeat(Color.Red, 6).ToList()),
    new Block(Enumerable.Repeat(Color.Yellow, 6).ToList()),
    new Block(Enumerable.Repeat(Color.Blue, 6).ToList()),
    new Block(Enumerable.Repeat(Color.Blue, 6).ToList())
};

var generator = new PuzzleGenerator();
// 生成每个色块最多含2种颜色的谜题
var puzzle = generator.GeneratePuzzle(targetBlocks, 2);
foreach (var block in puzzle)
{
    Console.WriteLine(block.ToString());
}

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

面向游戏的待排序色块生成算法设计与难度递进方案问询

使用示例 #

使用示例