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

Question

我回答说我将有一个2d阵列

然后我将有3个函数

• 一个用于检查水平状态
• 检查垂直状态的另一个功能
• 另一个是检查3*3阻塞条件

---

但他并不满意，有人能给这个问题一个好的答案吗

我发现这个堆栈溢出链接与我的问题有关。 Programming Design Help - How to Structure a Sudoku Solver program?

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

Answer 1

对于解算器的基类，我认为Cell、ValidationRegion、Board和Pattern是一个良好的开始

Cell：包含单元格的当前值、单元格的剩余可能值，以及单元格是否固定

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

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

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

Answer 2

如果问题只是“什么是面向对象的数独设计”，而你开始告诉他一些东西，他可能会对你没有要求实际需求感到失望。“数独”的含义相当广泛。只是数据表示？解决方案？玩的方法？验证器？谜题创造者

在你知道他想让你做什么之前，你无法真正设计解决方案

Answer 3

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

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

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块，那么你可能会选择composite设计模式，这将非常适合这个问题。 下面是一个链接，指向一个非常有趣和实用的book解决一个使用OOAD和设计模式的复杂游戏

Answer 5

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

我会说这已经足够了。因为在面试中，你没有足够的时间提出课程的细节，所以也没有必要这样做（至少在典型情况下）

Answer 6

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

ANumberSpace是数独板上的一个正方形，可以容纳1-9之间的数字

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

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