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

Question

我回答说我将会有一个二维数组，并且接下来将会有三个函数。一个用于检查横向条件，另一个用于检查纵向条件，还有一个检查3*3块的条件。

但是面试官并不满意，有没有人能给出这个问题的好答案？

我发现了这个与我的问题相关的stackoverflow链接：Programming Design Help - How to Structure a Sudoku Solver program?。

但是我想要一个合适的面向对象设计（例如应该有哪些类、继承和其他细节），这也是面试官对我的期望。

- javaMan

Answer 1

对我而言，您的设计始于一个“region”类。然后，您可以将其扩展为“水平区域”、“垂直区域”和“正方形区域”作为三种类型的区域。编辑：经过进一步考虑，除非是为了显示目的，否则您不需要进行此区分...在算法上它是相同的。

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

- corsiKa

Answer 2

如果问题只是“数独的面向对象设计是什么”，而你却开始讲述其他内容，他可能会失望，因为你没有要求实际需求。 "数独" 是非常广泛的。仅仅是数据表示？解决器？玩游戏的手段？验证器？谜题创造者？

在你了解他想要你构建什么之前，你无法真正设计出一个解决方案。

- Risser

Answer 3

对于求解器的基类，我建议以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”等模式。

- Briguy37

Answer 4

这个问题引出了两个优秀的类，一个是主游戏板，另一个是保存值的单元格。

在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块，则可以选择组合设计模式，这将非常适合解决此问题。 这是一个链接到一个非常有趣和实用的书籍，使用OOAD和设计模式解决复杂游戏的问题。

- GETah

Answer 5

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

我认为这就足够了。在面试中，您没有足够的时间来详细说明类的细节，也不需要这样做（至少在典型情况下不需要）。

- Nazar Merza

Answer 6

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

一个NumberSpace是数独棋盘上的一个单独方格，能够容纳1-9的数字。

一个Block是由9个NumberSpace组成的3x3模式的分组，可能只是在类中表示为NumberSpace对象的多维数组。该类的方法可以包括(bool)validate，用于测试确保每个块内没有重复数字。

最后，Board将代表整个游戏区域，这将是另一个数组（3x3）的Block。该类的方法将包括验证列/行有效性的手段。

- Brandon Buck