面试问题：为数独创建面向对象的设计

Question

我回答说我会有一个二维数组。

然后我将有 3 个功能，

• 其中之一是检查水平状态。
• 另一个函数用于检查垂直条件
• ，另一个函数用于检查 3*3 块条件。

---

但他并不满足，这个问题有谁能给出一个好的答案吗？

我发现这个堆栈溢出链接与我的问题相关。 编程设计帮助 - 如何构建数独求解器程序？ 。

但我想要一个适当的面向对象的设计（比如应该是类、继承和其他细节），这与面试官对我的期望是一样的。

Answer 1

对我来说，您的设计从“区域”类开始。然后，您可以将其扩展为“水平区域”、“垂直区域”和“方形区域”这三种类型的区域。编辑：经过进一步考虑，您实际上不需要进行这种区分，除非是出于显示目的......从算法上讲，它是相同的。

然后，您可以制作二维“元素”数组，并将元素适当地添加到您的区域，这为您的计算提供了一个网络。您的元素有一个潜在值列表，您的区域负责删除这些潜在值。当您找到一个值时，它会触发它所属的区域，以从这些区域中删除潜在的值。

Answer 2

对于求解器的基类，我认为 Cell、ValidationRegion、Board 和 Pattern 是一个良好的开端，如下所示你的主要课程。

Cell：具有单元格的当前值、单元格的剩余可能值以及单元格是否固定。

ValidationRegion：引用了 Board 上相应的 9 个Cells。这个类实际上不需要知道它是否表示水平、垂直或正方形区域，因为规则是相同的。此类有一个 validate() 方法来验证该区域的当前状态是否可行。

Board：具有Cells的整个布局，并通过引用传递适当的Cells来适当地初始化固定的ValidationRegions 。它还具有一个 solve 方法，该方法以预定义的顺序应用Patterns，直到达到解决方案或确定不可能有解决方案（因此，暴力模式必须是最后的努力）。

Pattern：具有 apply(Board) 方法的抽象类，该方法将给定的模式应用于指定的板对象（从 Cells 中删除可能性并设置当它知道只剩下一种可能性时）。从 Sudoku Dragon - Sudoku Strategy 中，您可能会实现类似 OneChoicePattern 的模式， SinglePossibilityPattern、OnlySquareRule 等。

Answer 3

如果问题只是“数独的面向对象设计是什么”，而您开始告诉他一些东西，他可能会因为您没有询问实际需求而感到失望。 “数独”的范围相当广泛。只是数据表示？求解器？一种玩的手段？验证器？谜题创造者？

在您知道他希望您构建什么之前，您无法真正设计解决方案。

Answer 4

对于数独的面向对象方法，我会这样做（仅使用简单的名称）：

NumberSpace 是数独板上的单个方块，能够容纳 1-9 之间的数字。

Block 是 3x3 模式中 9 个 NumberSpace 的分组，它可能在类中表示为 NumberSpace 的多维数组对象。相关方法可能包括 (bool)validate ，它将进行测试以确保每个块没有重复的数字。

最后，Board 将代表整个游戏区域，其中将是另一个 Block 数组 (3x3)。此类的方法将包括验证列/行有效性的方法。

Answer 5

这个问题引发了两个突出的类，即主游戏板和保存值的单元格。

在 C# 中，这将是：

// Main game board
public class BoardGame{
   List<List<Cell> cells = new List<List<Cell>>();
   public BoardGame(int dimention){
      // Initialize and add cells to the cells attribute
   }
   public bool HorizLineContainsValue(int lineNumber, value){
      // return true if any cell in horiz. line number contains value
   }
   public bool VertLineContainsValue(int lineNumber, value){
      // return true if any cell in vertic. line number contains value
   }
}
public class Cell {
   // X index on the game board
   public int X{get; set;}
   // Y index on the game board
   public int Y{get; set;}
   // Value of this cell
   public int Value{get; set;}
   // Set game board 
   public GameBoard GameBoard{set;}
   public boolean AcceptValue(int value){
        // Ask the game board if cells on horizontal line X have this value
        // Ask the game board if cells on vertical line Y have this value
        // And return true or false accordingly
   }
}

如果您希望考虑 3*3 块，那么您可能会选择 composite 设计模式非常适合这个问题。
这是一本非常有趣且实用的书的链接，该书使用解决复杂的游戏OOAD 和设计模式

Answer 6

我对此不太确定，但我有一种感觉，面试官可能想要 MVC 模式等高级设计/架构。然后，在此上下文中，您将拥有三个模块/组件：模型、视图和控制器。其中每个类都由一个或多个类组成。对于大多数交互式应用程序，此模式或某些变体/相关模式是适用的。

我想说这已经足够了。由于在面试中您没有足够的时间来提出课程的详细信息，因此也没有必要这样做（至少在典型情况下）。