4

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

然后我将拥有 3 个功能

  • 一是检查水平状态。
  • 另一个检查垂直条件的功能
  • 另一个检查 3*3 块条件。

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

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

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

4

6 回答 6

5

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

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

于 2011-11-11T19:07:22.327 回答
2

对于求解器的基类，我认为以Cell、ValidationRegion、Board和Pattern作为主类是一个很好的开始。

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

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

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

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

于 2011-11-11T19:36:58.613 回答
2

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

直到你知道他想让你建造什么，你才能真正设计出一个解决方案。

于 2014-04-29T17:20:09.823 回答
0

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

ANumberSpace是数独板上的一个方格，可以容纳 1-9 的数字。

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

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

于 2011-11-11T19:10:29.590 回答
0

从这个问题中产生了两个优秀的类，主游戏板和一个持有值的单元格。

在 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 和设计模式解决了复杂的游戏

于 2011-11-11T19:30:38.293 回答
0

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

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

于 2011-12-10T01:48:48.490 回答