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   

Newbie Tackling Sudoku Generator in C

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

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sun Feb 05, 2006 7:38 am    Post subject: Newbie Tackling Sudoku Generator in C Reply with quote

This is the first in what may be many questions and comments. I hope to get off on a good footing.

First off, let me say that I only have a rudimentary grasp of some of the terminology used in this forum. So, please try to simplify any replies whenever possible. I will strive to learn more as I progress.

Second, there are way too many posts in this forum for me to read and categorize all of them. I will do what I can to research information first, but I may not find (or understand) an answer even though it exists. If I ask a question that's not new, then please bear with me.

I've played Sudoku using 'Simple Sudoku', but I'm only a fair player. Still, that doesn't keep me from wanting to try my hand at programming some aspects of the game. It seems to me that the best way to get started is to write a Sudoku generator. I know it's been done hundreds of times before me, but it's still a good learning project.

I'd like to start with two questions for now. The first question involves filling empty cells, and the second question has to do with choosing a 'candidates' data structure -- One of many DS's that will eventually be needed.

Q #1:

Is there any way an invalid layout can be created simply by filling the first three blocks with any properly arranged set of values? I don't see it happening ... but I'm a novice.

Q #2:

I'm at the very initial stage of planning my data structures. One of the ideas I have is to use the following C array to hold the candidates, as nine bits stored in an int, for all cells.

int Candidates[3][3][3][3];

This array can be visualized as follows:

Candidates [block:0..2][row:0..2] [block:0..2][column:0..2]

By choosing the correct pairing of [0][0]..[2][2] values, I can map them into [1..9] to access rows, columns, and blocks.

Some examples:

Row(1) would be Candidates[0][0][0..2][0..2]
Row(9) would be Candidates[2][2][0..2][0..2]

Column(1) would be Candidates[0..2][0..2][0][0]
Column(9) would be Candidates[0..2][0..2][2][2]

Block(1) would be Candidates[0][0..2][0][0..2]
Block(9) would be Candidates[2][0..2][2][0..2]

Basically, I wanted a way to represent rows in terms of columns and blocks, and columns in terms of rows and blocks. I also wanted a way to access blocks in terms of their row and column components. I'm not sure if this is an overkill or not.

Do you think that I've made it too complicated for this array?

Thanks for all constructive input!!!

-Danny
Back to top
View user's profile Send private message
evert

Joined: 30 Aug 2005
Posts: 68
:
Location: Amsterdam

Items
PostPosted: Mon Feb 06, 2006 8:14 pm    Post subject: Reply with quote

daj95376 wrote:
I'm not sure if this is an overkill or not. Do you think that I've made it too complicated for this array?

With Candidates[9][9] things can also get complicated. In my opinion your DS is more elegant.
Back to top
View user's profile Send private message Send e-mail
donaldf

Joined: 31 Dec 2005
Posts: 11
:
Location: Sweden

Items
PostPosted: Mon Feb 06, 2006 10:27 pm    Post subject: Reply with quote

Hi,

Well, questions regarding internal representation (data structures) is always interesting. One can make it difficult, and one can make it simple.

The simple way is to think in terms of operations. Which operations do you want to perform? Define the operations, name them as they come up in your mind, and then implement them. When you have this work done, it usually comes to one which structures are needed.

I implemented a quite straightforward generator/solver using a 9x9 matrix of {int, int}. One of the ints is the key for the cell, the other is a bit mask for the candidate list. A getColumn() primitive is then implemented using an array of pointers into the matrix, for instance.

The pro of this method is space efficiency. If you want to implement a backtracker algorithm or any other brute force method, it is easy to start with a matrix, copy it and twist one cell, copy it again, and so on.

The generator/solver then looks like this:

Code:

    /**
     * makeBoard returns a valid filled sudoku board. There is no guarantee
     * that the board has a single solution.
     * @param B: If B is null, a new sudokuboard is generated
     * by first generating a random first line, and thereafter the puzzle
     * is solved by a simple backtracking mechanism. If B is set to a valid
     * initialized sudoku puzzle, the puzzle is solved.
     * @return a filled (solved) puzzle.
     **/
    intSudokuBoard makeBoard(intSudokuBoard B) {
        int i, j, k, l, r, br, bc, boardMinusOne, counter = 0;;
       
        currentBoard = 0;
       
        if(B == null){
            Board[currentBoard].initFirstLine();
            br = 1;
        } else {
            Board[currentBoard] = B.copy();
            br = 0;
            Board[currentBoard].lastX = 0;
            Board[currentBoard].lastY = 0;
        }
               
        Backtrack: for(i = br; i < 9; i++) {
            for(j = 0; j < 9; j++) {
                if(!Board[currentBoard].Matrix[i][j].isKey){
                    boardMinusOne = currentBoard;
                    currentBoard++;
                    Board[currentBoard] = Board[boardMinusOne].copy();
                    Board[currentBoard].lastX = i;
                    Board[currentBoard].lastY = j;
                    r = Board[currentBoard].Matrix[i][j].getAvailable();
                   
                    if(r != 0) {
                        Board[boardMinusOne].Matrix[i][j].unSetAvailable(r);
                        Board[currentBoard].Matrix[i][j].unSetAvailable(r);
                        Board[currentBoard].Matrix[i][j].setAllocated(r);
                       
                        for(k = j+1; k < 9; k++){
                            Board[currentBoard].Matrix[i][k].unSetAvailable(r);
                        }
                       
                        for(k = i+1; k < 9; k++){
                            Board[currentBoard].Matrix[k][j].unSetAvailable(r);
                        }
                       
                        Board[currentBoard].unSetAvailableInBox(i, j, r, i, j);
                    } else {
                        currentBoard -= 2;
                        counter++;
                        if(currentBoard <= 0) {
                            i = br-1;
                            continue Backtrack;
                        } else {
                            i = Board[currentBoard].lastX;
                            j = Board[currentBoard].lastY;
                        }
                    }
                }
            }
        }
        return Board[currentBoard];
    }


This function finds a solution sooner or later, actually quite often sooner. Approximately nine times out of ten it returns multiple solutiuon sudokus, however, so its really low quality. But it's an example of how easy one can make it Smile
_________________
It's better to seek forgiveness than to ask permission
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting 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