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.