FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Basic Sudoku Solver in C          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message clag Joined: 03 Feb 2010 Posts: 2 : Items Posted: Wed Feb 03, 2010 1:01 am    Post subject: Basic Sudoku Solver in C 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! Back to top JasonLion Joined: 16 Nov 2008 Posts: 61 : Location: Silver Spring, MD Items Posted: Wed Feb 03, 2010 2:27 am    Post subject: 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 clag Joined: 03 Feb 2010 Posts: 2 : Items Posted: Wed Feb 03, 2010 4:01 am    Post subject: wsfasf 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 thanks! Back to top Pat Joined: 06 Sep 2006 Posts: 128 : Items Posted: Fri Feb 05, 2010 8:22 am    Post subject: 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 indeed you are wrong, you start at square - 9 and go down -- when will you reach any higher rows?? Back to top dmhayden Joined: 01 Aug 2007 Posts: 16 : Location: Central New Jersey Items Posted: Sun Feb 14, 2010 2:39 am    Post subject: 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 hobiwan Joined: 11 Feb 2008 Posts: 83 : Items Posted: Sun Feb 14, 2010 8:04 pm    Post subject: 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 dmhayden Joined: 01 Aug 2007 Posts: 16 : Location: Central New Jersey Items Posted: Mon Feb 15, 2010 2:58 pm    Post subject: 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 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming sudoku All times are GMT Page 1 of 1   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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