数据崩溃中的数独求解器

Question

我试图弄清楚我的代码有什么问题，它应该解决一个9x9数独，当我用维基百科中的数据运行它时崩溃了。

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

findunassignedlocation返回1，如果在sudoku和0中仍然有0，如果没有更多的0。
如果所有行，列和3x3网格不包含数字，则qazxsw poi返回qazxsw poi，否则返回isSafe。

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

以下是我的代码：

Answer 1

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

您的代码几乎不需要进行任何更改，只需删除无用的FindUnassignedLocation并添加递归即可

如果我用SZ替换9也能够搜索大小3,6或9并且我添加解决方案的绘图代码可以是：

depth

找到SZ 3的首批解决方案（362880可能的解决方案）：

/* 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;
        }
    }
}

找到SZ 6的首个解决方案：

#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 9找到了第一个解决方案

数据崩溃中的数独求解器

问题描述投票：-1回答：1

1个回答

最新问题

数据崩溃中的数独求解器

问题描述 投票：-1回答：1

1个回答

最新问题

问题描述投票：-1回答：1