c遞歸回溯返回錯誤的sudoku求解器

Question

嘿大家所以我寫了一個在C中使用遞歸回溯的數獨求解器。但是輸出結果並不符合要求。爲了使代碼正常工作，您需要傳遞81個數字的數組，並且板上的0等於'。'。在數組中。問題是我的輸出開始用1代替'。'的地方。我不明白爲什麼，我需要一雙新鮮的眼睛來爲我看。

#define DEBUG FALSE 
#define TRUE 1 
#define FALSE 0 

#include <stdio.h> 

/* function declarations */ 
int readPuzzle(int puzzle[9][9]); 
int findRowErrors(int puzzle[9][9]); 
int findColErrors(int puzzle[9][9]); 
int findBoxErrors(int puzzle[9][9]); 
int solvePuzzle(int puzzle[9][9], int index); 
int validMove(int puzzle[9][9], int index, int num); 
int noSolution(int puzzle[9][9]); 
void writePuzzle(int puzzle[9][9]); 

int main (void) 
{ 
    int puzzle[9][9]; 
    int index = 0; 
    int error; 

    while ((error = readPuzzle(puzzle)) != EOF) 
    { 
     error += findRowErrors(puzzle); 
     error += findColErrors(puzzle); 
     error += findBoxErrors(puzzle); 

    if (error) printf("Error\n\n"); 
    else 
    { 
     /* in DEBUG mode, show initial puzzle in standard sudoku form */ 
     if (DEBUG) writePuzzle(puzzle); 
     solvePuzzle(puzzle, index); 
     if (!noSolution(puzzle)) writePuzzle(puzzle); 
    } 
} 
    return 0; 
} 

int readPuzzle(int puzzle[9][9]) 
{ 
    int i, num, row, col; 
    int error = FALSE; 

    for (i = 0; (num = getchar()) != '\n'; i++) 
    { 
     if (num == EOF) return EOF; 
     putchar(num); 
     if ((num < '1' || num > '9') && (num != '.')) error = TRUE; 
     if (num == '.') num = '0'; 

     row = (i/9) % 9; 
     col = i % 9; 
     puzzle[row][col] = num - '0'; 
    } 
    putchar('\n'); 
    if (i != 81) error = TRUE; 
    return error; 
} 

    int findRowErrors(int puzzle[9][9]) 
{ 
    int row, col, i; 

    /* check rows */ 
    for (row = 0; row < 9; row++) 
    { 
     for (col = 0; col < 9; col++) 
     { 
      for (i = col + 1; i < 9; i++) 
      { 
       if ((puzzle[row][col] != 0) && (puzzle[row][col] == puzzle[row][i])) 
      { 
       return TRUE;      /* row error found in puzzle\ 
*/ 
       } 
      } 
     } 
    } 

    return FALSE; 
} 



int findColErrors(int puzzle[9][9]) 
{ 
    int row, col, i; 
    for (col = 0; col < 9; col++) 
    { 
     for (row = 0; row < 9; row++) 
     { 
      for (i = row + 1; i < 9; i++) 
      { 
       if ((puzzle[row][col] != 0) && (puzzle[row][col] == puzzle[i][col])) 
       { 
        return TRUE;      /* column error found in   puzzle */ 
       } 
      } 
     } 
    } 
    return FALSE; 
} 




int findBoxErrors(int puzzle[9][9]) 
{ 
    int row, col, i, j; 
    for (row = 0; row < 9; row += 3) 
    { 
     for (col = 0; col < 9; col += 3) 
     { 
      for (i = 0; i < 9; i++) 
      { 
       for (j = i + 1; j < 9; j++) 
       { 
        if ((puzzle[row + i/3][col + i % 3] != 0) && 
         (puzzle[row + i/3][col + i % 3] == 
         puzzle[row + j/3][col + j % 3])) 
        { 
         return TRUE;     /* box error found in  puzzle*/ 
        } 
       } 
      } 
    } 
    } 
    return FALSE; 
} 


int noSolution(int puzzle[9][9]) 
{ 
    int row, col; 
    for (row = 0; row < 9; row++) 
    { 
     for (col = 0; col < 9; col++) 
     { 
      if (!puzzle[row][col]) 
      { 
       printf("No solution\n\n"); 
       return TRUE; 
      } 
     } 
    } 
    return FALSE; 
} 


void writePuzzle(int puzzle[9][9]) 
{ 
    int row, col; 
    for (row = 0; row < 9; row++) 
    { 
     if (DEBUG) printf("\n"); 
     if ((DEBUG) && (row == 3 || row == 6)) 
     { 
      printf("----------------------\n"); 
     } 
     for (col = 0; col < 9; col++) 
     { 
      if (DEBUG) printf(" "); 
      if (puzzle[row][col]) printf("%d", puzzle[row][col]); 
      else printf("."); 
      if ((DEBUG) && (col == 2 || col == 5)) printf(" |"); 
     } 
    } 
    printf("\n\n"); 
} 



int solvePuzzle(int puzzle[9][9], int index) 
{ 
    int num; 
    int row = index/9; 
    int col = index % 9; 

    if (index == 81) return TRUE;     /* all cells are filled */ 

    if (puzzle[row][col] != 0) 
    { 
     return solvePuzzle(puzzle, ++index);  /* recursive call */ 
    } 

    else 
    { 
     for (num = 1; num <= 9; num++) 
     { 
      if (validMove(puzzle, index, num)) 
      { 
       puzzle[row][col] = num; 
       if (solvePuzzle(puzzle, index)) return TRUE; 
       puzzle[row][col] = 0; 
      } 
     } 
     return FALSE; 
    } 
} 


    /*Checks to see Valid moves for rows, columns, and regions*/ 
    int validMove(int puzzle[9][9],int start, int num) 

    { 
    int r, c; 
    int row = start/9; 
    int column = start % 9; 
    int regionFirstRow = row - (row %3); 
    int regionFirstColumn = column - (row % 3); 


    /*Checks rows for valid moves*/ 
    for(c = 0; c < 9; c++) 
     { 
     if(puzzle[row][c] == num) 
      { 
      return FALSE; 
      } 
     } 
    /*Checks columns for valid moves*/ 
    for(r = 0; r < 9; r++) 
     { 
     if(puzzle[r][column] == num) 
      { 
      return FALSE; 
      } 
     } 

    /*FINISH THIS!!!!!!!!!*/ 
    /*Checks each 3x3 region for valid moves*/ 
    for(r = 0; r < 3; r++) 
     { 
     for(c = 0; c < 3; c++) 
      { 
      if(puzzle[regionFirstRow + r][regionFirstColumn + c] == num) 
       { 
       return FALSE; 
    } 
      } 
     } 
    return TRUE; 
    } 
} 

Answer 1

有盒子區域計算函數validMove

int regionFirstColumn = column - (row % 3); 

的錯誤應該是

int regionFirstColumn = column - (column % 3);