Design Patterns, C#, SQL Server...

Sudoku Game Design

2005-10-26T10:59:00.000-07:00

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.

Designing Sudoku Game

2005-10-24T13:58:00.000-07:00

Do you play Sudoku game? I recently got this on web and addicted to it. The game is fairly simple and its numbers and applying your brain game.

(from WebSudoku.com)

The rules are simple. As you see in the picture, this Sudoku is 9 X 9 matrix.
1. Each row and each column of matrix must be filled with 1 to 9 digits.
2. Each small matrix ( 3 X 3) must also have 1 to 9 digits.
3. You cannot change already filled in digits.

So, in the picture, you start filling the missing digits and also make sure you dont break any rules mentioned above. Its interesting game and becomes difficult as you fill in the slots. Play it when you have free time.

My point to put this game on my post is to design this game. I will post my design and point out why i have used certain design patterns by explaining them. I would like to know how you would design such a game?

Post your comments..

Pattern Resources

2005-10-24T11:43:00.000-07:00

In an effort to collate resources i find useful to learn patterns and to do better design improving day by day, i will start posting the resources in my blog and update it regularly.

Pattern Wiki - a place where you find definitions for GoF patterns and examples. Go through the discussions for each pattern..its an interesting read.

Car Dealer sample - Strategy Pattern

2005-10-24T08:05:00.000-07:00

Prev Post

In the last post, we designed move behaviour of car for our famous DOOP car dealer web site. We observed couple of problems with that particular design. To explain the issue in brief, we had added MoveWithV4, MoveWithV6 kind of methods in base class Car, thinking that we do not need to duplicate code in all deriving classes. But the problem we ended up with is making certain cars move with powerful engines though the car does not actually support the engine. Finally, we thought to externalize or separate the varying behaviour out of Car class. The varying behaviour was Moving car with engine. In this post, lets see how Strategy pattern comes to rescue us from the problems explained above.

Strategy Pattern :

Intent from GoF : Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it.

This means, when you a more than way to implement certain feature or to solve certain problem (call it an algorithm), the client need not be tied to a particular implementation. Client should get flexibility to shift to any other algorithm without being modified. Strategy pattern applies to a design problem where client need to dynamically interchange the algorithms (feature or responsibility implementation) and vary them independently, without being tied to certain way of implementation. UML below describes the strategy pattern.

As you observe, Strategy class defines an interface to access the algorithm. Client is only exposed to Strategy class, and not to the ConcreteStrategy classes which are actual implementations of algorithm. In above notation, client can have reference to more than one concrete implementation, based on the requirement for design. Now you know what is strategy pattern is and what its UML looks like. Lets apply this pattern to our car dealer example's move car behaviour. Take a look at the following UML diagram.

The design shows that we have separated Engine out of Car(no no..we didnt take engine out of the car..we just delegated the move behaviour to engine). Car class has reference to Engine instance and Move method in Car class just calls this.i_Engine.Move. If you observe, we see 2 deriving heirarchies, one for Car and another one for Engine. Car has very deriving subclasses as Corrola, Accord, whereas Engine has V4 and V6. A car instance will be created with a particular Engine. That way, respective engine instance can be passed that particular car instance, such as V4 to Corrola and V6 to Accord. So when you call Car.Move, it calls respective engine's move method. Move behaviour is well encapsulated into Engine class, and its not duplicated. The strategy interface here is Engine class, and V4 and V6 are concrete implementation of strategy class. Dynamically different car types can load different strategy based on their moving behaviour.

Strategy pattern is most widely used pattern. You will find this pattern in various designs and it serves the purpose the best. Other examples of Strategy pattern are listed below.

1. ArrayList.Sort( IComparer ), ArrayList.BinarySearch( IComparer ),
String.Format( IFormatProvider.. )

In all of the above methods, the behaviour of Comparing, formatting is externalized to another class. This provides flexibility to change implementation at runtime dynamically.

2. System.Collections.Generics make heavy use of Strategy.

