Common problem solver framework design

[AceKnocks]

I am working on a framework design problem in which I have to design a C++ based framework capable of solving three puzzles for now but actually it should work with a general puzzle of any kind and I need your able help in this activity.

Objective -

In this activity you will design a framework capable of solving any puzzle of a specific type and, as a test of this framework, use the framework to solve a very simple puzzle. In this first activity, you are mainly concerned with the design of the framework. The term framework means a set of classes that enable implementation of solutions to certain problems. However, the framework by itself is not a complete program. You will work with abstract notions such as configuration, goal, and find-next-configuration. The problem solver should be able to solve any problem that conforms to an interface that you develop in your design. Think carefully about this interface, as you will also have to write classes that conform to it to solve the four problems (as of now only three are given, and the fourth would be given just few days before - to be integrated in the remaining time).

Your design document is a text file that contains a description of the framework that will solve puzzles. It should include a description of the classes and the public methods that the client uses to solve puzzles. This description should explain how the solver will solve puzzles. It is important to realize that the solver must be capable of solving any puzzle and must contain all of the puzzle-solving machinery. The individual puzzles should not contain any puzzle-solving machinery but only contain methods implementing the rules for a particular puzzle. You do not need to design a general puzzle rule mechanism as each puzzle can explicitly code the possible successor states to any (legal) puzzle configuration.

These are three different puzzle problems as 1, 2 & 3.

Problem 1: A clock' batteries have gone bad and thats why the clock is showing wrong time (slowed down time) when compared to the current time. The clock only has hour hand and if the current time is 4 and the true time is 12, we need to turn the hour hand to make it 12. The objective is to find the shortest number of moves for the hour hand at 4 to show 12. In this case, which is, 4 moves (instead of 8 moves when going the other way from 4 to 5, then 5 to 6...and so on from 11 to 12).

Problem 2: This puzzle has four entities and they are Carpenter, Wolf, Goose and Corn. All of them have to cross a river and there is only one boat which can carry atmost 2 entities at any point in time. Of course, if the wolf is left alone with the goose and also, if the goose is left alone with the corn both of them with eat the latter. The objective here is to allow all four of them cross the river unharmed.

Problem 3: This is a one-person game played on a rectangular grid of lamps which can be turned on and off. A move consists of flipping a "switch" inside one of the squares, thereby toggling the on/off state of this and all four vertically and horizontally adjacent squares. The goal of this problem is to find a way to wind up with a specific number of lights turned on, while keeping in mind that you are "forbidden" to turn certain lights on or off. Sort of a similar problem is defined here http://mathworld.wolfram.com/LightsOutPuzzle.html.

This is what I have thought about the solution till this point -

There will be a base class which will create a tree to store objects of a particular problem (for e.g. prob 1).. I am using tree here because the problem could have multiple solutions and we need to provide all solutions to the given problem

There will be a config file which will have all possible states for a particular problem such as all possible states for problem 1 would be 12 (or states) 1, 2, 3….to 12. All possible states for problem 2 would be different combinations for carpenter ( ca), goose (g), wolf (w) and corn (c ) such as initial state would be (ca, g, w, c). Next valid state could be (w, c) if the ca takes the g to the other side of the river and so on.

We only have to solve one problem at one execution of the program. Given an initial state for a specific problem the base class' goal would be to find the goal (or target state). Assuming for pblm 1 the current time is 4 and true time is 12 then these are initial and target states. For pblm 2, target state would be (-, -, -, -) i.e. none of the entities are present on this side of the river.

There will be a rules file, which the base class will use to check if the next state (generated by the base class) is actually valid according to the problem specifications or not. Assuming for pblm1, the current time is 4 and true time is 12 then we can either move right i.e. from 4 to 5, 5 to 6..and so on from 11 to 12 OR we can move left i.e. 4 to 3, and so on from 1 to 12.. the rules file will ensure that either we'll chose left or right we are only allowed to move one unit i.e. 4 to 5 or 4 to 3..not 4 to 6 or 4 to 2. Similarly for pblm2, it will make sure that goose and corn are not left behind on any side of the river un-attended..

I am not sure after that.. still thinking..

I am not looking for any implementations or anything of that sort. However, any hints to the possible approaches for the framework design will be of great help. I have not worked on any framework design ever before. Any url's for the framework design will also be of help. I am searching online also but till now I could not find any specific help online regarding the design approaches.

