3

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

这是我到目前为止的代码。我删除了大部分不相关的代码，但如果您想查看未实现但在下面使用的内容，请告诉我。如果您愿意，我也可以提供我对该方法的尝试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);
        }
    }
}

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

4

2 回答 2

3

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

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

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

于 2013-02-13T17:15:05.670 回答
0

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

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

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

两种最流行的算法都用于解决数独，计算所有数独解决方案和删除单元格是回溯算法和跳舞链接算法。

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

这是用 JavaScript 编写的数独中舞蹈链接算法的另一种描述：http: //www.sudokubum.com/documentation.html

这是关于一般舞蹈链接算法的完整论文：http: //lanl.arxiv.org/pdf/cs/0011047

于 2018-04-23T22:35:03.303 回答