Algorithm-and-DataStructure/Algorithms/Backtracking/sudokuSolver.cpp at master · dipta-dhar/Algorithm-and-DataStructure · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;

int isAvailable(int sudoku[][9], int row, int col, int num) {
    int i, j;
    for(i=0; i<9; ++i)
        if ((sudoku[row][i] == num) || (sudoku[i][col] == num))
            return 0;

     //checking in the grid
    int rowStart = (row/3) * 3;
    int colStart = (col/3) * 3;

    for(i=rowStart; i<(rowStart+3); ++i) {
        for(j=colStart; j<(colStart+3); ++j) {
            if (sudoku[i][j] == num)
                return 0;
        }
    }

    return 1;
}

int fillsudoku(int sudoku[][9], int row, int col) {
    int i;
    if (row<9 && col<9) {
        if (sudoku[row][col] != 0) {
            if ((col+1) < 9)
                return fillsudoku(sudoku, row, col+1);
            else if ((row+1) < 9)
                return fillsudoku(sudoku, row+1, 0);
            else
                return 1;
        }

        else {
            for(i=0; i<9; ++i) {
                if (isAvailable(sudoku, row, col, i+1)) {
                    sudoku[row][col] = i+1;

                    if ((col+1) < 9) {
                       if (fillsudoku(sudoku, row, col +1))
                           return 1;
                        else
                            sudoku[row][col] = 0;
                    }
                    else if ((row+1) < 9) {
                        if (fillsudoku(sudoku, row+1, 0) )
                            return 1;
                        else
                            sudoku[row][col] = 0;
                    }
                    else
                        return 1;
                }
            }
        }
        return 0;
    }
    else {
        return 1;
    }
}

int main()
{
    int i, j;
    int sudoku[9][9]={{3, 0, 6, 5, 0, 8, 4, 0, 0},
                      {5, 2, 0, 0, 0, 0, 0, 0, 0},
                      {0, 8, 7, 0, 0, 0, 0, 3, 1},
                      {0, 0, 3, 0, 1, 0, 0, 8, 0},
                      {9, 0, 0, 8, 6, 3, 0, 0, 5},
                      {0, 5, 0, 0, 9, 0, 6, 0, 0},
                      {1, 3, 0, 0, 0, 0, 2, 5, 0},
                      {0, 0, 0, 0, 0, 0, 0, 7, 4},
                      {0, 0, 5, 2, 0, 6, 3, 0, 0}};

    if(fillsudoku(sudoku, 0, 0)) {
        printf(" After solving:\n\n");
        for(i=0; i<9; ++i) {
            for(j=0; j<9; ++j) {
                if (i%3 == 0 && j==0 && i!=0)
                    printf(" ------+-------+--------\n");

                printf(" %d", sudoku[i][j]);

                if ((j+1)%3 == 0) printf(" |");
            }
            printf("\n");
        }
    }

    else    printf("\n\nNO SOLUTION\n\n");

    return 0;
}