在c中使用回溯算法测试数独谜题

回溯求解算法的数独难题在c计数可能的解决方案
我发现这个c代码实现了一个数独求解回溯算法，它能够找到一个解决任何数独难题，至少有一个解决方案。我想知道是否有一个简单的调整，即它能够告诉如果有一个以上的解决方案，在一个给定的数独难题

#include <stdio.h>

int matrix[9][9]={0};    //row*col sudoku numbers

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

int veryhard[9][9] = {
     {8, 0, 0,  0, 0, 0,  0, 0, 0} ,
     {0, 0, 3,  6, 0, 0,  0, 0, 0} ,
     {0, 7, 0,  0, 9, 0,  2, 0, 0} ,

     {0, 5, 0,  0, 0, 7,  0, 0, 0} ,
     {0, 0, 0,  0, 4, 5,  7, 0, 0} ,
     {0, 0, 0,  1, 0, 0,  0, 3, 0} ,

     {0, 0, 1,  0, 0, 0,  0, 6, 8} ,
     {0, 0, 8,  5, 0, 0,  0, 1, 0} ,
     {0, 9, 0,  0, 0, 0,  4, 0, 0}
};

int fivesolution[9][9] = {
     {0, 0, 0,  0, 0, 0,  0, 0, 0} ,
     {0, 1, 6,  0, 3, 0,  0, 5, 0} ,
     {0, 9, 0,  0, 0, 2,  0, 0, 8} ,

     {0, 0, 7,  0, 0, 8,  0, 0, 0} ,
     {0, 6, 0,  0, 1, 0,  3, 4, 5} ,
     {2, 5, 1,  0, 4, 0,  0, 0, 0} ,

     {0, 0, 0,  0, 9, 0,  0, 8, 0} ,
     {0, 4, 0,  5, 2, 1,  6, 7, 0} ,
     {0, 2, 0,  0, 8, 3,  0, 0, 0}
};

int moresolution[9][9] = {
     {1, 0, 0,  0, 0, 0,  0, 0, 0} ,
     {0, 0, 0,  0, 0, 0,  0, 0, 0} ,
     {0, 0, 0,  0, 0, 0,  0, 0, 0} ,

     {0, 0, 0,  0, 0, 0,  0, 0, 0} ,
     {0, 0, 0,  0, 0, 0,  0, 0, 0} ,
     {0, 0, 0,  1, 0, 0,  0, 0, 0} ,

     {0, 0, 0,  0, 0, 0,  0, 0, 0} ,
     {0, 0, 0,  0, 0, 0,  0, 0, 0} ,
     {0, 0, 0,  0, 0, 0,  0, 0, 0}
};

int nosolution[9][9] = {
     {0, 0, 0,  0, 0, 0,  0, 0, 0} ,
     {0, 1, 6,  0, 3, 0,  0, 5, 0} ,
     {0, 9, 0,  0, 0, 2,  0, 0, 8} ,

     {0, 0, 7,  0, 0, 8,  0, 0, 0} ,
     {0, 6, 0,  0, 1, 0,  3, 4, 5} ,
     {0, 0, 0,  0, 0, 0,  0, 0, 0} ,

     {0, 0, 0,  0, 0, 0,  0, 8, 0} ,
     {0, 4, 0,  0, 2, 1,  6, 7, 0} ,
     {0, 5, 0,  0, 4, 3,  0, 0, 0}
};

int usedInRow(int matrix[9][9],int row,int num) {
    for (int col = 0; col < 9; col++) {
        if (matrix[row][col] == num) {
            return 1;
        }
    }
    return 0;
}

int usedInCol(int matrix[9][9],int col,int num) {
    for (int row = 0; row < 9; row++) {
        if (matrix[row][col] == num) {
            return 1;
        }
    }
    return 0;
}

