C++ generator, noob programmer, need help

FlukeLogic

Ok, first off, I know it's not very elegant, or efficient, or even a very good program to begin with but hey, I tried. And I'm kinda proud of it. In any case, I want to get it working first, then I'll worry about optimization, and trying different methods of generating/solving. Right now, it compiles and runs, but it freezes up at the end and I'm noticing that duplicate values are being assigned to some cells. I don't know why but it won't let me post my code... it keeps giving me some crap about posting URLS, which I'm not even trying to do... I just pasted it in here between the

Adak · Posted: Mon Nov 17, 2008 10:33 am Post subject:

Here's the mistake I see.

You've written a lot of code, and now that you go to run it, find it doesn't work right.

The way to write code up is to make just stubs (with the bare minimum of code), for the essential functions, and test as you go. Whenever you finish a new function (or it's essential stub of code), you re-test it.

So piece by piece, you can test and verify the accuracy of your code, as you go.

The worst thing is to have a handful or more of untested functions, with maybe hundreds of lines of code, and you're left staring at a program that has 86 warnings and 53 compiler errors - or just doesn't give the darn right answer. No fun. Shocked

I haven't written a generator, so I can't really help you much with the code, but I would start by looking at the accuracy of each function, or block of code, as you go through it.

Good luck!

FlukeLogic · Posted: Mon Nov 17, 2008 7:32 pm Post subject:

Good point, Adak. I think I got a little ahead of myself. I guess at this point I can test each function individually from main() rather than calling them in succession and wondering which one isn't working. Embarassed

Thanks for the advice.

FlukeLogic · Posted: Tue Feb 23, 2010 3:24 am Post subject:

Well, I'm not sure if resurrecting this thread will be frowned upon. I figured starting a new one for the same topic might be.

I eventually got my solver working (mostly). It can solve easy puzzles - but if it hits a puzzle with more than one solution it kinda freaks out. Also it only has a couple logic-based methods (hidden singles/naked singles) so if it can't solve with those I put in a check to see if the puzzle was unchanged after calling both the search functions, then it gives up.

Then I gave up on it myself, for a long time - and now I've learned more about C++ and I'm taking another crack at it. This time I'm going to structure it better and plan it out before I even write one line of code.

My plan is to have a Cell object which contains a bitset to hold the candidate values for each cell. Then the Grid object will be a single array of Cell objects (rather than the crazy x/y cell-coordinate loops I was doing before). I think this will vastly simplify my searching/eliminating functions.

Then I was thinking I could map the regions/houses at run-time using separate arrays containing pointers to the Cell objects. Then for candidate elimination I could simply loop through the regions.

I have found formulas to map the rows and columns from the Grid array index for an N*N Sudoku, but I can't figure out how to map the zones/boxes.

Here is an example for setting the pointer to each cell in each row.

Adak · Posted: Tue Feb 23, 2010 3:41 am Post subject:

What I did was make up a table which has all the boxes listed, and what cells they contain.

It's all explicit, and not OOP, but I'm happy with it. I believe you'll like the 1D array. It has a few wrinkles to it, but that "row and col" stuff gets old after awhile.

FlukeLogic · Posted: Thu Feb 25, 2010 2:30 am Post subject:

OK, so I found a formula and experimented with it (you can see the the forum post here):

http://www.setbb.com/sudoku/viewtopic.php?t=1892&mforum=sudoku

The great thing about having that formula is that now I can make any Sudoku N^2*N^2 and the same mapping formulas and search routines should work regardless (I have 3 kids so I want to be able to make 4*4 Sudoku with pictures as well as the traditional 9*9 and larger 16*16).

So, my next thought is, my data structure for the Cell object. I was planning to use an STL <bitset> to hold the candidate values, where a 1 means the value is a candidate and a 0 means the value is not a candidate. But I'm worried about efficient search routines - won't I have to loop through the bitsets every time to see which values are possible for each Cell? I suppose I could check the count() of each and start with the most constrained Cells first, but even still...

Anyhow, I haven't found anything yet in the forums about this but I'll keep searching, and if anyone has any advice on efficient Cell object structure I would appreciate it.

Pat · Posted: Thu Feb 25, 2010 10:35 am Post subject: