hi, Im coding a sodoku program base on backtracking, but somehow it did not work as what I expected, can help me figure out what's the problem?

sodoku.c

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

void printGrid(int board[]) {
    int i,j;
    if (board==NULL){
        printf("No Solution\n");
        return;
    }
    for (i=0;i<9;i++){
        for (j=0;j<9;j++){
            printf ("%d",board[i*9+j]);
            if (j%3==2)
                printf (" ");
            }
        printf ("\n");
        if (i%3==2)
            printf ("\n");
        }       
}

int checkDigit(int board[], int digit, int n) {

    int i,j;
    int ROW;
    int COL;

    ROW=n/9;
    COL=n%9;

    if (ROW<0 || COL<0 || ROW>8 || COL >8 || digit <1 || digit >9 )
        return false;
    if (board[ROW*9+COL]!=0)
        return false;

//scan horizontally and vertically
    for (i=0;i<9;i++){
        if (board[i*9+COL]==digit || board[ROW*9+i]==digit)
            return false;
    }

//scan within the square
    for (j=((ROW/3)*3);j<(((ROW/3)*3)+3);j++){
        for (i=((COL/3)*3);i<((COL/3)*3+3);i++){
            if (board[j*9+ROW]==digit)
                return false;
        }
    }
    return true;
}

int solveGrid(int board[], int n) {

    int i,j,k;
    i=n/9;
    j=n%9;
    int solved=1;
    for (n=0;n<81;n++){
        if (board[n]==0){
            solved=0;
        }
        else
            solved=1;
    }

    if (solved)
        return;
    
    for (i=0;i<9;i++){
        for (j=0;j<9;j++){
            if (board[i*9+j]==0){
                for (k=1;k<=9;k++){
                    if (checkDigit(board,k,i*9+j)){
                        board[i*9+j]=k;
                        solveGrid(board,i*9+j+1);
                    }
                }
            }
        }
    }
}


main.c

#include <stdio.h>
#include <stdlib.h>

#define ROW 9
#define COL 9

int main(int argc, char** argv) {

    /* the sudoku grid is represented by this 1D array */
    int board[ROW * COL];
    char filename[100];
    int i, j, input;
    FILE *fp;

    printf("Enter data file name: ");
    scanf("%s", filename);

    fp = fopen(filename, "r");
    if (fp == NULL) {
        printf("Cannot open data file\n");
        exit(0);
    }

    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            fscanf(fp, "%d", &input);
            board[i * ROW + j] = input;
        }
    }
    fclose(fp);

    // the solver starts from position 0
    if (solveGrid(board, 0)) {
        printf("Solved.\n");
        printGrid(board);
    }
    else
        printf("No Solution.");

    return (EXIT_SUCCESS);
}

found a small bug:

for (j=((ROW/3)*3);j<(((ROW/3)*3)+3);j++){      
  for (i=((COL/3)*3);i<((COL/3)*3+3);i++){            
     if (board[j*9+ROW]==digit)               
       return false;       
 }    
}

but still parts are wrong :(

Edited 7 Years Ago by Justea: n/a

I still doubt your logic for solving a sudoku.
Anyways what the checkDigit() method doing?

And will u explain your logic in summary (not in codes just the summary such a pseudocode with minimum complexity).

This article has been dead for over six months. Start a new discussion instead.