Please help me with my sudoku solver

I've just started programming and I've been trying to make a C program that solves sudoku puzzles. Basically the user enters all of the numbers in the grid and enters a zero for unsolved spaces, then the program will try numbers in the first box until it finds a number that doesn' break any rules and move onto the second box etc. When it finds a box where no numbers work it will backtrack and try a different number for the previous box and so on.

It only works if there are less than about 10 spaces left empty and if there are more empty spaces the program will stop working and windows shuts it down right away. Is this because my computer cannot handle the program or do I have ann error in my code? If someone could have a look at my code that'd be great. I'm running it on Eclipse indigo on windows 7.Attachment 11239

It's because your code has errors (of course). Solving a sudoku puzzle isn't exactly a beginners level type of program.

I haven't studied it much yet, but calling main() a second time if the puzzle is input incorrectly, is WAY wrong - you never call main() a second time!

You have a very compact program - hard to debug that check if valid function because you have everything crammed into there.

I'll look at it more tomorrrow. Try to troubleshoot exactly WHERE it's crashing, by adding some printf() statements in critical places.

Ran your program. No warnings or errors from the compiler, so that's good!

The way you have the entry set up is wacko, however. You can't expect people to enter a sudoku puzzle, with digits running vertically down the left side of the screen:

1
2
3
4
5
6
7
8
9
end of the first row of the puzzle. You HAVE to get entry to appear in a horizontal format:

|123|456|789|
|000|000|000|
etc.

Second thing, and equally important, is that for all your testing, you need your program to read in the puzzle data, from a file - you will wear your fingers to the bone if you have to enter yet another puzzle, every single time the program is re-started.

The data files for sudoku are in the form of 81 digits (for 9 x 9 size), with zero being the placeholder for an empty square, of course. You can read in the digits as int's or char's, it doesn't matter.

For your testing, you'll want a couple files. Every puzzle in the collection MUST have just ONE solution, or you can't use it for testing purposes.

1) A small 10 puzzle collection. 3 very easy one's, 3 medium one's, and 4 that are tough as you can find them.

2) Just copy the easiest puzzle to a separate file, for easy testing. Include medium or hard puzzle that your program currently fails on.

Add in the file loading code, and I'll post up some puzzles I've used that are like this.

For testing, I just hardcoded an example (from wikipedia).

Code:

---

int main(void){
    index k=0, j=0;
    int d=0;
    int lettercheck=0;
    int yesorno;
    int givenNumbers[9][9];
    int valueMarker[9][9];
    int sudoku[9][9];
#if 0
//////  snip snip snip
#else
    {
        int testNumbers[9][9] = {
          { 5, 3, 0, 0, 3, 0, 0, 0, 0 },
          { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
          { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
          { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
          { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
          { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
          { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
          { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
          { 0, 0, 0, 0, 8, 0, 0, 7, 9 },
        };
        for(k=0;k<9;k++){
            for(j=0;j<9;j++){
                sudoku[k][j]=testNumbers[k][j];
                givenNumbers[k][j] = testNumbers[k][j] != 0;
            }
        }
    }
#endif
    solveSudoku(sudoku, 0, 0, givenNumbers,valueMarker);
    printf("\n\t\tSolution:\n\n");
    printSudoku(sudoku);
    return 0;
}

---

Until it works for at least one known test case, there isn't any point going all interactive. It just wastes too much time.

FWIW, I ran this in gdb and it just enters infinite recursion at some point.

Code:

---

(gdb) where
#0  0x0000000000400cf5 in solveSudoku (sudoku=0x7fffffffdeb0, r=1, c=7, givenNumbers=0x7fffffffe150, valueMarker=0x7fffffffe000) at bar.c:158
#1  0x0000000000400e7a in solveSudoku (sudoku=0x7fffffffdeb0, r=1, c=7, givenNumbers=0x7fffffffe150, valueMarker=0x7fffffffe000) at bar.c:175
#2  0x0000000000400e7a in solveSudoku (sudoku=0x7fffffffdeb0, r=1, c=7, givenNumbers=0x7fffffffe150, valueMarker=0x7fffffffe000) at bar.c:175
#3  0x0000000000400e7a in solveSudoku (sudoku=0x7fffffffdeb0, r=1, c=7, givenNumbers=0x7fffffffe150, valueMarker=0x7fffffffe000) at bar.c:175
#4  0x0000000000400e7a in solveSudoku (sudoku=0x7fffffffdeb0, r=1, c=7, givenNumbers=0x7fffffffe150, valueMarker=0x7fffffffe000) at bar.c:175
#5  0x0000000000400e7a in solveSudoku (sudoku=0x7fffffffdeb0, r=1, c=7, givenNumbers=0x7fffffffe150, valueMarker=0x7fffffffe000) at bar.c:175
// and so on....
(gdb) frame 10000
#10000 0x0000000000400e7a in solveSudoku (sudoku=0x7fffffffdeb0, r=1, c=7, givenNumbers=0x7fffffffe150, valueMarker=0x7fffffffe000) at bar.c:175
// then boredom set in...

---

You're right my keyboard was taking a beating from entering so many numbers! Here is my revised program with the suggested hardcoded test matrix. Attachment 11242

I realize it's not opening a file to get the entries but i can just store my test puzzles in a file and copy and paste them in easily enough. My previous code was getting the user to enter numbers horizontally. j is the coloumn number and k is the row number. I have looked over the sudokuSolver function and cannot figure out why it would ever go into infininite recursion.

Your first for loop in check, I can't grok what the g is doing in there? I suspect it's trouble.

Here's the easiest puzzle I have for a solver:
00800000005010070903907004101070000000590810000000 2030890040520704001080000000900

And a very hard one:
00000001270006000000000005008020000060000040000010 9000019000000000030800502000000

I used to have a file with puzzle grids that were sorted by difficultly levels, but I can't find it atm.

A bit more testing:

If you REM out either of the two lines inside this for loop, the program runs to completion. It crashes ONLY when both the lines are active. The answer to the puzzle is incorrect, but it runs.

This is the loop, with the column check REM'd out:

Code:

---

int checkValue(int sudoku[mSize][mSize],index k, index j, int x){
        index f=0;
        index g=0;
                for(f=0;f<9;f++){
                  printf("x: %d  row: %d  col: %d",x, k, f); getchar();
        if(sudoku[k][f]==x && f!=j) return 0;
                        //if(sudoku[f][j]==x && f!=k) return 0;
                }

---

I'd like to see the for loop for row and column checking, broken out into their own separate for loops.