C# 數(shù)獨(dú)求解算法的實(shí)現(xiàn)

public class SudokuSolver
 {
  /// <summary>
  /// 題目面板
  /// </summary>
  public SudokuBlock[][] SudokuBoard { get; }

  public SudokuSolver(byte[][] board)
  {
   SudokuBoard = new SudokuBlock[board.Length][];
   //初始化數(shù)獨(dú)的行
   for (int i = 0; i < board.Length; i++)
   {
    SudokuBoard[i] = new SudokuBlock[board[i].Length];
    //初始化每行的列
    for (int j = 0; j < board[i].Length; j++)
    {
     SudokuBoard[i][j] = new SudokuBlock(
      board[i][j] > 0
      , board[i][j] <= 0 ? new BitArray(board.Length) : null
      , board[i][j] > 0 ? (byte?)board[i][j] : null
      , (byte)i
      , (byte)j);
    }
   }
  }

  /// <summary>
  /// 求解數(shù)獨(dú)
  /// </summary>
  /// <returns>獲得的解</returns>
  public IEnumerable<(SudokuState sudoku, PathTree path)> Solve(bool multiAnswer = false)
  {
   //初始化各個(gè)單元格能填入的數(shù)字
   InitCandidate();

   var pathRoot0 = new PathTree(null, -1, -1, -1); //填寫路徑樹，在非遞歸方法中用于記錄回退路徑和其他有用信息，初始生成一個(gè)根
   var path0 = pathRoot0;

   //循環(huán)填入能填入的數(shù)字只有一個(gè)的單元格，每次填入都可能產(chǎn)生新的唯一數(shù)單元格，直到?jīng)]有唯一數(shù)單元格可填
   while (true)
   {
    if (!FillUniqueNumber(ref path0))
    {
     break;
    }
   }

   //檢查是否在填唯一數(shù)單元格時(shí)就已經(jīng)把所有單元格填滿了
   var finish = true;
   foreach (var row in SudokuBoard)
   {
    foreach (var cell in row)
    {
     if (!cell.IsCondition && !cell.IsUnique)
     {
      finish = false;
      break;
     }
    }
    if (!finish)
    {
     break;
    }
   }
   if (finish)
   {
    yield return (new SudokuState(this), path0);
    yield break;
   }

   var pathRoot = new PathTree(null, -1, -1, -1); //填寫路徑樹，在非遞歸方法中用于記錄回退路徑和其他有用信息，初始生成一個(gè)根
   var path = pathRoot;
   var toRe = new List<(SudokuState sudoku, PathTree path)>();
   //還存在需要試數(shù)才能求解的單元格，開始暴力搜索
   int i = 0, j = 0;
   while (true)
   {
    (i, j) = NextBlock(i, j);

    //正常情況下返回-1表示已經(jīng)全部填完
    if (i == -1 && j == -1 && !multiAnswer)
    {
     var pathLast = path;//記住最后一步
     var path2 = path;
     while(path2.Parent.X != -1 && path2.Parent.Y != -1)
     {
      path2 = path2.Parent;
     }

     //將暴力搜索的第一步追加到唯一數(shù)單元格的填寫步驟的最后一步之后，連接成完整的填數(shù)步驟
     path0.Children.Add(path2);
     path2.Parent = path0;
     yield return (new SudokuState(this), pathLast);
     break;
    }

    var numNode = path.Children.LastOrDefault();
    //確定要從哪個(gè)數(shù)開始進(jìn)行填入嘗試
    var num = numNode == null
     ? 0
     : numNode.Number;

    bool filled = false; //是否發(fā)現(xiàn)可以填入的數(shù)
    //循環(huán)查看從num開始接下來(lái)的候選數(shù)是否能填（num是最后一次填入的數(shù)，傳到Candidate[]的索引器中剛好指向 num + 1是否能填的存儲(chǔ)位，對(duì)于標(biāo)準(zhǔn)數(shù)獨(dú)，候選數(shù)為 1~9，Candidate的索引范圍就是 0~8）
    for (; !SudokuBoard[i][j].IsCondition && !SudokuBoard[i][j].IsUnique && num < SudokuBoard[i][j].Candidate.Length; num++)
    {
     //如果有可以填的候選數(shù)，理論上不會(huì)遇見沒(méi)有可以填的情況，這種死路情況已經(jīng)在UpdateCandidate時(shí)檢查了
     if (SudokuBoard[i][j].Candidate[num] && !path.Children.Any(x => x.Number - 1 == num && !x.Pass))
     {
      filled = true; //進(jìn)來(lái)了說(shuō)明單元格有數(shù)可以填
      //記錄步驟
      var node = new PathTree(SudokuBoard[i][j], i, j, num + 1, path);
      path = node;
      //如果更新相關(guān)單元格的候選數(shù)時(shí)發(fā)現(xiàn)死路（更新函數(shù)會(huì)在發(fā)現(xiàn)死路時(shí)自動(dòng)撤銷更新）
      (bool canFill, (byte x, byte y)[] setList) updateResult = UpdateCandidate(i, j, (byte)(num + 1));
      if (!updateResult.canFill)
      {
       //記錄這條路是死路
       path.SetPass(false);
      }
      //僅在確認(rèn)是活路時(shí)設(shè)置填入數(shù)字
      if (path.Pass)
      {
       SudokuBoard[i][j].SetNumber((byte)(num + 1));
       path.SetList = updateResult.setList;//記錄相關(guān)單元格可填數(shù)更新記錄，方便在回退時(shí)撤銷更新
      }
      else //出現(xiàn)死路，要進(jìn)行回退，重試這個(gè)單元格的其他可填數(shù)字
      {
       path.Block.SetNumber(null);
       path = path.Parent;
      }
      //填入一個(gè)候選數(shù)后跳出循環(huán)，不再繼續(xù)嘗試填入之后的候選數(shù)
      break;
     }
    }
    if (!filled)//如果沒(méi)有成功填入數(shù)字，說(shuō)明上一步填入的單元格就是錯(cuò)的，會(huì)導(dǎo)致后面的單元格怎么填都不對(duì)，要回退到上一個(gè)單元格重新填
    {
     path.SetPass(false);
     path.Block.SetNumber(null);
     foreach (var pos in path.SetList)
     {
      SudokuBoard[pos.x][pos.y].Candidate.Set(path.Number - 1, true);
     }
     path = path.Parent;
     i = path.X < 0 ? 0 : path.X;
     j = path.Y < 0 ? 0 : path.Y;
    }
   }
  }

  /// <summary>
  /// 初始化候選項(xiàng)
  /// </summary>
  private void InitCandidate()
  {
   //初始化每行空缺待填的數(shù)字
   var rb = new List<BitArray>();
   for (int i = 0; i < SudokuBoard.Length; i++)
   {
    var r = new BitArray(SudokuBoard.Length);
    r.SetAll(true);
    for (int j = 0; j < SudokuBoard[i].Length; j++)
    {
     //如果i行j列是條件（題目）給出的數(shù)，設(shè)置數(shù)字不能再填（r[x] == false 表示 i 行不能再填 x + 1，下標(biāo)加1表示數(shù)獨(dú)可用的數(shù)字，下標(biāo)對(duì)應(yīng)的值表示下標(biāo)加1所表示的數(shù)是否還能填入該行）
     if (SudokuBoard[i][j].IsCondition || SudokuBoard[i][j].IsUnique)
     {
      r.Set(SudokuBoard[i][j].Number.Value - 1, false);
     }
    }
    rb.Add(r);
   }

   //初始化每列空缺待填的數(shù)字
   var cb = new List<BitArray>();
   for (int j = 0; j < SudokuBoard[0].Length; j++)
   {
    var c = new BitArray(SudokuBoard[0].Length);
    c.SetAll(true);
    for (int i = 0; i < SudokuBoard.Length; i++)
    {
     if (SudokuBoard[i][j].IsCondition || SudokuBoard[i][j].IsUnique)
     {
      c.Set(SudokuBoard[i][j].Number.Value - 1, false);
     }
    }
    cb.Add(c);
   }

   //初始化每宮空缺待填的數(shù)字（目前只能算標(biāo)準(zhǔn) n×n 數(shù)獨(dú)的宮）
   var gb = new List<BitArray>();
   //n表示每宮應(yīng)有的行、列數(shù)（標(biāo)準(zhǔn)數(shù)獨(dú)行列、數(shù)相同）
   var n = (int)Sqrt(SudokuBoard.Length);
   for (int g = 0; g < SudokuBoard.Length; g++)
   {
    var gba = new BitArray(SudokuBoard.Length);
    gba.SetAll(true);
    for (int i = g / n * n; i < g / n * n + n; i++)
    {
     for (int j = g % n * n; j < g % n * n + n; j++)
     {
      if (SudokuBoard[i][j].IsCondition || SudokuBoard[i][j].IsUnique)
      {
       gba.Set(SudokuBoard[i][j].Number.Value - 1, false);
      }
     }
    }
    gb.Add(gba);
   }

   //初始化每格可填的候選數(shù)字
   for (int i = 0; i < SudokuBoard.Length; i++)
   {
    for (int j = 0; j < SudokuBoard[i].Length; j++)
    {

     if (!SudokuBoard[i][j].IsCondition)
     {
      var c = SudokuBoard[i][j].Candidate;
      c.SetAll(true);
      //當(dāng)前格能填的數(shù)為其所在行、列、宮同時(shí)空缺待填的數(shù)字，按位與運(yùn)算后只有同時(shí)能填的候選數(shù)保持1（可填如當(dāng)前格），否則變成0
      // i / n * n + j / n：根據(jù)行號(hào)列號(hào)計(jì)算宮號(hào)，
      c = c.And(rb[i]).And(cb[j]).And(gb[i / n * n + j / n]);
      SudokuBoard[i][j].SetCandidate(c);
     }
    }
   }
  }

  /// <summary>
  /// 求解開始時(shí)尋找并填入單元格唯一可填的數(shù)，減少解空間
  /// </summary>
  /// <returns>是否填入過(guò)數(shù)字，如果為false，表示能立即確定待填數(shù)字的單元格已經(jīng)沒(méi)有，要開始暴力搜索了</returns>
  private bool FillUniqueNumber(ref PathTree path)
  {
   var filled = false;
   for (int i = 0; i < SudokuBoard.Length; i++)
   {
    for (int j = 0; j < SudokuBoard[i].Length; j++)
    {
     if (!SudokuBoard[i][j].IsCondition && !SudokuBoard[i][j].IsUnique)
     {
      var canFillCount = 0;
      var index = -1;
      for (int k = 0; k < SudokuBoard[i][j].Candidate.Length; k++)
      {
       if (SudokuBoard[i][j].Candidate[k])
       {
        index = k;
        canFillCount++;
       }
       if (canFillCount > 1)
       {
        break;
       }
      }
      if (canFillCount == 0)
      {
       throw new Exception("有單元格無(wú)法填入任何數(shù)字，數(shù)獨(dú)無(wú)解");
      }
      if (canFillCount == 1)
      {
       var num = (byte)(index + 1);
       SudokuBoard[i][j].SetNumber(num);
       SudokuBoard[i][j].SetUnique();
       filled = true;
       var upRes = UpdateCandidate(i, j, num);
       if (!upRes.canFill)
       {
        throw new Exception("有單元格無(wú)法填入任何數(shù)字，數(shù)獨(dú)無(wú)解");
       }
       path = new PathTree(SudokuBoard[i][j], i, j, num, path);
       path.SetList = upRes.setList;
      }
     }
    }
   }
   return filled;
  }

  /// <summary>
  /// 更新單元格所在行、列、宮的其它單元格能填的數(shù)字候選，如果沒(méi)有，會(huì)撤銷更新
  /// </summary>
  /// <param name="row">行號(hào)</param>
  /// <param name="column">列號(hào)</param>
  /// <param name="canNotFillNumber">要剔除的候選數(shù)字</param>
  /// <returns>更新候選數(shù)后，所有被更新的單元格是否都有可填的候選數(shù)字</returns>
  private (bool canFill, (byte x, byte y)[] setList) UpdateCandidate(int row, int column, byte canNotFillNumber)
  {
   var canFill = true;
   var list = new List<SudokuBlock>(); // 記錄修改過(guò)的單元格，方便撤回修改

   bool CanFillNumber(int i, int j)
   {
    var re = true;
    var _canFill = false;
    for (int k = 0; k < SudokuBoard[i][j].Candidate.Length; k++)
    {
     if (SudokuBoard[i][j].Candidate[k])
     {
      _canFill = true;
      break;
     }
    }
    if (!_canFill)
    {
     re = false;
    }

    return re;
   }
   bool Update(int i, int j)
   {
    if (!(i == row && j == column) && !SudokuBoard[i][j].IsCondition && !SudokuBoard[i][j].IsUnique && SudokuBoard[i][j].Candidate[canNotFillNumber - 1])
    {
     SudokuBoard[i][j].Candidate.Set(canNotFillNumber - 1, false);
     list.Add(SudokuBoard[i][j]);

     return CanFillNumber(i, j);
    }
    else
    {
     return true;
    }
   }

   //更新該行其余列
   for (int j = 0; j < SudokuBoard[row].Length; j++)
   {
    canFill = Update(row, j);
    if (!canFill)
    {
     break;
    }
   }

   if (canFill) //只在行更新時(shí)沒(méi)發(fā)現(xiàn)無(wú)數(shù)可填的單元格時(shí)進(jìn)行列更新才有意義
   {
    //更新該列其余行
    for (int i = 0; i < SudokuBoard.Length; i++)
    {
     canFill = Update(i, column);
     if (!canFill)
     {
      break;
     }
    }
   }

   if (canFill)//只在行、列更新時(shí)都沒(méi)發(fā)現(xiàn)無(wú)數(shù)可填的單元格時(shí)進(jìn)行宮更新才有意義
   {
    //更新該宮其余格
    //n表示每宮應(yīng)有的行、列數(shù)（標(biāo)準(zhǔn)數(shù)獨(dú)行列、數(shù)相同）
    var n = (int)Sqrt(SudokuBoard.Length);
    //g為宮的編號(hào)，根據(jù)行號(hào)列號(hào)計(jì)算
    var g = row / n * n + column / n;
    for (int i = g / n * n; i < g / n * n + n; i++)
    {
     for (int j = g % n * n; j < g % n * n + n; j++)
     {
      canFill = Update(i, j);
      if (!canFill)
      {
       goto canNotFill;
      }
     }
    }
    canNotFill:;
   }

   //如果發(fā)現(xiàn)存在沒(méi)有任何數(shù)字可填的單元格，撤回所有候選修改
   if (!canFill)
   {
    foreach (var cell in list)
    {
     cell.Candidate.Set(canNotFillNumber - 1, true);
    }
   }

   return (canFill, list.Select(x => (x.X, x.Y)).ToArray());
  }

  /// <summary>
  /// 尋找下一個(gè)要嘗試填數(shù)的格
  /// </summary>
  /// <param name="i">起始行號(hào)</param>
  /// <param name="j">起始列號(hào)</param>
  /// <returns>找到的下一個(gè)行列號(hào)，沒(méi)有找到返回-1</returns>
  private (int x, int y) NextBlock(int i = 0, int j = 0)
  {
   for (; i < SudokuBoard.Length; i++)
   {
    for (; j < SudokuBoard[i].Length; j++)
    {
     if (!SudokuBoard[i][j].IsCondition && !SudokuBoard[i][j].IsUnique && !SudokuBoard[i][j].Number.HasValue)
     {
      return (i, j);
     }
    }
    j = 0;
   }

   return (-1, -1);
  }

  public override string ToString()
  {
   static string Str(SudokuBlock b)
   {
    var n1 = new[] { "①", "②", "③", "④", "⑤", "⑥", "⑦", "⑧", "⑨" };
    var n2 = new[] { "⑴", "⑵", "⑶", "⑷", "⑸", "⑹", "⑺", "⑻", "⑼" };
    return b.Number.HasValue
     ? b.IsCondition
      ? " " + b.Number
      : b.IsUnique
       ? n1[b.Number.Value - 1]
       : n2[b.Number.Value - 1]
     : "▢";
   }
   return
$@"{Str(SudokuBoard[0][0])},{Str(SudokuBoard[0][1])},{Str(SudokuBoard[0][2])},{Str(SudokuBoard[0][3])},{Str(SudokuBoard[0][4])},{Str(SudokuBoard[0][5])},{Str(SudokuBoard[0][6])},{Str(SudokuBoard[0][7])},{Str(SudokuBoard[0][8])}
{Str(SudokuBoard[1][0])},{Str(SudokuBoard[1][1])},{Str(SudokuBoard[1][2])},{Str(SudokuBoard[1][3])},{Str(SudokuBoard[1][4])},{Str(SudokuBoard[1][5])},{Str(SudokuBoard[1][6])},{Str(SudokuBoard[1][7])},{Str(SudokuBoard[1][8])}
{Str(SudokuBoard[2][0])},{Str(SudokuBoard[2][1])},{Str(SudokuBoard[2][2])},{Str(SudokuBoard[2][3])},{Str(SudokuBoard[2][4])},{Str(SudokuBoard[2][5])},{Str(SudokuBoard[2][6])},{Str(SudokuBoard[2][7])},{Str(SudokuBoard[2][8])}
{Str(SudokuBoard[3][0])},{Str(SudokuBoard[3][1])},{Str(SudokuBoard[3][2])},{Str(SudokuBoard[3][3])},{Str(SudokuBoard[3][4])},{Str(SudokuBoard[3][5])},{Str(SudokuBoard[3][6])},{Str(SudokuBoard[3][7])},{Str(SudokuBoard[3][8])}
{Str(SudokuBoard[4][0])},{Str(SudokuBoard[4][1])},{Str(SudokuBoard[4][2])},{Str(SudokuBoard[4][3])},{Str(SudokuBoard[4][4])},{Str(SudokuBoard[4][5])},{Str(SudokuBoard[4][6])},{Str(SudokuBoard[4][7])},{Str(SudokuBoard[4][8])}
{Str(SudokuBoard[5][0])},{Str(SudokuBoard[5][1])},{Str(SudokuBoard[5][2])},{Str(SudokuBoard[5][3])},{Str(SudokuBoard[5][4])},{Str(SudokuBoard[5][5])},{Str(SudokuBoard[5][6])},{Str(SudokuBoard[5][7])},{Str(SudokuBoard[5][8])}
{Str(SudokuBoard[6][0])},{Str(SudokuBoard[6][1])},{Str(SudokuBoard[6][2])},{Str(SudokuBoard[6][3])},{Str(SudokuBoard[6][4])},{Str(SudokuBoard[6][5])},{Str(SudokuBoard[6][6])},{Str(SudokuBoard[6][7])},{Str(SudokuBoard[6][8])}
{Str(SudokuBoard[7][0])},{Str(SudokuBoard[7][1])},{Str(SudokuBoard[7][2])},{Str(SudokuBoard[7][3])},{Str(SudokuBoard[7][4])},{Str(SudokuBoard[7][5])},{Str(SudokuBoard[7][6])},{Str(SudokuBoard[7][7])},{Str(SudokuBoard[7][8])}
{Str(SudokuBoard[8][0])},{Str(SudokuBoard[8][1])},{Str(SudokuBoard[8][2])},{Str(SudokuBoard[8][3])},{Str(SudokuBoard[8][4])},{Str(SudokuBoard[8][5])},{Str(SudokuBoard[8][6])},{Str(SudokuBoard[8][7])},{Str(SudokuBoard[8][8])}";
  }
 }

