c - 数独 9 个盒子 ( 3x3 ) C 中的递归回溯所有组合

Question

我写了一个 3x3 的数独(9 个盒子)，我想让它递归并生成所有组合，但我不知道哪里出错了......这是我的代码:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define dbg 0
using namespace std; 
int n,st[100][100];

void afisare()
{
    for(int i=1;i<=3;i++) {
        for(int j=1;j<=3;j++)
            printf("%2d",st[i][j]);

        printf("\n");
    }

    printf("\n");
}

int valid(int k,int ii,int jj)
{
    int i,j;
//  if(k==1){
//      if(dbg)printf("\nReturnez 1 deoarece k-ul este egal cu 1");
//  return 1;
//  }

    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            if((i==ii) && (j==jj))
            {
                if(dbg)
                    printf("\nValorile nu indeplinesc criteriul, se incrementeaza j.");
            }
            else
            {
                if(dbg)
                    printf("\n i= %d j= %d",i,j);

                if(dbg)
                    printf("\nSe verifica daca %d este egal cu casuta %d %d",k,i,j);

                if(k==st[i][j]) {
                    if(dbg)printf("\nValorile sunt egale, returnez 0");
                    return 0;
                }
            }

    if(dbg)
        printf("\nValorile nu sunt egale, deci returnez 1");

    return 1;
} 

void back(int k)
{
    int i,j;

    if(dbg) printf("\nk=",k);

    for(i=1;i<=3;i++) {
        for(j=1;j<=3;j++)
        {
            if(dbg)
                printf("\nVerifica daca casuta %d %d este egal cu 0",i,j);

            if(st[i][j]==0) {
                if(dbg) printf("\n Este egal cu 0");
                if(dbg) printf("\n%d ia valoarea %d.",st[i][j],k);

                st[i][j]=k;

                if(dbg)
                    printf("\nSe verifica valabilitatea numarului %d",st[i][j]);

                // while(valid(k,i,j)!=0)
                if(valid(k,i,j)!=0) {
                    valid(++k,i,j);
                    //back(k+1);
                }
                else
                    do {
                        st[i][j]=k+1;
                        if(dbg)
                            printf("\nCasuta %d %d are noua valoare %d, veche valoare fiind %d.",i,j,k+1,k);    
                        if(dbg)
                            ("\nValoarea returnata este 0, merg cu urmatoarea valoare %d si verific valabilitatea.",k+1);

                        //back(k+1);
                    }
                    while(valid(++k,i,j)==0);
            }
            else
                if(dbg)
                    printf("\nNu este egala cu 0 ci are valoarea %d",st[i][j]);
        }
    }

    if(k>9 || st[3][3]!=0)
        afisare();

    //afisare();
}

int main()
{
    int i,j;
    freopen("sudoku.in","r",stdin);

    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            scanf("%d",&st[i][j]);

/*  for(i=1;i<=3;i++){
        for(j=1;j<=3;j++){
            printf("%2d",st[i][j]);
        }

        printf("\n");
    }*/

    back(1);
    system("pause");

    return 0;
}

正如我所说，我不知道如何生成所有组合，我只是认为我应该调用函数回溯而不是有效的...

Answer 1

您的代码的问题主要在于格式化和命名。您可能已经通过将递归函数命名为 back 来迷惑自己，原因如下:

要求您找到给定起始条件的所有解决方案的问题的递归解决方案基本上是在解决方案空间中进行深度优先搜索。这意味着每次递归调用都是一个向前移动。

您不会通过调用方法来回溯，而是通过不再调用前向方法来回溯，以允许 DFS 树(递归沿着其中一条路径遍历)向上移动回它正在寻找的路径。

就您而言，您正在使用全局数据结构(st)来存储您的数独网格。这意味着，当您要回溯时，您需要将网格的状态返回到调用该方法之前的状态。就您而言，这意味着将您 checkin 的位置再次设置为 0。

这是解决方案的指南，以及我解决它的方法，(如果我使用全局数据结构，顺便说一句，这不是很好的编程实践。我建议使用一个类来存储网格)。

首先，一些名称更改:

• void afisare() 在我的解决方案中将是 void printGrid()(实现相同)
• int valid(int, int, int) 将是 bool isValid(int, int, int)，并且可以简化。

• void back(int) 将是 void fillEmpty()

  此函数将尝试用所有可能的数字填充下一个空白空间，对于所有有效数字，它将向下递归并再次调用 fillEmpty()。如果没有剩余的空数字，它将打印网格，因为您已经找到了解决方案。

这就是我所理解的问题的解决方案。

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int grid[3][3];

void
printGrid()
{
    for(int i = 0; i < 3; ++i) {

        for(int j = 0; j < 3; ++j)
            printf("%d ", grid[i][j]);

        printf("\n");
    }

    printf("\n");
}

bool
isValid(int k, int ii, int jj)
{
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 3; ++j) {
            if( (i != ii || j != jj) && grid[i][j] == k)
                return false;
        }

    return true;
}

void 
fillEmpty()
{
    // Find the next empty position.
    int i, j; bool foundEmpty = false;
    for(i = 0; i < 3; ++i) {
        for(j = 0; j < 3; ++j)
            if(grid[i][j] == 0) {
                foundEmpty = true;
                break;
            }

        if(foundEmpty) break;
    }

    // If there are no empty positions left
    // we have reached a solution, so we
    // print it and do nothing else.
    if(!foundEmpty)
    {
        printGrid();
        return;
    }

    // Try every number
    for(int k = 1; k <= 9; ++k)
        if( isValid(k, i, j) )
        {
            grid[i][j] = k;
            fillEmpty();
        }

    // Reset the grid position before backtracking.
    grid[i][j] = 0;
}

int 
main(void)
{
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 3; ++j)
            scanf("%d", &grid[i][j]);

    printGrid();
    fillEmpty();

    return 0;
}