My sudoku program, any comments, improvements appreciated

dumas · 2009-12-13 11:23:10

Hi all,

So I've been refining my amateur-ish programming skills for around a month, and have been writing a C++ program that solves sudoku. (My background is in physics.) I realize there are a lot of mathematical sides in sudoku, but I'm concentrating on the programming side and not too much on the math/brain side. Now the program is basically finished (I hope!) and I just thought the hackers here can have a look and see if there are any things I can improve.

The link is here: http://ifile.it/jkr56v8/Sudoku.tar

Basically, a sudoku is an instance of Board, an abstract base class with the pure abstract function Go(). Any concrete class derived from it is essentially a strategy. I think this design pattern is called strategy?

I've implemented two basic strategies, BruteForce and Priority. BruteForce does the good old sudoku brute force algorithm, which use trial-and-error from the top left box to the bottom right box all possibilitiies until the correct one is found. Priority does basically the same as BruteForce, except instead of trying from top left to bottom right, it plugs numbers in the box that has the most filled "associated" boxes.

To accommodate "composite strategies," I implemented the prototype pattern, so for example, I can write

void HyperBF::Go(void)
{
    BruteForce::Go();
}

When a solution is found, I throw an exception to notify the main program, am I correct in that this is a clear and elegant use? Or is it a misuse and an alternative should be considered?

To actually choose a strategy, I created an abstract factory, a singleton. I'm aware there are all the advice out there that says don't use a singleton unless absolutely necessary? So, should I use a singleton in this case? Also, I think my implementation of the singleton leads to a bug, which is the only known bug: when I put a completed sudoku as input, it gives the output as usual, but gives a segmentation fault afterwards:

./Sudoku Puzzle/test_1_Basic.psv BruteForce | tail -n 12 | head -n9 | tee completed

|5|1|8|2|9|6|7|3|4|
|3|9|7|8|4|1|2|6|5|
|6|4|2|5|7|3|1|9|8|
|1|5|6|4|2|7|3|8|9|
|4|7|9|3|6|8|5|1|2|
|8|2|3|9|1|5|6|4|7|
|7|8|4|1|3|2|9|5|6|
|2|3|5|6|8|9|4|7|1|
|9|6|1|7|5|4|8|2|3|

./Sudoku completed BruteForce

Starting configuration:
|5|1|8|2|9|6|7|3|4|
|3|9|7|8|4|1|2|6|5|
|6|4|2|5|7|3|1|9|8|
|1|5|6|4|2|7|3|8|9|
|4|7|9|3|6|8|5|1|2|
|8|2|3|9|1|5|6|4|7|
|7|8|4|1|3|2|9|5|6|
|2|3|5|6|8|9|4|7|1|
|9|6|1|7|5|4|8|2|3|

Final configuration:
|5|1|8|2|9|6|7|3|4|
|3|9|7|8|4|1|2|6|5|
|6|4|2|5|7|3|1|9|8|
|1|5|6|4|2|7|3|8|9|
|4|7|9|3|6|8|5|1|2|
|8|2|3|9|1|5|6|4|7|
|7|8|4|1|3|2|9|5|6|
|2|3|5|6|8|9|4|7|1|
|9|6|1|7|5|4|8|2|3|

Number of attempts: 0.
Time elapsed: 0.00 s.
Segmentation fault

So what's wrong here?

Having implemented the basic functionalities, I tried to play around and gain some simple experience in some optimization. I looked at the Go() function and saw probably the expensive operation is IsConsistent(), so I optimized it by only checking the consistency of changed boxes. By doing so, I reduced the computational time to around 1/3 the original time. Is this the right move, or bad move, or are there better moves?

As a last question, I defined the number of attempts as a global variable. My reason is that, although it is possible to put it in class Board, I just think it doesn't "naturally belong" there, and putting it in a restricted scope would mean a lot of passing of parameters, slowing the program down unnecessarily. So, is this global variable fine?

Lastly, please have a look at my Makefile. This is the first Makefile I wrote, and it took me 3 solid days to get all the .o files in Release/ ! Are there things I've left out?