public class PathTree
 {
  public PathTree Parent { get; set; }
  public List<PathTree> Children { get; } = new List<PathTree>();

  public SudokuBlock Block { get; }
  public int X { get; }
  public int Y { get; }
  public int Number { get; }
  public bool Pass { get; private set; } = true;
  public (byte x, byte y)[] SetList { get; set; }

  public PathTree(SudokuBlock block, int x, int y, int number)
  {
   Block = block;
   X = x;
   Y = y;
   Number = number;

  }

  public PathTree(SudokuBlock block, int row, int column, int number, PathTree parent)
   : this(block, row, column, number)
  {
   Parent = parent;
   Parent.Children.Add(this);
  }

  public void SetPass(bool pass)
  {
   Pass = pass;
  }
 }

public class SudokuState
 {
  public SudokuBlock[][] SudokuBoard { get; }
  public SudokuState(SudokuSolver sudoku)
  {
   SudokuBoard = new SudokuBlock[sudoku.SudokuBoard.Length][];
   //初始化數(shù)獨(dú)的行
   for (int i = 0; i < sudoku.SudokuBoard.Length; i++)
   {
    SudokuBoard[i] = new SudokuBlock[sudoku.SudokuBoard[i].Length];
    //初始化每行的列
    for (int j = 0; j < sudoku.SudokuBoard[i].Length; j++)
    {
     SudokuBoard[i][j] = new SudokuBlock(
      sudoku.SudokuBoard[i][j].IsCondition
      , null
      , sudoku.SudokuBoard[i][j].Number
      , (byte)i
      , (byte)j);
     if (sudoku.SudokuBoard[i][j].IsUnique)
     {
      SudokuBoard[i][j].SetUnique();
     }
    }
   }
  }

  public override string ToString()
  {
   static string Str(SudokuBlock b)
   {
    var n1 = new[] { "①", "②", "③", "④", "⑤", "⑥", "⑦", "⑧", "⑨" };
    var n2 = new[] { "⑴", "⑵", "⑶", "⑷", "⑸", "⑹", "⑺", "⑻", "⑼" };
    return b.Number.HasValue
     ? b.IsCondition
      ? " " + b.Number
      : b.IsUnique
       ? n1[b.Number.Value - 1]
       : n2[b.Number.Value - 1]
     : "▢";
   }
   return
$@"{Str(SudokuBoard[0][0])},{Str(SudokuBoard[0][1])},{Str(SudokuBoard[0][2])},{Str(SudokuBoard[0][3])},{Str(SudokuBoard[0][4])},{Str(SudokuBoard[0][5])},{Str(SudokuBoard[0][6])},{Str(SudokuBoard[0][7])},{Str(SudokuBoard[0][8])}
{Str(SudokuBoard[1][0])},{Str(SudokuBoard[1][1])},{Str(SudokuBoard[1][2])},{Str(SudokuBoard[1][3])},{Str(SudokuBoard[1][4])},{Str(SudokuBoard[1][5])},{Str(SudokuBoard[1][6])},{Str(SudokuBoard[1][7])},{Str(SudokuBoard[1][8])}
{Str(SudokuBoard[2][0])},{Str(SudokuBoard[2][1])},{Str(SudokuBoard[2][2])},{Str(SudokuBoard[2][3])},{Str(SudokuBoard[2][4])},{Str(SudokuBoard[2][5])},{Str(SudokuBoard[2][6])},{Str(SudokuBoard[2][7])},{Str(SudokuBoard[2][8])}
{Str(SudokuBoard[3][0])},{Str(SudokuBoard[3][1])},{Str(SudokuBoard[3][2])},{Str(SudokuBoard[3][3])},{Str(SudokuBoard[3][4])},{Str(SudokuBoard[3][5])},{Str(SudokuBoard[3][6])},{Str(SudokuBoard[3][7])},{Str(SudokuBoard[3][8])}
{Str(SudokuBoard[4][0])},{Str(SudokuBoard[4][1])},{Str(SudokuBoard[4][2])},{Str(SudokuBoard[4][3])},{Str(SudokuBoard[4][4])},{Str(SudokuBoard[4][5])},{Str(SudokuBoard[4][6])},{Str(SudokuBoard[4][7])},{Str(SudokuBoard[4][8])}
{Str(SudokuBoard[5][0])},{Str(SudokuBoard[5][1])},{Str(SudokuBoard[5][2])},{Str(SudokuBoard[5][3])},{Str(SudokuBoard[5][4])},{Str(SudokuBoard[5][5])},{Str(SudokuBoard[5][6])},{Str(SudokuBoard[5][7])},{Str(SudokuBoard[5][8])}
{Str(SudokuBoard[6][0])},{Str(SudokuBoard[6][1])},{Str(SudokuBoard[6][2])},{Str(SudokuBoard[6][3])},{Str(SudokuBoard[6][4])},{Str(SudokuBoard[6][5])},{Str(SudokuBoard[6][6])},{Str(SudokuBoard[6][7])},{Str(SudokuBoard[6][8])}
{Str(SudokuBoard[7][0])},{Str(SudokuBoard[7][1])},{Str(SudokuBoard[7][2])},{Str(SudokuBoard[7][3])},{Str(SudokuBoard[7][4])},{Str(SudokuBoard[7][5])},{Str(SudokuBoard[7][6])},{Str(SudokuBoard[7][7])},{Str(SudokuBoard[7][8])}
{Str(SudokuBoard[8][0])},{Str(SudokuBoard[8][1])},{Str(SudokuBoard[8][2])},{Str(SudokuBoard[8][3])},{Str(SudokuBoard[8][4])},{Str(SudokuBoard[8][5])},{Str(SudokuBoard[8][6])},{Str(SudokuBoard[8][7])},{Str(SudokuBoard[8][8])}";
  }
 }

 public class SudokuBlock
 {
  /// <summary>
  /// 填入的數(shù)字
  /// </summary>
  public byte? Number { get; private set; }

  /// <summary>
  /// X坐標(biāo)
  /// </summary>
  public byte X { get; }

  /// <summary>
  /// Y坐標(biāo)
  /// </summary>
  public byte Y { get; }

  /// <summary>
  /// 候選數(shù)字，下標(biāo)所示狀態(tài)表示數(shù)字“下標(biāo)加1”是否能填入
  /// </summary>
  public BitArray Candidate { get; private set; }

  /// <summary>
  /// 是否為條件（題目）給出數(shù)字的單元格
  /// </summary>
  public bool IsCondition { get; }

  /// <summary>
  /// 是否為游戲開始就能確定唯一可填數(shù)字的單元格
  /// </summary>
  public bool IsUnique { get; private set; }

  public SudokuBlock(bool isCondition, BitArray candidate, byte? number, byte x, byte y)
  {
   IsCondition = isCondition;
   Candidate = candidate;
   Number = number;
   IsUnique = false;
   X = x;
   Y = y;
  }

  public void SetNumber(byte? number)
  {
   Number = number;
  }

  public void SetCandidate(BitArray candidate)
  {
   Candidate = candidate;
  }

  public void SetUnique()
  {
   IsUnique = true;
  }
 }

