Sudoku Game Design

In previous post, I introduced Sudoku game and wanted to design to see what patterns will fit into it. Here are few use cases using which we will design the game.

1. Display Sudoku Board to the User : user selects board size (3x3 or 9x9 or anyother), and difficulty level (easy, medium or difficult).
2. View result of the game : Once user plays the game, he would like to get game result. If he succeeded in completing it or not.

keeping these use cases in mind, here is a UML diagram showing the design.

(click on image and open it in a new window to see it bigger).

1. Lets start with the design. To develop a game like Sudoku, we need to identify the classes that we have to put in the design and assign responsibilities to them. The most prominent entities in the game are Game Board, Cell or Box, number.

2. So we draw 2 classes as Digit, Box. As shown in the diagram, a Digit instance will have a numeric value ( 0 to 9 ) and a get/set methods to access this numeric property.

3. Box class represents a cell in the board. Each box will either have a Digit filled in or it will be empty. If a Digit is already filled, the cell will not be editable right. An empty cell hides the actual digit in it allowing user to type in a value. Each cell should be smart enough to validate itself based on what user enters.

4. Every cell will validate itself it the user entered a correct value in it. Similar validation applies to smaller matrix (3x3) and also to the complete game board. So we need a way to abstract client from a cell or a small matrix or a complete game board. Client, based on it needs, can ask a cell or small matrix or a game board to validate it self and give the result. This sounds like Composite pattern. A composite pattern lets client treet a leaf and complex tree uniformly. Client should not be aware wether it is talking to a cell, matrix, or a board.

5. Thinking about composite pattern, lets create an AbstractBox class that will just have IsEditable, IsValid abstract methods. Now, lets create AtomicBox (you could name it as Cell) that derives from AbstractBox. Since AtomicBox should be able to have information like the actual number, user entered number..lets create two properties to hold these values. Only user entered digit property will have get/set methods. If you observe, these two properties are instances of Digit class.

6. As in composite pattern, Lets create one more class CompositeBox which will be a collection of AbstractBoxes. An obvious field for this class will Boxes. Lets create 1 more classe as SquareBox to represent a square matrix deriving from CompositeBox class (as shown in the diagram). Though there is no current need to create a CompositeBox class, instead we directly create SquareBox deriving from AbstractBox, lets have the CompositeBox for future.

7. So we successfully used a Composite pattern in our design. Whats the advantage we get out of it? One, client need not know about AtomicBox, SquareBox. All it needs a reference to AbstractBox class and its interfaces. Another advantage is, SquareBox need not know about its internal structure. As our use cases say, a Sudoko board can be of any size (3x3 or 9x9 etc). So a SquareBox will be collection of SquareBoxes of smaller sizes and each of smaller SquareBox can also be a collection of SquareBoxes or finally leaf nodes which are AtomicBoxes. This kind of abstraction is possible with Composite pattern. The best advantage is when we have to validate a SquareBox, it just needs to ask if the child boxes are valid. And each child box will ask their children and so on... if any of these children return false, that means the whole board is wrong and game is incomplete.

8. Did you observe that we created a Digit class that just holds a numeric value? Isnt that too much information that a class can have? ( :-)..i am just kidding). The reason why we created a Digit class is to have centralized control over the numbers, make comparision easy and also to abstract working with numbers. This reduces code that that deals with integers all over the project, had it been implemented with numbers. You would say that having a Digit class will kill the application performance because of number of instances of Digit classes is going to be more based on size of the board, and we are also maintaining actual digit vs user entered digit??? Yes. this is going to be problem with performance. We have to reduce the number of instances of Digit classes somehow.

9. Think of Flyweight pattern. Yes. Flyweight pattern lets reduce number instances by making instances sharable. Ok. Lets create a class to handle this sharing business. A class named DigitsFlyweight will serve our purpose. It will maintain a list of Digits ( 0 to 9 ) and also an interface to return a Digit instance for given integer. DigitFor method will check if an instance for ths integer already exists, if so, its going to return same instance or else it would create an instance and return that.

10. Till now, we have Digit, AtomixBox, SquareBox in place. But we need someone to construct Sudoku Board. As you would have observed, the sudoku board will be an instance of SquareBox. Based on the size of the board user selects, we need to construct that kind of SquareBox and its composite structure. We need some one build the composite structure.

11. Think of Builder pattern. A builder pattern separates construction of complex product from its representation. Most of the times, a builder will build composite structures, meaning builder pattern and composite pattern will be used together. Lets create a class named SudokuBoardBuilder that builds an instance of SquareBox based its size. Builder needs to know how many instances of AtomicBoxes, how many instances 3x3 SquareBoxes and how many instances of 9x9 SquareBoxes it needs to create for a 9x9 board.

12. Builder creates all AtomicBoxes on the board right. But each atomic box needs a Digit to make the game. Thats the interesting part of the actually creating a game. You need to be a game creator to create a sudoku kind of game. Your approach would be like, place all numbers in a big matrix and start hiding few of the numbers to make game difficult to solve. This is kind of algorithm or logic to create a sudoku game. So when i say algorithm or logic, there will be many implementations from various people. Our design should be extendable to easily change algorithms without needing changes to existing classes. We should dynamically change algorithms at runtime (not at compile time).

13. Think of Strategy pattern. It lets vary algorithms dynamically at runtime. So, lets separate logic of game creation from Builder class and delegate it to a strategy. Lets create an interface named ISudokuProvider with few methods to create a new game, get digit at certain cell, and also to find out if that value needs to be hidden. The concrete implementations of ISudokuProvider interface will talk to any algorithm that creates a sudoku game. Our builder class will have an instance of ISudokuProvider and will use it to build sudoku board. Builder class does not need to have direct reference to a concrete implementation. To make it work, we will have the concrete implementation's type name configured in any config file and load it from there.

This makes our design complete. As per use cases, our design allows varying sizes of sudoku boards. But we missed to include difficulty level. That should be simple. We should pass a difficulty level to strategy when we call NewGame method on it. Now, we can develop a client that uses this domain model to implement sudoku game.