
View previous topic :: View next topic 
Author 
Message 
 FlukeLogic
 Joined: 17 Nov 2008  Posts: 8  :   Items 

Posted: Mon Nov 17, 2008 4:46 am Post subject: C++ generator, noob programmer, need help 


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 tags. But if you go to cpplc dot net slash forum you can see the code under work in progress > for loop problem. Could someone check my code and see if they can find what I'm doing wrong? 

Back to top 


 Adak
 Joined: 27 Feb 2008  Posts: 87  :   Items 

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 retest 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.
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! 

Back to top 


 FlukeLogic
 Joined: 17 Nov 2008  Posts: 8  :   Items 

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. Thanks for the advice. 

Back to top 


 FlukeLogic
 Joined: 17 Nov 2008  Posts: 8  :   Items 

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 logicbased 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 cellcoordinate 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 runtime 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.
Code: 
Cell *Rows[N][N];
for (int Row = 0; Row < N; ++Row)
{
for (int Cell = 0; Cell < N; ++Cell)
{
Rows[Row][Cell] = &Grid[Row * N + Cell];
}
}

Does that look right? The column formula I have is similar. Can anyone point me a the right direction for mapping the zones/boxes?
For solving, I want to use a heuristic approach initially, then in case of an impasse (I don't plan on getting too tricky with my algorithms), convert the puzzle to an incidence matrix and run through a DLX solver (which I have questions about in another thread).
This may be an unrealistic approach, and any advice is welcome. Really the only reason I'm considering DLX is because it appears elegant, and offers a way to find every possible solution to a puzzle, if more than one exists. But I still want the humanstyle solver, because it seems more fun to code.
Can anyone offer input/advice/assistance on my plan thus far? I would greatly appreciate it. 

Back to top 


 Adak
 Joined: 27 Feb 2008  Posts: 87  :   Items 

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. 

Back to top 


 FlukeLogic
 Joined: 17 Nov 2008  Posts: 8  :   Items 

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. 

Back to top 


 Pat
 Joined: 06 Sep 2006  Posts: 128  :   Items 

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


FlukeLogic wrote: 
OK, so I found a formula
what I went on to do was play around and see if the mapping formula would work for a 4x4, 9x9 or 16x16 (basically N*N where N is a square) grid, and it does. Here is the formula, originally posted by angusj and modified by me (not to pat myself on the back because I'm sure others have figured this as well):
Code: 
for (box = 0; box < N; box++)
{
for (cell = 0; cell < N; cell++)
{
boxes[box][cell] = &grid[(box/sqrt(N))*(sqrt(N)*N)+(box%(int)sqrt(N))*sqrt(N)+(cell/sqrt(N)*N+(cell%(int)sqrt(N))];
}
}

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 much software has 3x3 hardwired
 very glad to see you're doing something more general!
but then, why should you insist on N being a square?
N = rows_per_box * columns_per_box
Code: 
for (box = 0 ; box < N ; box++)
{
whole_rows = ( box / rows_per_box )
* rows_per_box ;
skip = whole_rows * N
+ ( box  whole_rows ) * columns_per_box ;
for (cell = 0 ; cell < N ; cell++)
{
boxes [box] [cell] =
& grid [ skip
+ ( cell / columns_per_box ) * N
+ ( cell % columns_per_box )
] ;
}
}



Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
