c - c中的数独求解器崩溃

问题描述

我试图找出我的代码有什么问题，该代码应该解决一个 9x9 数独，当我使用 Wikipedia 中的数独示例运行它时会崩溃。

我也尝试过使用递归，但对它不是很熟悉，所以它也不起作用。

findunassignedlocation1如果数独中仍有 0 且0不再有 0 ，则返回。
isSafe1如果所有行、列和 3x3 网格不包含数字，则返回，0否则返回。

如果问题可能出在其他功能之一，请告诉我，我将发送代码。忽略depth变量。

下面是我的代码：

/* Returns an int which indicates whether if the sudoku has any
   more empty entries (which shows as a 0) */
int FindUnassignedLocation(int grid[9][9]) { 
    for (int row = 0; row < 9; row++) 
        for (int col = 0; col < 9; col++) 
            if (grid[row][col] == 0) 
                return 1; 
    return 0; 
}

/* Returns an int which indicates whether an assigned entry 
   in the specified row matches the given number. */
int UsedInRow(int grid[9][9], int row, int num) { 
    for (int col = 0; col < 9; col++) 
        if (grid[row][col] == num) 
            return 1; 
    return 0; 
} 

/* Returns an int which indicates whether an assigned entry 
   in the specified column matches the given number. */
int UsedInCol(int grid[9][9], int col, int num) { 
    for (int row = 0; row < 9; row++) 
        if (grid[row][col] == num) 
            return 1; 
    return 0; 
} 

/* Returns an int which indicates whether an assigned entry 
   within the specified 3x3 box matches the given number. */
int UsedInBox(int grid[9][9], int boxStartRow, int boxStartCol, int num) { 
    for (int row = 0; row < 3; row++) 
        for (int col = 0; col < 3; col++) 
            if (grid[row + boxStartRow][col + boxStartCol] == num) 
                return 1; 
    return 0; 
} 

/* Returns an int which indicates whether it will be legal to assign 
   num to the given row,col location. */
int isSafe(int grid[9][9], int row, int col, int num) { 
    /* Check if 'num' is not already placed in current row, 
       current column and current 3x3 box */
    if (!UsedInRow(grid, row, num) && 
        !UsedInCol(grid, col, num) && 
        !UsedInBox(grid, row - row % 3, col - col % 3, num) && 
        grid[row][col] == 0) {
        return 1;
    } else {
        return 0;
    }
} 

void solve_sudoku(int sudoku[9][9]) {
    int row = 0;
    int col = 0;
    if (FindUnassignedLocation(sudoku) == 0) { //if sudoku is completely filled
        return;
    }
    for (int num = 1; num <= 9; num++) {
        if (isSafe(sudoku, row, col, num) == 1) {
            sudoku[row][col] = num;
            solve_sudoku(sudoku, depth);
            sudoku[row][col] = 0;
        }
    }
}

标签： csudoku

解决方案

一种简单的（但由于对称/旋转不是最有效的）方法是尝试所有可能性，尝试将数字 1 到 9 放在连续位置 (0,0 0,1 .. 0,8 1,0 。 .. ) 递归，每次可以将一个数字放在 8,8 上，这是一个解决方案

您的代码几乎不需要更改，只是为了删除无用的FindUnassignedLocation并添加递归

如果我将 9 替换为 SZ 也能够搜索尺寸 3、6 或 9，并且我添加解决方案的绘制代码可以是：

#include <stdio.h>

// 3, 6 or 9
#define SZ 9

/* Returns an int which indicates whether an assigned entry 
   in the specified row matches the given number. */
int UsedInRow(int grid[][SZ], int row, int num) 
{ 
  for (int col = 0; col < SZ; col++)
    if (grid[row][col] == num) 
      return 1; 

  return 0; 
} 

/* Returns an int which indicates whether an assigned entry 
   in the specified column matches the given number. */
int UsedInCol(int grid[][SZ], int col, int num) 
{ 
  for (int row = 0; row < SZ; row++) 
    if (grid[row][col] == num) 
      return 1; 

  return 0; 
} 

/* Returns an int which indicates whether an assigned entry 
   within the specified 3x3 box matches the given number. */
int UsedInBox(int grid[][SZ], int boxStartRow, int boxStartCol, int num) { 
  for (int row = 0; row < 3; row++) 
    for (int col = 0; col < 3; col++) 
      if (grid[row + boxStartRow][col + boxStartCol] == num) 
        return 1; 

  return 0; 
} 


/* Returns an int which indicates whether it will be legal to assign 
   num to the given row,col location. */
int isSafe(int grid[][SZ], int row, int col, int num) 
{ 
  /* Check if 'num' is not already placed in current row, 
     current column and current 3x3 box */
  return (!UsedInRow(grid, row, num) && 
          !UsedInCol(grid, col, num) && 
          !UsedInBox(grid, row - row % 3, col - col % 3, num));
} 

/* print a solution */
void draw(int sudoku[][SZ])
{
  for (int row = 0; row != SZ; ++row) {
    for (int col = 0; col != SZ; ++col)
      printf("%d", sudoku[row][col]);
    putchar('\n');
  }
  putchar('\n');
}

void solve_sudoku(int sudoku[][SZ], int row, int col)
{
  for (int num = 1; num <= 9; num++) { //loop through numbers 1 to SZ
    if (isSafe(sudoku, row, col, num) == 1) { //the number is safe
      sudoku[row][col] = num;
      if ((col + 1) == SZ) {
        if ((row + 1) == SZ) {
          // done
          draw(sudoku);
        }
        else
          solve_sudoku(sudoku, row + 1, 0);
      }
      else
        solve_sudoku(sudoku, row, col + 1);
      sudoku[row][col] = 0;
    }
  }
}

int main()
{
  int sudoku[SZ][SZ] = {0};

  solve_sudoku(sudoku, 0, 0);
}

为 SZ 3 找到的第一个解决方案（362880 个可能的解决方案）：

为 SZ 6 找到的第一个解决方案：

为 SZ 9 找到的第一个解决方案

c - c中的数独求解器崩溃

问题描述

解决方案

推荐阅读