I realize the Generator is a joke, but at this moment I don't care too much about that, unless anyone has some good ideas.

Any comments would be greatly appreciated! Thanks in advance!

ewaller · 2009-12-14 21:39:27

I downloaded it and will look at it this evening.

I made a brief first pass through it. My first impressions:

No, I would not advocate throwing an exception in the normal flow of a program. In my mind, exceptions should be just that -- deviations from the ideal path.

Second, since this is an exercise in C++, you might look into using iostreams instead of the more C-like printfs.

Grazz256 · 2009-12-15 01:28:18

I made a sudoku solver in python not to long ago.. Mind you I made mine cause I'm not smart enough to solve the puzzles hehe

I would look into gdb, it will give you a trace of your program where the segfault happens so you can figure out whats causing it.

Cheers,
Jon Estey

dumas · 2009-12-15 11:59:41

ewaller wrote:

I downloaded it and will look at it this evening.
I made a brief first pass through it. My first impressions:
No, I would not advocate throwing an exception in the normal flow of a program. In my mind, exceptions should be just that -- deviations from the ideal path.
Second, since this is an exercise in C++, you might look into using iostreams instead of the more C-like printfs.

Thanks ewaller.

Is your opposition for throwing an exception purely because of "convention?" If that's the case I basically agree, but I think Stroustrup, in his book "The C++ Programming Language" said in certain cases throwing exceptions in non-error contexts might be good idea. I had a brief thought about alternative ways of coding the flow of winning, but I think the coding would basically replicate the throwing of an exception? What would you propose as an alternative?

As for iostreams and printfs, I used to use iostreams a lot, but now I just find printfs to be more attractive to me. Are you proposing iostream due to more of a computer science reasoning? I guess the difference between iostream and printf is that with iostream I would get to do things the object-oriented way, overload the cout and cin operator for Board and such? But would that, in the end of the day, just be a matter of "ideology," since I'm inheriting and overloading the Board::Read() and Board::Write() methods anyway? (OK, maybe in the end of the day I find typing printf("blah",argument,argument,...) easier than std::cout<<argument<<argument<<...)

Grazz256 wrote:

I would look into gdb, it will give you a trace of your program where the segfault happens so you can figure out whats causing it.

Thanks Grazz256.

Do you mean with the backtrace command? I'll have to look up the references for that. Using a debugger is like another set of skills altogether!

Thanks everyone, any pointers would really be helpful to me.

Grazz256 · 2009-12-16 11:57:05

Using iostreams is the c++ way of doing things, printf is the c way. Personally I don't like iostreams either I don't find them very intuitive, that being said I have been attempting to switch over to iostreams.

To use gdb you will probably want to remove the -O2 build option (optimization can make it more difficult to debug)
then from within the project folder run: gdb ./Sudoku
within gdm type: r "Puzzles/test_1_Basic.psv" BruteForce
that runs the executable, if you use the puzzle that causes the segfault it should tell you whats causing it

gdb has lots of other commands that you can use to help debug, type help within gdb for more info.

Cheers,
Jon EStey

ewaller · 2009-12-16 17:00:35

Dumas,
Sorry for not getting back to you as yet. I ended up spending the evening helping my daughter through some calculus problems.

I agree with Grazz256, iostreams is the "c++ way", but there is nothing really wrong with using printf. A lot of us write c code in a c++ environment -- I just wanted to point out the difference. That said, keep in mind there is no type checking or dynamic recasting when you use printf and friends. The format string tells the compiler what it expects the pointers to point at -- It had better be correct. If the pointer points to a double, but the format string says its an int, chaos ensues.

As to exceptions, I certainly cannot argue with Dr. Stroustrup -- But as I try to understand the structure of the code, I find it easier to follow the flow rather than trying to figure out how an exception is going to unwind the stack and figuring out where it is going to be caught.

I will try again tonight to look at the code some more.

juster · 2009-12-16 18:50:44

You are deleting a Board pointer twice. Once in the Strategy class destructor and again in the Win class destructor. I commented out ~Win's delete and the segfault went away.

dumas · 2009-12-17 11:44:33

ewaller wrote:

