C數獨的回溯解算器預檢功能

Question

這是我在StackOverflow上的第一篇文章，所以我很抱歉如果我做錯了什麼。我對C相對比較陌生，所以我確信我的代碼在某些地方相當醜陋，而且大部分代碼都符合我的期望。我在使用precheck方法時遇到問題，在我開始通過求解邏輯進行提供之前，我正在使用它來檢查數獨板。我正在重定向來自文本文件的輸入字符串，看起來像

4 ..... 8.5.34 ......... 7 ...... 2 .... .6 ..... 8.4 ...... 1 ....... 6.3.7.5..2 ..... 1.4 ...... 4 ..... 8.5.3 .......... 7 ...... 2 ..... ..... 6 8.4 ...... 1 ....... 6.3.7.5..2 ..... 1.5 ...... 4 ..... 8.5.3 .......... 7 ...... 2 ..... 6 .... .8.4 ...... 1 ... X ... 6.3.7.5..2 ..... 1.4 ...... 417369825632158947958724316825437169791586432346912758289643.71573291684164875293

每個字符串（理想） 81個字符只有數字1-9和'。我將一個字符串解析爲一個temp char數組，然後使用方法fillBoard將temp數組中的字符轉換爲2d int數組。一旦完成，我打電話給我的precheck方法。如果填充板未通過行，列和框檢查，則precheck方法會返回一個，表示拼圖不可解（表示應打印錯誤消息，並且程序應移至下一個字符串）。出於某種原因，我的precheck方法即使對於應該可解的字符串也會返回一個。我不確定這是爲什麼。任何幫助，將不勝感激。謝謝。

#include <stdio.h> 
#include <string.h> 

int alphaError = 0; 

struct Point findEmpty(int board[9][9]); 
int usedInBox(int board[9][9], int boxStartRow, int boxStartCol, int num); 
int positionSafe(int board[9][9], int row, int col, int num); 
int usedInCol(int board[9][9], int col, int num); 
int usedInRow(int board[9][9], int row, int num); 
int solvePuzzle(int board[9][9]); 
int precheck(int board[9][9]); 

int main() 
{ 
    char c; 
    int charCount = 0; 
    int i = 0; 
    char tempStr[100000]; 
    int board[9][9]; 

    while((fscanf(stdin, "%c", &c)) != EOF) 
    { 
    printf("%c", c); 

    if(c != '\n') 
    { 
     if(isalpha(c)) 
     { 
     alphaError = 1; 
     } 

     tempStr[i] = c; 
     i++; 
     charCount++; 
    } 
    else 
    { 
     if(charCount != 81 || alphaError == 1) 
     { 
     printf("Error\n\n"); 
     i = 0; 
     charCount = 0; 
     alphaError = 0; 
     } 
     else 
     { 
     fillBoard(board, tempStr); 
     printBoard(board); 
     if(precheck(board) == 1) 
     { 
      printf("Error\n\n"); 
     } 
     else 
     { 
      if(solvePuzzle(board) == 1) 
      { 
      printBoard(board); 
      } 
      else 
      { 
      printf("No solution\n\n"); 
      } 
     } 
     i = 0; 
     charCount = 0; 
     } 
    } 
    } 
    return 0; 
} 

struct Point 
{ 
    int x; 
    int y; 
} point; 

struct Point findEmpty(int board[9][9]) 
{ 
    struct Point point1; 
    point1.x = -1; 
    point1.y = -1; 
    int row, col; 

    for(row = 0; row < 9; row++) 
    { 
    for(col = 0; col < 9; col++) 
    { 
     if(board[row][col] == 0) 
     { 
     point1.x = col; 
     point1.y = row; 
     } 
    } 
    } 
    return point1; 
} 

int usedInBox(int board[9][9], int boxStartRow, int boxStartCol, int num) 
{ 
    int row, col; 

    for(row = 0; row < 3; row++) 
    { 
    for(col = 0; col < 3; col++) 
    { 
     if(board[row + boxStartRow][col + boxStartCol] == num) 
     { 
     return 1; 
     } 
    } 
    } 
    return 0; 
} 

int positionSafe(int board[9][9], int row, int col, int num) 
{ 
    if((usedInRow(board, row, num)) == 0 && (usedInCol(board, col, num)) == 0 && (usedInBox(board, (row-row%3), (col-col%3), num)) == 0) 
    { 
    return 1; 
    } 
    else 
    { 
    return 0; 
    } 
} 

int usedInCol(int board[9][9], int col, int num) 
{ 
    int row; 

    for(row = 0; row < 9; row++) 
    { 
    if(board[row][col] == num) 
    { 
     return 1; 
    } 
    } 
    return 0; 
} 


int usedInRow(int board[9][9], int row, int num) 
{ 
    int col; 

    for(col = 0; col < 9; col++) 
    { 
    if(board[row][col] == num) 
    { 
     return 1; 
    } 
    } 
    return 0; 
} 

int solvePuzzle(int board[9][9]) 
{ 
    int num; 
    struct Point point2; 

    point2 = findEmpty(board); 
    if(point2.x == -1) 
    { 
    return 1; 
    } 

    for(num = 1; num <= 9; num++) 
    { 
    if(positionSafe(board, point2.y, point2.x, num) == 1) 
    { 
     board[point2.y][point2.x] = num; 

     if(solvePuzzle(board) == 1) 
     { 
     return 1; 
     } 

     board[point2.y][point2.x] = 0; 
    } 
    } 
    return 0; 
} 

void printBoard(int board[9][9]) 
{ 
    int i, j; 
    for (i = 0; i < 9; i++) 
    { 
    for (j = 0; j < 9; j++) 
    { 
     printf("%d", board[i][j]); 
    } 
    } 
    printf("\n\n"); 
} 

void fillBoard(int board[9][9], char tempStr[100000]) 
{ 
    int i, j; 
    int k = 0; 

    for(i = 0; i < 9; i++) 
    { 
    for(j = 0; j < 9; j++) 
    { 
     if(tempStr[k] == '.') 
     { 
     board[i][j] = 0; 
     } 
     else 
     { 
     board[i][j] = (tempStr[k] - '0'); 
     } 
     k++; 
    } 
    } 
} 

int precheck(int board[9][9]) 
{ 
    int i, j, num; 

    for(i = 0; i < 9; i++) 
    { 
    for(j = 0; j < 9; j++) 
    { 
     if(board[i][j] != 0) 
     { 
     num = board[i][j]; 
     if(positionSafe(board, i, j, num) == 0) 
     { 
      return 1; 
     } 
     } 
    } 
    } 
    return 0; 
} 

Answer 1

因此，您在已填充的電路板上使用precheck？這可能是問題，因爲如果該值已經存在，則usedInCol,usedInRow和usedInBlock將返回1。所以precheck只能在填充板時使用，而不能在之後使用。如果您檢查從已填充板上取的值，它將始終返回1。