從Sudoku解決方案中移除單元格使其成爲一個難題

Question

我正在編寫Sudoku應用程序，目前正在研究遊戲生成算法。我設法弄清楚如何快速生成解決方案（未解決）。儘管如此，我很難理解如何刪除一些數字來真正使它變成一個謎題。我的第一個想法是根據難度隨機刪除一定數量的細胞，但這不是正確的算法，因爲它經常會導致難以解決的難題或具有多種解決方案。它也可能產生不能反映所需難度的謎題。

這是我到目前爲止的代碼。我刪除了大部分不相關的代碼，但如果您希望查看以下未實現的內容，請告訴我。如果您願意，我也可以提供我在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