Dumas,
I agree with Grazz256, iostreams is the "c++ way", but there is nothing really wrong with using printf. A lot of us write c code in a c++ environment -- I just wanted to point out the difference. That said, keep in mind there is no type checking or dynamic recasting when you use printf and friends. The format string tells the compiler what it expects the pointers to point at -- It had better be correct. If the pointer points to a double, but the format string says its an int, chaos ensues.
As to exceptions, I certainly cannot argue with Dr. Stroustrup -- But as I try to understand the structure of the code, I find it easier to follow the flow rather than trying to figure out how an exception is going to unwind the stack and figuring out where it is going to be caught.
I will try again tonight to look at the code some more.

Thanks about the notte on printf. That does seem like a (somewhat small) motivation to use iostream? I think I actually had the wrong formatting a few times, but gcc was good enough to fire off some warnings. Maybe in my next project I'll try iostream. Right now I suppose it's not worth the trouble rewriting the IO.

For the win exception, I'm not saying Stroustrup is on my side, which is why I asked if that's a good implementation. I had a brief thought about implementing without throwing exceptions, and thought that would basically replicate an exception structure. So may I ask what would be a good alternative implementation of the flow to winning?

juster wrote:

You are deleting a Board pointer twice. Once in the Strategy class destructor and again in the Win class destructor. I commented out ~Win's delete and the segfault went away.

Yeah, of course. I actually did exactly as you did, just that I forgot! One of those bad programming habits about not tracking off bugs and forgetting afterwards?

The problem I can't get through is, when we're not inputting a completed Sudoku, the code actually is right, and ~Win() helps avoid memory leak. What would be a good way to get rid of the bug?

Thanks again.

Grazz256 · 2009-12-17 14:54:18

Just looking over your code a little I have a couple of comments about your coding style. Please keep in mind that these are just comments...

I think you need to comment your code more. I know its a pain and I'm horrible about it as well but it really does help when/if you go back to read your code in a couple of years.

I try to avoid lines like these:
fprintf( stdout, "Starting configuration:\n" ); a->Write(stdout);
start = clock(); a->Go();
by putting two commands on one line it makes the code harder to read. with one command on each line I can quickly scan through and know
generally what each line does, with two I have to actually read each line fully so that I don't miss anything.

Descriptive variable names can also help with readability, I've always been taught the convention of using the first character to indicate type then
using a short descriptive name. For instance you have a function that returns a long value, the value would be decalred like this:
long lRetVal;
so looking through the code I would know thats a long value that represents a return value.
This is an area I'm all over the place with, I always try to stick to one convention but never seem manage it...

As far as your problem goes, where are the boards normally deleted? ie if an incomplete sudoku is inputed?

One possible solution is to run an IsComplete check before you start processing the board. so you would have...
if (a->IsConsistent()) {
...
}
if (a->IsComplete()) {
...
}
a->Go()

I'll be honest in that I don't really understand the flow of your code, but instead of having the board deleted within strategy or within win why not just delete it on the next line... eg:
start = clock(); a->Go();
delete a;
the downside to this approach is that you would have to delete it within each exception as well but this is relatively minor.

Cheers

dumas · 2009-12-21 07:30:39

Grazz256 wrote:

Just looking over your code a little I have a couple of comments about your coding style. Please keep in mind that these are just comments...
I think you need to comment your code more. I know its a pain and I'm horrible about it as well but it really does help when/if you go back to read your code in a couple of years.
I try to avoid lines like these:
fprintf( stdout, "Starting configuration:\n" ); a->Write(stdout);
start = clock(); a->Go();
by putting two commands on one line it makes the code harder to read. with one command on each line I can quickly scan through and know
generally what each line does, with two I have to actually read each line fully so that I don't miss anything.
Descriptive variable names can also help with readability, I've always been taught the convention of using the first character to indicate type then
using a short descriptive name. For instance you have a function that returns a long value, the value would be decalred like this:
long lRetVal;
so looking through the code I would know thats a long value that represents a return value.
This is an area I'm all over the place with, I always try to stick to one convention but never seem manage it...
As far as your problem goes, where are the boards normally deleted? ie if an incomplete sudoku is inputed?
One possible solution is to run an IsComplete check before you start processing the board. so you would have...
if (a->IsConsistent()) {
...
}
if (a->IsComplete()) {
...
}
a->Go()

