算法来解决数独

Question

我想写一个算法，它可以解决一个扩展的数独。我设法找到了9x9 Sudoku的解决方案，但是当我试图扩展它时，我的程序返回“没有解决方案”，我不知道什么是错的。也许有人可以建议我犯了什么错误？

#include<stdio.h> 
#include<algorithm> 

int sudoku[15][9] = {{0, 0, 0, 0, 0, 0, 0, 0, 9}, 
        {4, 7, 0, 0, 0, 0, 0, 0, 0}, 
        {0, 0, 0, 5, 6, 2, 0, 0, 3}, 
        {0, 6, 0, 0, 0, 0, 0, 0, 0}, 
        {0, 0, 4, 0, 0, 3, 0, 6, 0}, 
        {0, 5, 9, 0, 0, 0, 0, 0, 0}, 
        {0, 0, 0, 2, 0, 0, 0, 0, 0}, 
        {6, 0, 0, 4, 0, 0, 0, 0, 0}, 
        {0, 4, 8, 0, 0, 0, 6, 0, 0}, 
        {0, 0, 4, 0, 0, 0, 0, 0, 0}, 
        {0, 2, 0, 0, 0, 0, 1, 0, 0}, 
        {0, 9, 1, 0, 0, 4, 0, 0, 5}, 
        {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
        {4, 0, 0, 6, 0, 0, 0, 0, 5}, 
        {5, 0, 0, 0, 0, 0, 8, 6, 0}}; 

bool isPossibleToInsert(int array[][9], int v, int x, int y){ 
    int rows = (x/3) * 3; 
    int columns = (y/3) * 3; 
    for (int i=0; i<9; i++){ 
      if (i < 3){ 
        for (int j=0; j<7; ++j){ 
          if (sudoku[j][y] == v) return false; 
        } 
      } 
      if (i > 5){ 
        for (int j=8; j<=14; ++j){ 
          if (sudoku[j][y] == v) return false; 
        } 
      } 
      if (array[x][i] == v) return false; 
      if (array[i][y] == v) return false; 
      if (array[rows + i%3][columns + i/3] == v) return false; 
    } 
    return true; 
} 

bool checkNextCell(int orginal[][9], int copy[][9], int x, int y); 
bool tryToSolve(int sudoku[][9], int temp[][9], int x_val, int y_val){ 
    if (sudoku[x_val][y_val] == 0){ 
      for (int i=1; i<=9; ++i){ 
        if (isPossibleToInsert(temp,i,x_val,y_val)){ 
          temp[x_val][y_val] = i; 
          if (checkNextCell(sudoku,temp,x_val,y_val)) return true; 
        } 
      } 
      temp[x_val][y_val] = 0; 
      return false; 
    } 
    return checkNextCell(sudoku,temp,x_val,y_val); 
} 

bool checkNextCell(int orginal[][9], int copy[][9], int x, int y){ 
    if ((x == 8) && (y == 8)) return true; 
    else if (x == 8) return tryToSolve(orginal,copy,0,y+1); 
    else return tryToSolve(orginal,copy,x+1,y); 
} 

int main(){ 
    /*int sudoku[15][9] = {{0, 0, 0, 0, 0, 0, 0, 0, 9}, 
         {4, 7, 0, 0, 0, 0, 0, 0, 0}, 
         {0, 0, 0, 5, 6, 2, 0, 0, 3}, 
         {0, 6, 0, 0, 0, 0, 0, 0, 0}, 
         {0, 0, 4, 0, 0, 3, 0, 6, 0}, 
         {0, 5, 9, 0, 0, 0, 0, 0, 0}, 
         {0, 0, 0, 2, 0, 0, 0, 0, 0}, 
         {6, 0, 0, 4, 0, 0, 0, 0, 0}, 
         {0, 4, 8, 0, 0, 0, 6, 0, 0}, 
         {0, 0, 4, 0, 0, 0, 0, 0, 0}, 
         {0, 2, 0, 0, 0, 0, 1, 0, 0}, 
         {0, 9, 1, 0, 0, 4, 0, 0, 5}, 
         {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
         {4, 0, 0, 6, 0, 0, 0, 0, 5}, 
         {5, 0, 0, 0, 0, 0, 8, 6, 0}};*/ 
    int arrayMain[9][9]; 
    std::copy(sudoku+7, sudoku+15, arrayMain); 
    if (tryToSolve(sudoku,arrayMain,0,0)){ 
      for (int i=0; i<9; ++i){ 
        for (int j=0; j<9; ++j){ 
          printf("%d ",arrayMain[i][j]); 
        }printf("\n"); 
      } 
    } 
    else{ 
      printf("No solution"); 
    } 
    return 0; 
} 

编辑：
对不起，我没有正确解释这个问题。在上面的例子中，数独必须是两个独立的9x9 Sudokus（第1-9行，第一行，第七行至第十五行）。

Answer 1

所以你有一个超级数独，它由两个重叠在行6-8（我开始计数为0）的sudokus组成。

问题是你无法像你的代码那样独立地解决它们。为什么？因为他们不是两个独立的sudokus。根据定义，数独的解决方案是独一无二的，否则它不是数独。超级数独也是如此。但是，如果你独立看待重叠的数独，那么解决方案（大多数情况下）不是唯一的。因此，整个超数独必须被解决为一个难题，而不是两个独立的难题。换句话说，你的算法找到了一个解决上数独的问题，这使得解决低数独是不可能的。

回溯也适用于超数独，算法与简单的数独非常相似。但是当你到达第6-8行时，你必须对上面和下面的数独进行测试。之后，你继续正常解决第二个数独。