Please help.

[oler1s]

So, let me get this right. Your approach to writing a generic framework for certain types of puzzles is to encode every possible question the framework could possibly have to solve, you are going to store all solutions to each of those questions. Does this not strike you as...unscalable?

Perhaps you should find a generic algorithm.

I have not worked on any framework design ever before

Did you not just go through an entire class?

[Savage]

So, let me get this right. Your approach to writing a generic framework for certain types of puzzles is to encode every possible question the framework could possibly have to solve, you are going to store all solutions to each of those questions. Does this not strike you as...unscalable?

Perhaps you should find a generic algorithm.

Did you not just go through an entire class?

Sure is unscalable,but writing and implementing generic algorithm might be just to hard.After all,he is allowed to write rules,and this is supposed to be a FSM(finite state machine) after all(i think)

Savage

[weaknessforcats]

This is exactly where you use a factory to generate the puzzle object.

That is, a Maze object might be generated by a MazeFactory. Then later when you need to open doors using a magic spell, you derive EnchantedMazeFactory from MazeFactory to produce an EnchantedMaze object. Next you derive an Enchanted Maze from Maze and you hide (by using domination) the Maze::Open with EnchantedMaze::OpenDoor(string& theSpell).

You will never create the framework you seek.

The above is the exact example for the Factory pattern from Design Patterns by Erick Gamma, et. al.

[AceKnocks]

So, let me get this right. Your approach to writing a generic framework for certain types of puzzles is to encode every possible question the framework could possibly have to solve, you are going to store all solutions to each of those questions. Does this not strike you as...unscalable?

Perhaps you should find a generic algorithm.

Did you not just go through an entire class?

No, my intent is of course not to encode specific class for a specific problem as I will be completely ignoring the primary objective of designing a generic framework (not the specialized classes).

Well, as my objective says that the solver must be able to process all given problems, though on an abstract level. It will not have any specific knowledge about the specific puzzle because according to me the specialized classes will only be able to provide (or validate) all valid states for the problem.

The base class, on the other hand, can either generate (or validate, if specialized classes are not doing it) the valid states for a problem.

Based on every generated state, the algorithm will first validate the state, then add a node in the graph so as to keep track of all possible solutions. The algorithm ends when either there are no valid states left for a problem or we reach the goal state through any of the paths from the initial state (root node) to goal state (target node). Of course the initial and goal state will be provided by the user.

These states, I am talking about, could be string (or binary representations) for a given state (configuration) coming from the following idea.

There will be a config file which will have all possible states for a particular problem such as all possible states for problem 1 would be 12 (or states) 1, 2, 3….to 12. All possible states for problem 2 would be different combinations for carpenter ( ca), goose (g), wolf (w) and corn (c ) such as initial state would be (ca, g, w, c). Next valid state could be (w, c) if the ca takes the g to the other side of the river and so on.

We only have to solve one problem at one execution of the program. Given an initial state for a specific problem the base class' goal would be to find the goal (or target state). Assuming for pblm 1 the current time is 4 and true time is 12 then these are initial and target states. For pblm 2, target state would be (-, -, -, -) i.e. none of the entities are present on this side of the river.

There will be a rules file, which the base class will use to check if the next state (generated by the base class) is actually valid according to the problem specifications or not. Assuming for pblm1, the current time is 4 and true time is 12 then we can either move right i.e. from 4 to 5, 5 to 6..and so on from 11 to 12 OR we can move left i.e. 4 to 3, and so on from 1 to 12.. the rules file will ensure that either we'll chose left or right we are only allowed to move one unit i.e. 4 to 5 or 4 to 3..not 4 to 6 or 4 to 2. Similarly for pblm2, it will make sure that goose and corn are not left behind on any side of the river un-attended..

I am not entirely sure how to first generate a state for a given problem and then validate it afterwards.

Are there any URL's for designing a generic framework? or any UML design approach to a framework?

[AceKnocks]

This is exactly where you use a factory to generate the puzzle object.

That is, a Maze object might be generated by a MazeFactory. Then later when you need to open doors using a magic spell, you derive EnchantedMazeFactory from MazeFactory to produce an EnchantedMaze object. Next you derive an Enchanted Maze from Maze and you hide (by using domination) the Maze::Open with EnchantedMaze::OpenDoor(string& theSpell).