I'll be honest in that I don't really understand the flow of your code, but instead of having the board deleted within strategy or within win why not just delete it on the next line... eg:
start = clock(); a->Go();
delete a;
the downside to this approach is that you would have to delete it within each exception as well but this is relatively minor.
Cheers

Thanks for your comments. At my present level of programming skills, any comments will help.

I thought all my code was basically concise and self-explanatory, and each function is small enough that a quick skim through the definition and declaration would be enough to understand. As the project grew, however, things got slightly more complicated. I have added more comments in my source files, trying to comment why rather than how. I thought the flow of the code was fairly obvious though, by inspecting the main loop. It takes care of the input, bark if anything's wrong, trigger a.Go(), and try to catch a Win. Do you mean the flow within Go()? Anyway, it is very true I need clearer coding style.

Yeah I now solved the segfault problem. The reason a completed sudoku was deleted twice is because the original sudoku is meant to be deleted by the abstract factory, while the solved sudoku is meant to be deleted by Win. When a solved sudoku is inputted it would be deleted twice. Due to lack of programming experience, I failed to see the obvious way is to, as Grazz256 said, check in the beginning whether the inputted sudoku is already solved. If it is, then I duplicate the inputted sudoku and throw the win exception.

By the way, I think I'm beginning to understand why some people are obsessed wtih optimization. I did 3 optimization techniques in my program. First, I thought the most expensive procedure is the IsConsistent() method. By evaluating it lazily I reduced the time to 1/3 the original time. Then following http://www.acm.org/crossroads/xrds1-4/ovp.html, I used initialized the 2D vector within each sudoku via constructor rather than as statements. Doing so gave a 20% time boost. Using a friend procedure while copying sudokus boost another 5%. Doing a right move and getting positive feedback through better performance can be so satisfying.

EDIT:

I found out there was memory leak after all, which I finally solved.

What happens is with all my brute force algorithms I keep creating new Board's and call the Board's Go() recursively. To delete all Board's in the heap I need to have, within each Board::Go(), instead of

Board* a = Clone(); // return new derived Board(*this);
a->Put(x,y,'0'+k);
a->Go();
delete a; // if an exception is thrown this line never gets executed

this

Board* a = Clone();
a->Put(x,y,'0'+k);
try {a->Go(); }
catch( const Win& e) {
    delete a;
    throw(e);
}
delete a;

But this deletes the winning sudoku too. This means I have to keep the result in Win, either by duplicating the winning sudoku or storing the string. In the end I overloaded Board::Write(File* f) to also have Board::Write(std::string& p) to sprintf on the reference of a string, so Win just stores the solution in string format. Finally, no memory leak, no need to do a first check to see if the inputted sudoku is already solved, and no pointer deleted twice.

So in the end, to manage pointers I recursively threw exceptions. That made me ask, is using exceptions worth it, or should I stick to the more conventional methods, such as have Go() return a boolean value, then deleting pointers which would give an implementation that is essentially the same as recursive exceptions?

I still think exceptions is the way to go, the reasons being:
1) Exception mechanism provide a natural place to hold the result. Throwing exceptions recursively and the traditional way is essentially the same, but where should the result be stored in the latter case?
2) Arguing over the dictionary, an exception is not necessarily an "error." Winning is an exception in this algorithm, because failure is the norm (as in life).
3) Exception arguably gives better presentation in the main loop, to my "unbiased" eyes at least. Board* a->Go() is triggered in the try block in the main(), with all (foreseeable) possible results caught as exceptions. It is true that this might be a bit unconventional, but given proper comments I still think it is at least as good as the conventional way, in terms of presentation.

So what do you think?

Last edited by dumas (2009-12-21 12:37:47)

keenerd · 2009-12-21 14:10:01

Are you familiar with the technique of constraint propagation? It is kind of like your "priority" algo, but instead of plugging values into a board, you maintain a 3D table of all numbers with could be plugged into the board. Then you remove all logical inconsistencies, falling back to guessing when logic runs out.

Massive spoilers here.

Grazz256 · 2009-12-21 18:31:24

Generally your own code is concise and easy for you to read Its the same reason why its best to get someone else to proof read your school reports, your brain tends to fill in the blanks when you know whats going on.
The hard part for me is having multiple commands on one line and using the factory which I'm not familiar with.

Personally I think I would implement your app without the factory or exceptions. In my mind exceptions are for fatal errors not return values, for that matter (for better or worse) most of my apps don't use exceptions, I try to error check enough that exceptions aren't required.

The completed puzzle could always be returned by the go function
Board *Board::Go()
In this case Go would return NULL unless the puzzle is solved.

or you could use a pointer to a pointer for the return value
Board::Go(Board **brdSolved)
Here your main loop would go something like this..
Board *brdSolution = NULL;
a->Go(&brdFinal);
if (brdSolution != NULL)
// Solved!
else
// No solution found!

Is there any reason you need to pass back the completed puzzle? why not have the board print the puzzle when its completed, then you don't even have to worry about passing it back.

In my little sudoku solver uses the method keenerd mentions, Initially all unknown blocks have every possible value in a list then it recursively processes the lines and squares removing impossible values, followed by checking for probable values (aka if cell 1,1 can be 1 or 2 and cell 1,2 can be 1 or 2 then if cell 1,3 can be 1,2, or 3 it must be 3) this solves all puzzles I tried with it with no guessing...

There are always lots of ways of solving a problem no one way is right or wrong it mostly comes down to personal preference. A fun excersize is to try to reprogram a utility you made a couple years (or even months) later and see the difference in your code.

Cheers

dumas · 2009-12-22 03:43:16

keenerd wrote:

Are you familiar with the technique of constraint propagation? It is kind of like your "priority" algo, but instead of plugging values into a board, you maintain a 3D table of all numbers with could be plugged into the board. Then you remove all logical inconsistencies, falling back to guessing when logic runs out.
Massive spoilers here.

Wow, "constraint propagation," that's a big fancy word. I think I'll implement that as an exercise.

Very nice site too, by Peter Norvig. One of the major ways I gain my somewhat wayward knowledge is through browsing all these websites and resources. I think that gives you more insight, by having a good big picture of related disciplines, especially through the words of wise men.

Grazz256 wrote:

Generally your own code is concise and easy for you to read wink Its the same reason why its best to get someone else to proof read your school reports, your brain tends to fill in the blanks when you know whats going on.
The hard part for me is having multiple commands on one line and using the factory which I'm not familiar with.

True, I need to improve my coding style. I've added a lot more comment on my code, and removed most multiple commands. Am I right in saying good commenting for others to read is an art that should be developed?

What's wrong with the factory though? I've given it a good thought, I think a factory in my case is advantageous as all I need to do when I add a new strategy is register it to the factory. Then it returns the actual strategy requested through Strategy::Choose(), takes care of memory management in the destructor, and returns a list of strategies through Strategy::List(). I'm unsure about the use of singleton because I'm aware experts say this pattern is overused and misused, but according to my incomplete knowledge this use is fine in my case. In fact, when I was programming the factory I tried several times to do it more "the C way," because I don't want to overuse design patterns, but fell back to factory+singleton. If there's any problem, please enlighten me!

And yeah, returning a pointer of the solved sudoku would be an equivalent and more conventional way, which probably makes it the better way. I think I'll do that in my next project. Throwing exceptions made me learn in this project though, by being more aware of memory management and code flow. And then, this is the first "real" project I ever did. I never used exception handling before, nor any design pattern, nor optimization. I learnt so much in this project, and you guys helped a lot too.

The reason I want to pass back the solution to the main loop is because I wanted all code flow to be within the main loop. So within Sudoku.cpp I register all strategies, process the command line arguments and fire up the algorithm, then catch all exceptions. Thus all code flow is here. Is this a good practice or are there better ones?

Another thing I want to ask is, does the operating system do some simple garbage collection after a program is terminated? I think I read somewhere each program has its own heap which grows inwards in a process's memory block. That would explain why firefox can have all the memory leak in the world and yet when I close it the memory leak is apparently gone according to conky.

