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   

Basic Sudoku Solver in C

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

Joined: 03 Feb 2010
Posts: 2
:

Items
PostPosted: Wed Feb 03, 2010 1:01 am    Post subject: Basic Sudoku Solver in C Reply with quote

Hi, I'm writing a sudoku solver for my C. I'm going to convert it to assembly later so I'm planning on keeping it as simple as possible.

This is what I have so far.
Code:

const int width = 9;
int board[] = {
   7, 9, 0, 0, 0, 0, 3, 0, 0,
   0, 0, 0, 0, 0, 6, 9, 0, 0,
   8, 0, 0, 0, 3, 0, 0, 7, 6,
   0, 0, 0, 0, 0, 5, 0, 0, 2,
   0, 0, 5, 4, 1, 8, 7, 0, 0,
   4, 0, 0, 7, 0, 0, 0, 0, 0,
   6, 1, 0, 0, 9, 0, 0, 0, 8,
   0, 0, 2, 3, 0, 0, 0, 0, 0,
   0, 0, 9, 0, 0, 0, 0, 5, 4
   };

int main(void)
{
   int row = 0, col = 1;
   printf("The second element is %d\n", board[row * width + col]);
   return 0;
}
int checkCol(int row, int col)
{
    int index; //index through the array for column
    int square = row * width + col; //definition
   
    //loops through to check for columns
    for(index = square - 9; index > -1; index -= 9)
    {
        if(board[square] == board[index])
           return 0;
    }
    return 1;
}

int checkRow(int row, int col)
{
    int index; //index through the array for row
    int square = row * width + col; //definition
    int head = square - (square % 9);  //this is the square to stop (i > head)
   
    //loops through to check for columns
    for(index = head + 9; index > head; index--)
    {
        if(index == square)
           continue;
        else if(board[square] == board[index])
           return 0;
    }
    return 1;
}


is this a reasonable approach? My next plan is to create checkBox and then in my main method I would call these methods and solve it by backtracking. Any suggestions?

Thanks! Smile
Back to top
View user's profile Send private message
JasonLion

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Wed Feb 03, 2010 2:27 am    Post subject: Reply with quote

That general approach will work, though it will be fairly slow.

I don't believe that checkCol checks any cells in higher numbered rows, which it needs to do.

Why are you planning to convert to assembler? The best way to speed things up is to improve the algorithm first, and only consider assembler once that is taken care of. Of course, if you just want an example so you can practice assembly programming, then speed really isn't an issue.
Back to top
View user's profile Send private message
clag

Joined: 03 Feb 2010
Posts: 2
:

Items
PostPosted: Wed Feb 03, 2010 4:01 am    Post subject: wsfasf Reply with quote

Code:
I don't believe that checkCol checks any cells in higher numbered rows, which it needs to do.


correct me if I'm wrong but wouldn't it check higher numbered rows if input the column I want for the parameter? I ran it through on paper and it seemed right but I might be wrong Smile

thanks!
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Fri Feb 05, 2010 8:22 am    Post subject: Reply with quote

clag wrote:
JasonLion wrote:
clag wrote:
Code:

int checkCol(int row, int col)
{
    int index; //index through the array for column
    int square = row * width + col; //definition
   
    //loops through to check for columns
    for(index = square - 9; index > -1; index -= 9)
    {
        if(board[square] == board[index])
           return 0;
    }
    return 1;
}


I don't believe that checkCol checks any cells in higher numbered rows, which it needs to do.

correct me if I'm wrong but wouldn't it check higher numbered rows if input the column I want for the parameter? I ran it through on paper and it seemed right but I might be wrong Smile

indeed you are wrong,
you start at square - 9 and go down --
when will you reach any higher rows??
Back to top
View user's profile Send private message Visit poster's website
dmhayden

Joined: 01 Aug 2007
Posts: 16
:
Location: Central New Jersey

Items
PostPosted: Sun Feb 14, 2010 2:39 am    Post subject: Reply with quote

Clag,

Why declare the board as a 1 dimensional array? I think you'll find it easier to code and easier to read if you declare it as:
Code:

int board[9][9] = {
   {7, 9, 0, 0, 0, 0, 3, 0, 0},
   {0, 0, 0, 0, 0, 6, 9, 0, 0},
   {8, 0, 0, 0, 3, 0, 0, 7, 6},
   {0, 0, 0, 0, 0, 5, 0, 0, 2},
   {0, 0, 5, 4, 1, 8, 7, 0, 0},
   {4, 0, 0, 7, 0, 0, 0, 0, 0},
   {6, 1, 0, 0, 9, 0, 0, 0, 8},
   {0, 0, 2, 3, 0, 0, 0, 0, 0},
   {0, 0, 9, 0, 0, 0, 0, 5, 4}
   };


Now instead of writing this:
Code:

printf("The second element is %d\n", board[row * width + col]);

you can write this:
Code:

printf("The second element is %d\n", board[row][col]);

Regarding checkCol, consider a call to checkCol(0,0). The contents of the"for" loop won't execute at all. In fact, if you're checking a column, then why pass a row at all? If the purpose is to check whether the the column is invalid then you could code it like this (untested):
Code:

int checkCol(int col)
{
  int row;
  int numbersTaken[9];
  memset(numbersTaken, 0, sizeof(numbersTaken));
  for (row=0; row<9; ++row) {
   if (numbersTaken[board[row][col]) return 0;
   numbersTaken[board[row][col]] = 1;
  }
  return 1;
}

Something similar would work for checkRow().

I agree with the comment about converting to assembly. If your purpose is to learn assembly then by all means go for it, but if you want to speed up the program, work on the algorithms instead and let the compiler worry about tweaking the code.

Oh, and you can usually tell the compiler to generate the assembly code for you. Typically with the "-s" command line argument, but this depends on your specific compiler.

Good luck. It's really a wonderful subject for practicing various coding techniques.
Back to top
View user's profile Send private message AIM Address
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Sun Feb 14, 2010 8:04 pm    Post subject: Reply with quote

A one dimensional array as basis has the advantage, that checks for rows, cols and boxes can be done using the exact same code. To do that you had to define arrays, that hold the correct indices in board[]. Pass the correct index array for the row/col/box you want to check.
Back to top
View user's profile Send private message
dmhayden

Joined: 01 Aug 2007
Posts: 16
:
Location: Central New Jersey

Items
PostPosted: Mon Feb 15, 2010 2:58 pm    Post subject: Reply with quote

hobiwan wrote:
A one dimensional array as basis has the advantage, that checks for rows, cols and boxes can be done using the exact same code. To do that you had to define arrays, that hold the correct indices in board[]. Pass the correct index array for the row/col/box you want to check.

You could always pass two arrays - one with the row indices and one with the column indices.

Better yet, don't pass indices at all. Pass an array of 9 pointers to the squares that make up a "group" (row, column, or box). This is the technique that my solver uses. So the function to check a group always has a prototype like this:
Code:

int myFunc(Square* group[9]);


Then you can write a function that takes a pointer to one of these and calls it for each row, column, and box. In that way, to implement a new algorithm, you just have to write the function that analyzes a group.

Of course this only works with the algorithms that don't care whether a group is a row, column, or box.

Dave
Back to top
View user's profile Send private message AIM Address
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