3. System.Security.Cryptography.

We have seen how to use decorator and strategy patterns in various scenarios. Next we will go over Composite pattern and apply it to car dealer sample. until then..happy patterning..

Car Dealer Design - w/o Strategy Pattern

2005-10-21T08:16:00.000-07:00

Prev post

Continuing series of designing Car dealer example with patterns, my approach is to design without patterns, observe the problems, apply patterns and feel the advantages of patterns. As we have applied this approach to design w/o decorator, with decorator, now we are going to design another feature in car dealer example.

One of the requirements or use cases in car dealer web site design is to show interactive demo and virtual driving experience to user. This involves giving the user some kind of control to make car start, move, accellerate to show how fast it can go (may be something like..this car reaches 0 to 60mph in 5 seconds) and all. So, to support such kind of requirement, we start adding certain methods and properties to various classes in our design. The UML below shows a raw design to support move car feature.

Car speed varies based on its engine that manufacturor uses to build the car. In the design Corrolla, Accord have varying initial moving speeds because former uses V4 and later uses V6. Lets add MoveWithV4 method inside Car class so that any deriving car that uses V4 engine need not have the code duplicated. But the issue is there will be few cars which use V6 engine, and not to duplicate code in all cars that use V6 engine, we can add one more method MoveWithV6 in Car class. Though we achieve the goal of not duplicating code all across, but there is an inherent problem with this design. Some one can call CorollaSedan.MoveWithV6 and get the corrolla move faster. That means, any deriving class can also use the methods which it is not supposed to.

So to get around this problem, we could override MoveWithV6 in CorollaSedan class and throw MethodNotImplemented exception from it. This needs to be done in all deriving car classes which do not support certain methods that exist in their base classes...maintaince overhead. What if a new car comes into the market that uses a very smart engine that makes car fly. So you would either override the respective sub class or put the method in Car class to not to replicate code. we end up in same problem again. To solve this problem, we need to externalize the varying behaviour. The varying behaviour in this example is moving with engine.

In the next post, you will see how Strategy pattern comes to rescue from this kind of problem. stay tuned.

Car Dealer sample - Decorator Pattern

2005-10-20T11:35:00.000-07:00

Prev post

Decorator Pattern :

Intent from GoF : Attach additional responsibilities to an object dynamically. Decorators provide flexible alternative to subclassing for extending functionality.

Decorator pattern allows design to be flexible when there is a need to add responsibilities to an object at runtime, based on configuration or by someother means. The responsibilities could be anything such as, in the car dealer example, the car features will be added dynamically based on customer selection. The UML for decorator pattern is shown below.

The intent is to add features or responsibilities to the component. Each feature or responsibility will be created as a decorator class as shown. The decorator wraps the component class (check the constructor of decorator in UML) and adds the responsibility onto that component. This composition of component class into decorator makes Decorator pattern flexible enough to pass any component (even Decorators because, decorators are also components as they derive from it) and add features over feature over feature...

In car dealer sample, we faced the problem of numerous classes created when we designed car types and each car type supporting various car features. Check my previous post for more details on this. To solve the problem with decorator pattern, we are going to design the system as shown in the following UML diagram.

Above diagram shows 2 sides. One side we have all car types deriving from Car class, and another side car features deriving from a decorator class that intern derives from a Car. Observe that the Decorator class constructor takes in Car instance, which can be any Car ( car type instance or decorator instance too ). Now, lets consider how our design supports the functionality we need.

Our goal is to create a coupe that has All power options, Leather seat and moon roof ( and come what may..). Earlier we had used inheritance and defined a class AllPowerLeatherMoonRoofCoupe. But now, to get a car with such features what we need is this..

myCar = new AllPoweredDecorator( new LeatherDecorator( new MoonRoofDecorator( new Coupe() )));

Remember, the decorator wraps a car instance, that allows me to add one feature at a time to coupe. Similarly, i can add any number of features to any car type dynamically based on what customer selects, and the number of classes in design is small. Observe that car types are completely independent of car features. Adding a new car type or a new car feature does not effect the existing design or code.