Thanks again.

Grazz256 · 2009-12-22 15:44:35

You are correct in saying that good commenting for others is an art that should be developed!

There's nothing "wrong" with the factory or the singleton I'm just not familiar with either of them (the terms at the very least).

I'll let someone else chime in on weather or not its good practice to do everything in the main loop or not. Personally I think unless your going to
further process the board there really is no reason to pass it back. In my implementation I do pass the solution back but I also do a final
verification on the solution.

I'm fairly sure modern operating systems do work in this manner. Memory leaks are only a really big problem if your app is going to continue to run for a long period of time (like firefox, your WM, etc). That being said it would be bad practice to ignore memory leaks just because the OS is going to clean it up for you.

Cheers

juster · 2009-12-22 16:49:40

Exceptions:
This is interesting because you are using excepions here like in a functional language like Lisp where they are used for more than just errors. But this would probably confuse C++ programmers and IMO is not really needed because you do not go so deep into a call stack to prevent you from returning a value easily.

Singleton/Strategy:
I think this is overly complex. The strength of the singleton IMO is that it hides the fact that there is only one object created. Here you don't need to hide the fact, you could just have a Strategy object inside main(). I would not exactly call Strategy a "factory" because to me a factory is a bit different. A "factory" should create a new pointer on request but not be sent new pointers. That is just a container of objects.

If it were me I would separate the Board object and the solving logic, maybe into a Solver class. Board would just be a utility class for reading/writing boards, rotating, entering x/y coords. Solver could take a board as argument, maybe with a play(Board &b) function or something. Then you can keep the number of attempts data inside the Solver class, as you mentioned once before. Along with other state, private methods etc.

Why is it so hard to not use exceptions in main? IE in my mind:

Board board;
Solver *solver = Strategory::Choose( bla );
solver->solve( board );
board.print;
printf( "Attempts: %d\n", solver->get_attempts() );

I meant to give these suggestions for awhile but never got around to it. Good job! Keep up the good work!

dumas · 2009-12-23 01:11:19

juster wrote:

Exceptions:
This is interesting because you are using excepions here like in a functional language like Lisp where they are used for more than just errors. But this would probably confuse C++ programmers and IMO is not really needed because you do not go so deep into a call stack to prevent you from returning a value easily.
Singleton/Strategy:
I think this is overly complex. The strength of the singleton IMO is that it hides the fact that there is only one object created. Here you don't need to hide the fact, you could just have a Strategy object inside main(). I would not exactly call Strategy a "factory" because to me a factory is a bit different. A "factory" should create a new pointer on request but not be sent new pointers. That is just a container of objects.
If it were me I would separate the Board object and the solving logic, maybe into a Solver class. Board would just be a utility class for reading/writing boards, rotating, entering x/y coords. Solver could take a board as argument, maybe with a play(Board &b) function or something. Then you can keep the number of attempts data inside the Solver class, as you mentioned once before. Along with other state, private methods etc.
Why is it so hard to not use exceptions in main? IE in my mind:
Board board;
Solver *solver = Strategory::Choose( bla );
solver->solve( board );
board.print;
printf( "Attempts: %d\n", solver->get_attempts() );
I meant to give these suggestions for awhile but never got around to it. Good job! Keep up the good work!

Thanks for your advice and encouragement.

Yeah, I think both you and Grazz256 are right in that exceptions would confuse C++ programmers, and there are no real advantages in using it as a win situation. In my next project I won't do something so eccentric.

Also I think your idea of separating a Solver class is a very good one. Especially when I have those implementations of Boards with additional consistency requirement, for example the Hyper and DisJoint classes. I think this shows how important experience is in the programming world, the "obvious" keeps evading me!

The reason I kept falling back to singleton is that
1) in the end of the day, I want to the client of the factory to have the simplest procedure to get a strategy.
2) register a new strategy in the clearest, most fool-proof way
3) given 1 and 2, I can use Factory::Choose(string) to get a new strategy, and Factory::List() to get the names of strategies, and so forth. Factory itself is somewhat a blackbox, it can be a namespace for all the client cares.