static void Main(string[] args)
  {
   //模板
   //byte[][] game = new byte[][] {
   // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
   // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
   // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
   // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
   // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
   // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
   // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
   // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
   // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},};
   //這個(gè)簡(jiǎn)單，無(wú)需嘗試，一直填唯一數(shù)單元格，填完后剩下的單元格又有會(huì)變唯一數(shù)單元格
   //byte[][] game = new byte[][] {
   // new byte[]{0, 5, 0, 7, 0, 6, 0, 1, 0},
   // new byte[]{0, 8, 0, 0, 9, 0, 0, 6, 0},
   // new byte[]{0, 6, 9, 0, 8, 0, 7, 3, 0},
   // new byte[]{0, 1, 0, 0, 4, 0, 0, 0, 6},
   // new byte[]{6, 0, 7, 1, 0, 3, 8, 0, 5},
   // new byte[]{9, 0, 0, 0, 0, 8, 0, 2, 0},
   // new byte[]{0, 2, 4, 0, 1, 0, 6, 5, 0},
   // new byte[]{0, 7, 0, 0, 6, 0, 0, 4, 0},
   // new byte[]{0, 9, 0, 4, 0, 2, 0, 8, 0},};
   //可以填一部分唯一數(shù)單元格，剩下一部分需要嘗試，調(diào)試用
   //byte[][] game = new byte[][] {
   // new byte[]{7, 0, 0, 5, 0, 0, 0, 0, 2},
   // new byte[]{0, 3, 0, 0, 0, 4, 6, 0, 0},
   // new byte[]{0, 0, 2, 6, 0, 0, 0, 0, 0},
   // new byte[]{2, 0, 0, 0, 7, 0, 0, 0, 5},
   // new byte[]{5, 0, 0, 1, 0, 3, 0, 0, 6},
   // new byte[]{3, 0, 0, 4, 0, 0, 0, 0, 9},
   // new byte[]{0, 0, 0, 0, 0, 1, 5, 0, 0},
   // new byte[]{0, 0, 7, 2, 0, 0, 0, 4, 0},
   // new byte[]{4, 0, 0, 0, 0, 9, 0, 0, 7},};
   //全部要靠嘗試來(lái)填
   byte[][] game = new byte[][] {
    new byte[]{1, 0, 0, 2, 0, 0, 3, 0, 0},
    new byte[]{0, 4, 0, 5, 0, 0, 0, 6, 0},
    new byte[]{0, 0, 0, 7, 0, 0, 8, 0, 0},
    new byte[]{3, 0, 0, 0, 0, 7, 0, 0, 0},
    new byte[]{0, 9, 0, 0, 0, 0, 0, 5, 0},
    new byte[]{0, 0, 0, 6, 0, 0, 0, 0, 7},
    new byte[]{0, 0, 2, 0, 0, 4, 0, 0, 0},
    new byte[]{0, 5, 0, 0, 0, 6, 0, 9, 0},
    new byte[]{0, 0, 8, 0, 0, 1, 0, 0, 3},};
   var su = new SudokuSolver(game);
   var r = su.Solve();
   var r1 = r.First();
   static IEnumerable<PathTree> GetPath(PathTree pathTree)
   {
    List<PathTree> list = new List<PathTree>();
    var path = pathTree;
    while (path.Parent != null)
    {
     list.Add(path);
     path = path.Parent;
    }

    return list.Reverse<PathTree>();
   }

   var p = GetPath(r1.path).Select(x => $"在 {x.X + 1} 行 {x.Y + 1} 列填入 {x.Number}");
   foreach(var step in p)
   {
    Console.WriteLine(step);
   }

   Console.WriteLine(r1.sudoku);
   Console.ReadKey();
  }