从数独解决方案中删除单元格以使其成为谜题

Question

我正在编写一个数独应用程序，目前正在研究游戏生成算法。我设法想出了如何快速生成解决方案（而不是解决方案）。然而，如何删除一些数字，使其真正成为一个谜，我感到困惑。我的第一个倾向是根据难度随机移除一定数量的单元格，但这不是正确的算法，因为它通常会呈现无法解决或有多个解决方案的谜题。它还可能生成无法反映所需难度的谜题。

这是我到目前为止拥有的代码。我删除了大部分不相关的代码，但如果您想看到下面未实现但使用的东西，请告诉我。如果您愿意，我也可以提供我对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

没有“简单”的方法可以从已完成的数独网格中删除线索，因为删除过程不是线性的。

每次删除单元格或线索后，您需要检查数独是否只有唯一的解决方案。

要检查这一点，您需要运行一个可以计算所有可能解决方案的解算器（您可以在找到两种可能后停止它以节省时间）。

求解数独、计算所有数独解和删除单元格时最常用的两种算法是回溯算法和跳链算法。

这篇文章很好地解释了跳舞链接算法如何在数独中使用：http://garethrees.org/2007/06/10/zendoku-generation/#section-2

这是用JavaScript编写的Sudokus中跳舞链接算法的另一个描述：http://www.sudokubum.com/documentation.html

下面是关于舞蹈链接算法的全文：http://lanl.arxiv.org/pdf/cs/0011047

Answer 2

这是一篇关于数独生成的论文

我认为你需要一个数独解算器，它也会计算出可用解的数量，然后以这样一种方式减去数字，即始终只有一个可用解。

您可以使用相同的方法向网格中添加数字，然后检查可能的解决方案的数量，并在解决方案数量大于1时继续添加，在解决方案数量为0时回溯