Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

C++ generator, noob programmer, need help

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
FlukeLogic

Joined: 17 Nov 2008
Posts: 8
:

Items
PostPosted: Mon Nov 17, 2008 4:46 am    Post subject: C++ generator, noob programmer, need help Reply with quote

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
Code:
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
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Mon Nov 17, 2008 10:33 am    Post subject: Reply with quote

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!
Back to top
View user's profile Send private message
FlukeLogic

Joined: 17 Nov 2008
Posts: 8
:

Items
PostPosted: Mon Nov 17, 2008 7:32 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
FlukeLogic

Joined: 17 Nov 2008
Posts: 8
:

Items
PostPosted: Tue Feb 23, 2010 3:24 am    Post subject: Reply with quote

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.
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 human-style 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
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Tue Feb 23, 2010 3:41 am    Post subject: Reply with quote

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
View user's profile Send private message
FlukeLogic

Joined: 17 Nov 2008
Posts: 8
:

Items
PostPosted: Thu Feb 25, 2010 2:30 am    Post subject: Reply with quote

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
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Thu Feb 25, 2010 10:35 am    Post subject: Reply with quote

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 hard-wired
-- 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
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron