freetime/sudoku.c at master · jpbat/freetime · 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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/*
 *      sudoku.c
 *
 *      Copyright 2011 João Ferreira <joao@void>
 */

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

int matrix[9][9];

void show()
{
    int i, j;

    for (i = 0; i < 9; ++i)
    {
        if (i % 3 == 0)
                printf("+-----------------------+\n");
        printf("| ");

        for (j = 0; j < 9; ++j) {

            if (j % 3 == 0 && j != 0)
                printf("| ");

            if (matrix[i][j] == 0)
                printf("- ");
            else
                printf("%d ", matrix[i][j]);
        }
        printf("|\n");
    }
    printf("+-----------------------+\n");

}

bool canbe(int temp, int x, int y) {

    int i;

    /* check columns and lines*/
    for (i = 0; i < 9; i++) {
        if (matrix[i][y] == temp || matrix[x][i] == temp) {
            return false;
        }
    }

    /* check squares */
    int X = x / 3;
    int Y = y / 3;

    int j;
    for (i = 0; i < 3; ++i) {
        for (j = 0; j < 3; ++j) {
            if (matrix[X*3+i][Y*3+j] == temp) {
                return false;
            }
        }
    }

    return true;
}

void solve(int x, int y) {

    int i;

    if (y == 9) {
        x++;
        y = 0;
    }

    if (matrix[x][y] == 0) {

        for (i = 1; i <= 9; ++i) {

            if (canbe(i, x, y)) {

                matrix[x][y] = i;

                if (x == 8 && y == 8) {
                    printf("\tFinal:\n");
                    show();
                    exit(0);
                }

                solve(x, y+1);
                matrix[x][y] = 0;
            }
        }
    }

    else {
        if (x == 8 && y == 8) {
            printf("\tFinal:\n");
            show();
            exit(0);
        }
        solve(x, y+1);
    }
}

int main(int argc, char** argv) {

    int i, j;

    for (i = 0; i < 9; i++)
        for (j = 0; j < 9; j++)
            scanf("%d", &matrix[i][j]);

    printf("\tInitial:\n");
    show();
    solve(0, 0);
    printf("Impossible to solve\n");

	return 0;
}