具有递归回溯返回错误的 C 数独求解器

Question

大家好，我用 C 语言编写了一个使用递归回溯的数独求解器。但是，输出不是 expected.For 工作代码，您需要传入一个包含 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);

具有递归回溯返回错误的 C 数独求解器

c sudoku solver with recursive backtracking returning errors

c

recursion

solver

sudoku

backtracking