int usedInBox(int matrix[9][9],int boxStartRow,int boxStartCol,int num) {
    for (int row = 0; row < 3; row++) {
        for (int col = 0; col < 3; col++) {
            if (matrix[row + boxStartRow][col + boxStartCol] == num) {
                return 1;
            }
        }
    }
    return 0;
}

 int isSafe(int matrix[9][9],int row,int col,int num) {
    return (
        !usedInRow(matrix, row, num) &&
        !usedInCol(matrix, col, num) &&
        !usedInBox(matrix, row - (row % 3), col - (col % 3), num)
    );
}

void print_sgrid(int matrix[9][9]){

    for(int a=0;a<9;a++){

        for (int b=0;b<9;b++){
             printf("%d ",matrix[a][b]);
            if (b==2 || b==5) printf("| ");
        }
        printf("\n");
        if (a==2 || a==5) printf("------+-------+------\n");

    }
}

int solveSudoku(int matrix[9][9]) {
    int row = 0;
    int col = 0;
    int checkBlankSpaces = 0;

    /* verify if sudoku is already solved and if not solved,
    get next "blank" space position */
    for (row = 0; row < 9; row++) {
        for (col = 0; col < 9; col++) {
            if (matrix[row][col] == 0) {
                checkBlankSpaces = 1;
                break;
            }
        }
        if (checkBlankSpaces == 1) {
            break;
        }
    }
    // no more "blank" spaces means the puzzle is solved
    if (checkBlankSpaces == 0) return 1;

    // try to fill "blank" space with correct num
    for (int num = 1; num <= 9; num++) {
        /* isSafe checks that num isn't already present
        in the row, column, or 3x3 box (see below) */
        if (isSafe(matrix, row, col, num)) {
            matrix[row][col] = num;

            if (solveSudoku(matrix)) return 1;

            /* if num is placed in incorrect position,
            mark as "blank" again then backtrack with
            a different num */
            matrix[row][col] = 0;

        }
    }
    return 0;
}

int main (void){

if (solveSudoku(veryhard))
print_sgrid(veryhard);

    return 0;
}

为了回答你的问题，如果你想得到解决方案的数量，你可以修改你的代码像添加计数功能。

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

...
long count=0;
int countSolutions(int matrix[9][9]) {
    count = 0;
    return solveSudoku(0,matrix);
}

int solveSudoku(int level,int matrix[9][9]) {
    int row = 0;
    int col = 0;
    int checkBlankSpaces = 0;

    /* verify if sudoku is already solved and if not solved,
    get next "blank" space position */
    for (row = 0; row < 9; row++) {
        for (col = 0; col < 9; col++) {
            if (matrix[row][col] == 0) {
                checkBlankSpaces = 1;
                break;
            }
        }
        if (checkBlankSpaces == 1) {
            break;
        }
    }
    // no more "blank" spaces means the puzzle is solved
    if (checkBlankSpaces == 0) {
        count +=1;
        printf("Solution %ld\n",count);
      return count;
    }

    // try to fill "blank" space with correct num
    for (int num = 1; num <= 9; num++) {
        /* isSafe checks that num isn't already present
        in the row, column, or 3x3 box (see below) */
        if (isSafe(matrix, row, col, num)) {
            matrix[row][col] = num;

            if (solveSudoku(level+1,matrix)) {
                // print solution and keep exploring 
                print_sgrid(matrix);
                printf("_______________\n");
            }

            /* if num is placed in incorrect position,
            mark as "blank" again then backtrack with
            a different num */
            matrix[row][col] = 0;

        }
    }
    if (level == 0) {
       return count;
    }
    return 0;
}

int main (void){
    int nb_solutions = countSolutions(veryhard);
    printf("Number of solutions %d\n", nb_solutions);

    nb_solutions = countSolutions(fivesolution);
    printf("Number of solutions %d\n", nb_solutions);
}

在c中使用回溯算法测试数独谜题

1条答案

相关问题

热门标签

最新问答