c 中的数独求解器崩溃 [英] Sudoku solver in c crashes

问题描述

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

I am trying to figure out what is wrong with my code which is supposed to solve a 9x9 sudoku which crashes when I run it with the example in the Wikipedia for sudoku.

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

I have also tried using recursion but am not very familiar with it so it did not work either.

• findunassignedlocation 如果数独中仍有 0，则返回 1，如果没有更多 0，则返回 0.
• isSafe 如果所有行、列和 3x3 网格不包含数字，则返回 1，否则返回 0.

• findunassignedlocation returns 1 if there are still 0s in the sudoku and 0 if there are no more 0s.
• isSafe returns 1 if all rows, columns and 3x3 grid does not contain the number and 0 otherwise.

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

If the problem is probably in one of the other functions, please let me know, I will send code. Ignore the depth variable.

下面是我的代码:

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

推荐答案

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

A simple (but not the most efficient because of symmetries/rotations) way is to try all the possibilities trying to place the number 1 up to 9 on the successive positions (0,0 0,1 .. 0,8 1,0 ... ) recursively, each time a number can be put on 8,8 it is a solution

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

Few changes are needed from your code, just to remove the useless FindUnassignedLocation and add the recursion

如果我用 SZ 替换 9 也可以搜索尺寸 3、6 或 9 并添加解决方案的绘制代码可以是:

If I replace 9 by SZ to also be able to search for the sizes 3, 6 or 9 and I add the draw of the solutions the code can be :

#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 个可能的解决方案):

first solutions found for SZ 3 (362880 possible solutions) :

123
456
789

123
456
798

123
456
879

123
456
897

123
456
978

123
456
987

123
457
689

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

First solutions found for SZ 6 :

123456
456789
789123
214365
365897
897214

123456
456789
789123
214365
365897
897241

123456
456789
789123
214365
365897
978214

123456
456789
789123
214365
365897
978241

123456
456789
789123
214365
365978
897214

123456
456789
789123
214365
365978
897241

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

First solutions found for SZ 9

123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531642

123456789
456789123
789123456
214365897
365897214
897214365
531642978
648971532
972538641

123456789
456789123
789123456
214365897
365897214
897214365
531642978
672938541
948571632

123456789
456789123
789123456
214365897
365897214
897214365
531642978
678931542
942578631

123456789
456789123
789123456
214365897
365897214
897214365
531642978
942578631
678931542

这篇关于c 中的数独求解器崩溃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！