In my implementation of Singleton/Strategy, to register a new strategy I need to
1) register the new strategy in Strategy::Choose()
2) include the header file in Sudoku.cpp
3) include the cpp file in Makefile
Given that, Factory::Choose(string) and Factory::List() are simply called in the main loop, nothing to worry about. Although, as you said, the "factory" is not even a real factory,

I would be very anxious to know what would be a better implementation/design.

Thanks again.

juster · 2009-12-23 18:45:18

I haven't used design patterns in awhile but after thinking about it a bit you are misusing the term Singleton. A singleton design patterns returns an instance of a class through a class method. Strategy is using static class methods instead. A singleton design pattern avoids this and gives you inheritence.

What I meant before is why not just use Strategy (is it named Factory now?) as a regular class? Without the class variable or its "singleton" instance and the smartptr stuff. Then just create a Strategy[/Factory] object inside main() and register the boards (or solvers) inside of it and use it like that. This seems simpler and more straight-forward. Keep in mind these are my opinions and not necessarily "better".

But now I understand using design patterns or more complicated techniques could be for practicing. However, your use of the design pattern terms is confusing because you are not implementing the singleton or factory design patterns. Maybe you unconsciously want to convert the Strategy class to a true singleton/factory? Could be good practice.

dumas · 2010-01-23 06:33:36

OK, after taking a break I've updated my program: http://ifile.it/gn4uhx9/Sudoku.tar

Modifications include:

A new abstract class Solver with Solver::Solve(Board* a) replacing Board::Go().

No more using exceptions as winning. The solution is passed as the return value of Solver::Solve(), return type being const Board*.

The new Solver classes mean I need another Factory/Strategy thingy to choose both Solver's and Board's (Board is now a concrete class storing the 9x9 boxes, with derived classes Disjoint and Hyper that has additional consistency requirements). Therefore Factory/Strategy is now implemented as Menu<template>. It is called Menu because it is not what is conventionally called a "factory," which returns new pointers rather than store registered new pointers. It is also no longer a "singleton."

Lightly updated user interface.

Files are organized into directories, with an improved Makefile.

I think I observed slightly better optimization in gcc's part. Since I didn't change anything in the algorithms, would it simply be due to better "design?"

I've been trying to put in comments, but I'm not sure if it's "user friendly" enough.

Any feedback would be greatly appreciated!

Arch Linux

#1 2009-12-13 11:23:10

My sudoku program, any comments, improvements appreciated

#2 2009-12-14 21:39:27

Re: My sudoku program, any comments, improvements appreciated

#3 2009-12-15 01:28:18

Re: My sudoku program, any comments, improvements appreciated

#4 2009-12-15 11:59:41

Re: My sudoku program, any comments, improvements appreciated

#5 2009-12-16 11:57:05

Re: My sudoku program, any comments, improvements appreciated

#6 2009-12-16 17:00:35

Re: My sudoku program, any comments, improvements appreciated

#7 2009-12-16 18:50:44

Re: My sudoku program, any comments, improvements appreciated

#8 2009-12-17 11:44:33

Re: My sudoku program, any comments, improvements appreciated

#9 2009-12-17 14:54:18

Re: My sudoku program, any comments, improvements appreciated

#10 2009-12-21 07:30:39

Re: My sudoku program, any comments, improvements appreciated

#11 2009-12-21 14:10:01

Re: My sudoku program, any comments, improvements appreciated

#12 2009-12-21 18:31:24

Re: My sudoku program, any comments, improvements appreciated

#13 2009-12-22 03:43:16

Re: My sudoku program, any comments, improvements appreciated

#14 2009-12-22 15:44:35

Re: My sudoku program, any comments, improvements appreciated

#15 2009-12-22 16:49:40

Re: My sudoku program, any comments, improvements appreciated

#16 2009-12-23 01:11:19

Re: My sudoku program, any comments, improvements appreciated

#17 2009-12-23 18:45:18

Re: My sudoku program, any comments, improvements appreciated

#18 2010-01-23 06:33:36

Re: My sudoku program, any comments, improvements appreciated

Board footer