스도쿠 솔버와 재귀 backtracking 오류가 발생했습니다.

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

에 유래에

int regionFirstColumn = column - (column % 3);