So applying decorator pattern solved the problems like tremendously reduced number of classes, flexibility to add features dynamically (you can even add a feature twice to the component..cool haa), eases maintainance.

Few more Examples

1. System.IO namespace in .Net
this.Stream = new BufferredStream( new MemoryStream( new Stream() )));
2. In car dealer example, if we have to add color twice to the car
this.Car = new ColorCoatedDecorator( new ColorCoatedDecorator( new Sedan() )));

Next, we are going to design Car dealer example without and with Strategy Pattern, and observe the advantages. stay tuned.

Pattern examples - Car Dealer Sample

2005-10-19T07:33:00.000-07:00

Prev post

As said in my previous posts, the best way to understand a pattern is to understand the problem without the pattern and then apply pattern to see what issues it solves. In this series of examples to understand how to apply patterns and change the way we think to apply patterns, the first example is DOOP car dealer example. DOOP stands for design patterns and OO (just coined a new acronym to name the example :).

Scenario :

DOOP car dealer sells cars from various manufactorers (such as lexus, toyota, BMW...) to various customers. The dealer wants to set up a website where he can show what cars are in store, display cars, get orders from the customers, order tracking and more. Here are some of use cases that dealer wants to allow customers to do be able to use the web site for.

1. Display list of all cars, along with manufactorer's information.
2. Select a car to view complete information about that car.
3. Display car interactive demo to show customer virtual driving experience with keyboard navigation.
4. Display default features available to the car, and additional features that are available.
5. Display quote (prices) to the customer based on what features he selects for the car.

For now, lets assume the dealer wants to have these use cases implemented in initial iterations (know about iterative development?? lets talk about that later). In this series, we are not going to develop the complete website, but we are only going to design the domain layer of the application by applying design patterns. These domain layer classes then will be used to develop the web site. Considering above requirements, we are ready to start our design. Lets first put design patterns aside and design.

Note : we are not going to design a full fledged project. so classes, their properties, methods are going to limited to purpose of explaining the patterns.

1. Identifying the main classes in our design, the most prominent one is a Car class. We can make this as base class for other derivatives and place some of abstract methods for Car behaviour.
2. As there are going to be different types of cars, such as Coupe ( a 2 door car), Sedan (4 door ), SUV, etc. Each one is based on the body of the car. We can create few deriving classes from Car class as shown in the picture below.

3. There is going to be a separate deriving class for each type of the car. Now, to include support for various additional features for each car such as Leather seats, power windows, moon roof etc.. we start deriving each from the type of the car. To have support for LeatherSeatsCoupeCar, LeatherSeatsSedanCar or AllPoweredCoupeCar or AllPoweredSedanCar, we are going to derive from the respective car type. Check the UML diagram below.

3. Great. We have derived the feature added car from the respective car type. What if i want a coupe with AllPowered, LeatherSeated? No issues. I can derive a class named AllPwdLeatherCoupe from Coupe. Similarly, i would like to do for sedan, SUV or any other car type. Ok fine that works. What if i want a coupe with combination of features such {FeatureA, FeatureB}, {FeatureA, FeatureC}, {FeatureB, FeatureC}, {FeatureA, FeatureB, FeatureC}??? oh..i can support such kind of requirements too. I am going to derive each combination as a separte class. ok. so lets take a look of the design when only 3 features and 3 car types added.

Fine. Did you see the problem with the design? For every car type and every car feature and combination of features, we are going to add classes and increase number of classes. There will be numerous problems with such a design. Maintaining huge number of classes is going to be a nightmare. Each new car type that comes into the market, we need to add a large number of classes to our design to support such new design. Similarly, a new feature to a the car, we gotto add that feature and its combination to all car types. hhaaaaa...lot of problems. How can we solve these problems? When we end up in such kind of mess during design, think of Decorator pattern. My next post is going to explain what Decorator pattern is, and how it solves the problem we have here.

