Interview question: Create an object oriented design for Sudoku

Question

I answered that I will have have a 2d Array.

And then I will have 3 functions

• one to check the horizontal condition.
• another function to check vertical condition
• and another one the check the 3*3 block condition.

---

But he is not satisfied, can any one give a good answer for this question?

I found this stack overflow link related to my question. Programming Design Help - How to Structure a Sudoku Solver program?.

But I want a proper object oriented design (like what should be the classes, inheritance and other details) which are the same things interviewer expected from me.

Answer 1

To me, your design starts with a "region" class. You can then extend this to be a "horizontal region" "vertical region" and "square region" as the three types of regions. Edit: upon further consideration you don't really need to make this distinction unless it's for display purposes... algorithmically it will be the same.

Then you can make your 2d array of "elements" and add the elements appropriately to your regions, which provides a network for your calculations. Your elements have a list of potential values, and your regions are responsible for removing those potential values. When you have a value found, it triggers the regions it is a member of to remove the potential values from those too.

Answer 2

For base classes of a solver, I see a good start with Cell, ValidationRegion, Board, and Pattern as your main classes.

Cell: Has the current value of the cell, the remaining possible values of the cell, and if the cell is fixed or not.

ValidationRegion: Has references to the appropriate 9 Cells on the Board. This class doesn't really need to know if it is representing horizontal, vertical, or a square regions, because the rules are the same. This class has a validate() method to verify that the current state of the region is possible.

Board: Has the entire layout of Cells, and initializes the fixed ValidationRegions appropriately by passing the appropriate Cells by reference. It also has a solve method that applies Patterns in a pre-defined order until a solution is reached or it is determined that no solution is possible (brute-force pattern must therefore be the last ditch effort).

Pattern: Abstract class that has an apply(Board) method that applies the given pattern to the specified board object (removes possibilities from Cells and sets them when it knows there is only one possibility left). From Sudoku Dragon - Sudoku Strategy, you'll likely implement patterns like OneChoicePattern, SinglePossibilityPattern, OnlySquareRule, etc.

Answer 3

If the question was just "What's an object-oriented design for Sudoku" and you went off and started telling him stuff, he may have been disappointed that you didn't ask for actual requirements. "Sudoku" is pretty broad. Just a data representation? A solver? A means to play? A validator? A puzzle creator?

Until you know what he wanted you to build, you can't really design a solution.

Answer 4

For an Object-Oriented approach to Sudoku I'd do something like this (just using simple names):

A NumberSpace is a single square on the Sudoku board and capable of holding a number from 1-9.

A Block is a grouping of 9 NumberSpaces in a 3x3 pattern, Which would probably just be represented in the class as a multidimensional array of NumberSpace objects. Methods on this could include (bool)validate which would test to make sure no number is repeated per block.

Finally, a Board would represent the entire gaming area where which would be another array (3x3) of Blocks. Methods for this class would include means for verifying the validity of columns/rows.

Answer 5

Two outstanding classes raise from this problem, the main game board and a cell holding a value.

In C#, this would be:

// 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
   }
}

If you wish to consider the 3*3 block then you might go for the composite design pattern which will fit this problem very well. Here is a link to a very interesting and pragmatic book resolving a complex game using OOAD and design patterns

Answer 6

I am not sure about this, but I have a feeling that the interviewer probably wanted something like MVC pattern etc, a high level design/architecture. Then, within this context, you will have three modules/components: model, view and controller. Each of which is then made up of one or more classes. For most interactive applications, this pattern or some variation/related pattern is applicable.

I would say this would have been enough. Since, in an interview you don't have enough time to come up with details of classes, neither it is necessary to do so (at least in typical cases).