You will never create the framework you seek.

The above is the exact example for the Factory pattern from Design Patterns by Erick Gamma, et. al.

Thanks for your pointer towards factory method design pattern. I have just started reading about it online. It could as well prove to be a solution to my objective. Let me skim through this topic for some time to allow me to gain some basic understanding about its possible implementations.

[AceKnocks]

This is exactly where you use a factory to generate the puzzle object.

That is, a Maze object might be generated by a MazeFactory. Then later when you need to open doors using a magic spell, you derive EnchantedMazeFactory from MazeFactory to produce an EnchantedMaze object. Next you derive an Enchanted Maze from Maze and you hide (by using domination) the Maze::Open with EnchantedMaze::OpenDoor(string& theSpell).

You will never create the framework you seek.

The above is the exact example for the Factory pattern from Design Patterns by Erick Gamma, et. al.

After reading Abstract Factory Design Pattern, it looks like I can make use of it to atleast abstract the object creation mechanism from the specialized classes to just a factory class.

Abstract Factory Design Pattern will help me create the generic and centralized object creation mechanism whereby the client (specialized classes) requests the object factory (base class) to create objects of a generic type, though the factory class has access to the configuration rules repository where some kind of indication is given which class' object has to be created. This base class then creates a generic object capable of calling methods from the specialized class and then solve it from there.

As for searching these objects, I can utilize a Breadth First Search Graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it can explore their unexplored neighbor nodes, and so on, until it finds the goal. Of course the goal is our final state and the root node is our initial state.

Can any one suggest a possible approach towards generating these states for a given puzzle? Will the states be represented in a string form or a binary representation of 1's and 0's..to represent a particular state for a problem?

How to configure this state generation and validation mechanism?

As the objective is pretty clear in terms of designing a common problem solver framework, I guess the specialized classes can have the rules for state validations and informing the base class whether its a valid state or not. On the other hand, the factory class will generate all possible states from the initial state and gets it validated from the specialized class.

But how to generate these states?

There are few more patterns like Prototype, Builder, and Singleton. I am going to explore these now.

[AceKnocks]

Sure is unscalable,but writing and implementing generic algorithm might be just to hard.After all,he is allowed to write rules,and this is supposed to be a FSM(finite state machine) after all(i think)

Savage

I missed reading this reply earlier. From the given keyword "FSM", I went through FSM and came across Turing Machine described at http://en.wikipedia.org/wiki/Turing_machine.

What attracts me towards Turing machine, is its ability to store -
- all finite set of states
- a transition function
- the initial state
- final state

Now for pblm2, I can store all possible states of the Carpenter (C), Wolf (W), Goose (G) and Corn (K) from one side of the bank to another side of the bank of the river, at any point in time. These states will be stored in a rules file which will actually hold all possible states for a given problem. The rules file will also store the validation checks to ensure that the solver is not processing any illegal state, after all.

Well, we already know which states we would need to solve pblm2 -

One side of the bank (S) ----> Transition --------> Other side (D)
C(S), W(S), G(S), K(S) F(D), G(D) G(D)
C(S), W(S), K(S) F(D), W(D) W(D)
C(S), G(S), K(S) F(D), K(D) W(D), K(D)
C(S), G(S) F(D), G(D) C(D), W(D), G(D), K(D)

For pblm2, we have 4 entities and there'll be 2^4 different combinations for <C,W,G,K>, flipping each of these for a S or a D atomic state. The base class still gets to create the graph from the root node and keeps on exploring the rest of the states in the rules file, after validating them.

In pblm1, we have only 12 possible states 1, 2, 3...12.. out of which there will be one initial and one target state.

I am still not sure how to think about pblm3 in these terms.

Thanks for all your inputs.

[AceKnocks]

Well, the update about this problem is that I have finished designing my solver for problem 2 and now I am starting off to integrate problem 1 now with my solver.

The solver as objective requires, should be able to solve any kind of problem depending upon the states validated by the specialized classes' rules and for me, it is working beautifully. :)

Once I will finish integrating the complete three (with the fourth one unknown, as it will be given just few days before submission) problems, I will post it for everyone's feedback.

[weaknessforcats]

What attracts me towards Turing machine, is its ability to store -
- all finite set of states
- a transition function
- the initial state
- final state

Read the article in the C/C++ HowTos on the State Design Pattern.