List of GoF Patterns : Overview

2005-10-17T14:27:00.000-07:00

A pattern, as name suggests, denotes a recurring problem in software design and explains its solution in a context. These problem/solution pairs have been applied to the best, time tested solutions that apply to any of such problems irrespective of the field or domain.

Software design pattern deals with how to design classes based on the responsibility, defining their collaborations with other classes. GoF defined 3 categories for the patterns such as Creational, structural and behavioural. Creational patterns deal with who creates the classes and how some of the complicated creation process is encapsulated into certain classes. Structural, as it sounds, deals with class collaborations and associations. Behavioural category is concerned with assigning responsibilities to classes.

Below are the one liners of all the patterns. As i go into details of each pattern, when i explain the DOOP car dealer design (remember? i was referring to DOOP design in my last post), each of these one liners will make more sense.

Creational Patterns -

Abstract Factory : This pattern allows to create family of objects without directly referring to the concrete classes.

Builder : Separate complex process of constructing a product from its representation. Its kind of encapsulating complex creation process and let client need not know about that process.

Factory Method : This is nothing but a method to create certain class instance, but this pattern also lets subclasses override this method to create their flavor of class instance.

Prototype : As name suggests, the class acts as prototype to create other instances of the class. New instances will be constructed or cloned from this prototype.

Singleton : This pattern controls count of instances of a class. Every client request for an instance of the class will be responded with the same instance.

Structural Patterns -

Adapter Pattern : An adapter class acts an adapter (remember socket adapter ??) between 2 parties where their interfaces are incompatible to each other.

Bridge Pattern : Decouples an abstraction from implementation so both can vary independently. Will be more clear when we talk in context of an example.

Composite : Represents part-whole hierarchies and lets client treet a leaf and complex tree uniformly.

Decorator : Add responsibilities to classes at runtime (dynamically), not at compile time.

Flyweight : Use sharing to handle huge number of small objects. Limit creation of the very high number of small objects for performance improvement of the app.

Proxy : acts as proxy for another class and diverts actual calls to the class.

Behavioural Patterns -

Chain of Responsibility - Make client unware of who fulfills the request in the chain of handlers. Avoid coupling between client and ultimate request processor.

Command - exposes an interface various requests and lets client call same interface for different requests.

Interpreter - for given language, defines grammer and an interpreter to interpret that language.

Iterator - as name suggests, provides a way to iterate over collections.

Mediator - acts as mediator between 2 parties and encapsulates how these parties interact.

Memento - lets capture and store objects internal state (without violating encapsulation ofcourse), and let the class come backto that state when required (such as serialization..)

Observer - defines dependency between objects, so that when object's state changes, other objects get notified.

State - a pattern that shows the state changes of an entity.

Strategy - dynamically vary or change the algorithms without modifying the client. examples will follow.

Template method - Defines an interface method and certain template methods in base class. The pattern lets subclasses override the template methods such that the actual interface method implementation changes.

Visitor - visitor lets an operation on an object structure. it allows new operations to be defined on that structure w/o changing old operations.

In coming post, i will directly jump into DOOP car dealer design and apply some of these patterns to the design to see what problems these patterns solve.

Design Patterns Tutorial

2005-10-11T13:42:00.000-07:00

To start over, i am going to begin blogging on Design patterns, starting with Gang Of Four. The way i am going to approach is to pickup an example of the sample real world project and design without patterns, and explain the pains without using the patterns. And next refactor the design using patterns one by one to make it better design.

In the forth coming sessions, we will design a web site for a fictitious car deeler named DOOP. no, its not dupe. its DOOP.. short and mixed form of Design Patters and OO. Before we start making actual requirement analysis, design without and with patterns, you may want to understand what design patterns are all about and how to go about using them.

Here are some online catalog of patterns.
http://patternshare.com/
http://www.dofactory.com/Patterns/Patterns.aspx

Few books i recommend :
Design Patterns by GoF
Head First Design Patterns