c# - 从数独解决方案中删除单元格使其成为一个谜题

Question

我正在编写一个数独应用程序，目前正在研究游戏生成算法。我设法弄清楚如何快速生成解决方案(不是解决)。不过，我对如何删除一些数字以实际使其成为一个谜题感到困惑。我的第一个倾向是根据难度随机删除一定数量的单元格，但这不是正确的算法，因为它经常呈现无法解决或有多个解决方案的谜题。它还可能生成未反射(reflect)所请求难度的谜题。

这是我目前的代码。我删除了大部分不相关的代码，但如果您想查看未实现但在下面使用的内容，请告诉我。如果您愿意，我也可以提供我对 Puzzlefy 方法的尝试，但我选择不立即发布它，因为它明显错误(即使它“有效”)。

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

namespace Sudoku
{
    public class Game
    {
        public enum Difficulty
        {
            VeryEasy,
            Easy,
            Medium,
            Difficult,
            Evil
        }

        private readonly int?[,] _currentItems = new int?[9,9];
        private readonly int?[,] _solution = new int?[9,9];
        private readonly int?[,] _startingItems = new int?[9,9];
        private readonly Difficulty _difficulty;

        public Game(Difficulty difficulty)
        {
            _difficulty = difficulty;
            GenerateSolution();
            Puzzlefy();
        }

        private void GenerateSolution()
        {
            var random = new Random();
            var availableNumbers = new Stack<List<int?>>(81);
            var x = 0;
            var y = 0;

            availableNumbers.Push(AllowableNumbers(_solution, 0, 0).ToList());
            while (x < 9 && y < 9)
            {
                var currentAvailableNumbers = AllowableNumbers(_solution, x, y).ToList();
                availableNumbers.Push(currentAvailableNumbers);

                // back trace if the board is in an invalid state
                while (currentAvailableNumbers.Count == 0)
                {
                    _solution[x, y] = null;
                    availableNumbers.Pop();
                    currentAvailableNumbers = availableNumbers.Peek();
                    x -= y >= 1 ? 0 : 1;
                    y = y >= 1 ? y - 1 : 8;
                }

                var index = random.Next(currentAvailableNumbers.Count);
                _solution[x, y] = currentAvailableNumbers[index];
                currentAvailableNumbers.RemoveAt(index);

                x += y < 8 ? 0 : 1;
                y = y < 8 ? y + 1 : 0;
            }
        }

        private void Puzzlefy()
        {
            CopyCells(_solution, _startingItems);

            // remove some stuff from _startingItems

            CopyCells(_startingItems, _currentItems);
        }
    }
}

我不是在寻找代码，而是在寻找算法。我将如何从解决方案中删除数字以使其成为一个谜题？

Answer 1

这是一个paper on sudoku generation

我认为您将需要一个数独求解器，它还会计算可用解决方案的数量，然后以始终只有一个可用解决方案的方式减去数字。

可以用同样的方法给网格加数，然后检查可能解的个数，当解数大于1时继续加，当解数为0时回溯