解数独中的裸三元组

Question

我希望我在大学时能更加关注数学课。 :)

我如何实现这个裸三元组的数学公式？

裸三元组
取三个共享单位 U 的单元格 C = {c1, c2, c3}。取三个数字 N = {n1, n2, n3}。如果 C 中的每个单元格都有 ci ⊆ N 作为其候选单元格，那么我们可以删除所有单元格 ni ∈ N 来自 U 中的其他单元格。**

我有一个方法，它采用一个单位（例如一个盒子、一行或一列）作为参数。 该单元包含 9 个单元格，因此我需要一次比较盒子中 3 个单元格的所有组合，也许将它们放入堆栈或集合中以进行进一步计算。

下一步将逐一获取这些 3 单元格组合，并将它们的候选值与 3 个数字进行比较。同样，这 3 个数字可以是从 1 到 9 的任何可能的组合。这就是我所需要的。

但我该怎么做呢？我会得到多少种组合？我是否会得到 3 x 9 = 27 个单元格组合，然后得到相同的数字 (N) 组合？

您将如何在经典 C# 循环中解决这个问题？请不要使用 Lambda 表达式，我已经很困惑了:)

代码： 为了代表他们来到这里，我不得不缩短课程时间。

public class Cell : INotifyPropertyChanged
    {

public ObservableCollection<ObservableCollection<Candidate>> CandidateActual {...}

public int Id { ... }

//Position of the Cell inside a box if applicable
public int CellBoxPositionX { get; private set; }  
public int CellBoxPositionY { get; private set; }

//Position of the Cell inside the game board
public int CellBoardPositionX { get; private set; }
public int CellBoardPositionY { get; private set; }

//Position of the Box inside the game board
public int BoxPositionX { get; private set; }
public int BoxPositionY { get; private set; }

public int CountCandidates { ... }    
public int? Value { ...}

public Candidate this[int number]
        {
            get
            {
                if (number < 1 || number > PossibleValues.Count)
                {
                    throw new ArgumentOutOfRangeException("number", number, "Invalid Number Index");
                }

                switch (number)
                {
                    case 1:
                        return CandidateActual[0][0];
                    case 2:
                        return CandidateActual[0][1];
                    case 3:
                        return CandidateActual[0][2];
                    case 4:
                        return CandidateActual[1][0];
                    case 5:
                        return CandidateActual[1][1];
                    case 6:
                        return CandidateActual[1][2];
                    case 7:
                        return CandidateActual[2][0];
                    case 8:
                        return CandidateActual[2][1];
                    case 9:
                        return CandidateActual[2][2];
                    default:
                        return null;
                }
            }
        }
}

候选人

public class Candidate : INotifyPropertyChanged
    {

        private int? _value;

        public int? Value { ... }

    }

盒子：

public class Box : INotifyPropertyChanged
    {

public ObservableCollection<ObservableCollection<Cell>> BoxActual { ... }

public Cell this[int row, int column]
        {
            get
            {
                if(row < 0 || row >= BoxActual.Count)
                {
                    throw new ArgumentOutOfRangeException("row", row, "Invalid Row Index");
                }
                if(column < 0 || column >= BoxActual.Count)
                {
                    throw new ArgumentOutOfRangeException("column", column, "Invalid Column Index");
                }
                return BoxActual[row][column];
            }
        }
}

董事会

public class Board : INotifyPropertyChanged 
    {

 public ObservableCollection<ObservableCollection<Box>> GameBoard {...}

public Cell this[int boardRowPosition, int boardColumnPosition]
        {
            get
            {
                int totalSize = GameBoard.Count*GameBoard.Count();
                if (boardRowPosition < 0 || boardRowPosition >= totalSize) 
                    throw new ArgumentOutOfRangeException("boardRowPosition", boardRowPosition, "Invalid boardRowPosition index");
                if (boardColumnPosition < 0 || boardColumnPosition >= totalSize)
                    throw new ArgumentOutOfRangeException("boardColumnPosition", boardColumnPosition, "Invalid boardColumnPosition index");
                return
                    GameBoard[boardRowPosition/GameBoard.Count][boardColumnPosition/GameBoard.Count][
                        boardRowPosition%GameBoard.Count, boardColumnPosition%GameBoard.Count];
            }
        }



        public Box this[int boardRowPosition, int boardColumnPosition, bool b]
        {
            get
            {
                int totalSize = GameBoard.Count * GameBoard.Count();
                if (boardRowPosition < 0 || boardRowPosition >= totalSize)
                    throw new ArgumentOutOfRangeException("boardRowPosition", boardRowPosition, "Invalid boardRowPosition index");
                if (boardColumnPosition < 0 || boardColumnPosition >= totalSize)
                    throw new ArgumentOutOfRangeException("boardColumnPosition", boardColumnPosition, "Invalid boardColumnPosition index");
                return
                    GameBoard[boardRowPosition / GameBoard.Count][boardColumnPosition / GameBoard.Count];
            }
        }
}

非常感谢您的帮助，

Answer 1

伪代码算法；我的C有点生锈了。

我建议从候选值中找到所有可能的三数组合。可以有 6 到 504 个这样的组合，具体取决于您有多少候选者（由 n!/(3!*(n-3)!) 给出）。

对于每一个，循环遍历单元中的所有单元格，看看它们是否符合条件，即它们没有任何不在您的组合中的数字。如果某个组合有三个或以上，那么就可以应用它。

combos = (array containing 3-long combination of candidates)
for each combo in combos                 # iterate through every combo
  matches = new array                    # initialize a blank array
  for each cell in unit
    if (cell does not contain candidates other than the ones in your current combo)
      matches.add(cell)                  # this is a match!
    end
  end

  if matches.size >= 3                   # naked triple found! (three matches for given combo)
    for each cell in unit
      if (cell is not in matches)
        (delete every candidate in current combo in this cell)
      end
    end
  end
  delete matches                         # clear up memory
end

希望这有帮助！如果您需要的话，我将 C-ify 这段代码；无论如何，我一直想温习我的C。

另外，如果您还不知道，有一种更简单的方法可以使用计算机解决数独难题，而不涉及任何逻辑的手动编程。但我认为你尝试这样做的方式是相当高尚的。

---

生成所有可能的组合的数组

有很多方法可以做到这一点，并且可能有一个最好的方法；我自己还没有对此进行过认真的研究。我推荐谷歌：组合算法...我实际上发现C 中的一个解决方案 我自己。

请务必附上支票，以确保您的候选人数量合适。对于 n=3，只有一种可能的候选组合，您的算法应该为您找到它。对于 n=1 和 n=2，裸三元组甚至不适用。