Next Spaceship

Driving into future…

A Simple Implementation of Solving Sudoku

| Comments

Sudoku is a popular game. Howerver, solving Sudoku is sometimes not so easy, so I wrote a program to help me do this job.

Solving Suduku
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
// Created by Leon in 2011
// http://leons.im

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
using namespace std;

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

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

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

bool solve(int d) {
    //printf("d=%d\n", d);
    if (81 == d) {
        return true;
    }
    unsigned i = d / 9, j = d % 9;
    if (in[i][j] > 0) {
        return solve(d + 1);
    }
    for (unsigned k = 1; k <= 9; ++k) {
        if (!(pos[i][j] & (1 << k))) {
            //printf("k=%d\n", k);
            out[i][j] = k;
            int m = 1 << k;
            vector<pair<int, int> > v;
            for (unsigned p = 0; p < 9; ++p) {
                if (!(pos[i][p] & m)) {
                    pos[i][p] |= m;
                    v.push_back(make_pair(i, p));
                }
                if (!(pos[p][j] & m)) {
                    pos[p][j] |= m;
                    v.push_back(make_pair(p, j));
                }
            }
            unsigned si = i / 3 * 3, sj = j / 3 * 3;
            for (unsigned p = 0; p < 3; ++p) {
                for (unsigned q = 0; q < 3; ++q) {
                    if (!(pos[si + p][sj + q])) {
                        pos[si + p][sj + q] |= m;
                        v.push_back(make_pair(si + p, sj + q));
                    }
                }
            }
            if (solve(d + 1)) {
                return true;
            }
            //printf("-------\n");
            for (unsigned p = 0; p < v.size(); ++p) {
                pos[v[p].first][v[p].second] &= ~m;
            }
        }
    }
    return false;
}

int main() {
    for (unsigned i = 0; i < 9; ++i) {
        for (unsigned j = 0; j < 9; ++j) {
            printf("%d, ", in[i][j]);

            if (in[i][j] > 0) {
                out[i][j] = in[i][j];
                int m = 1 << in[i][j];
                for (unsigned k = 0; k < 9; ++k) {
                    pos[i][k] |= m;
                    pos[k][j] |= m;
                }
                unsigned si = i/3 * 3, sj = j/3 * 3;
                for (unsigned k = 0; k < 3; ++k) {
                    for (unsigned p = 0; p < 3; ++p) {
                        pos[si + k][sj + p] |= m;
                    }
                }
            }
        }
        printf("\n");
    }
    /*
    for (unsigned i = 0; i < 9; ++i) {
        for (unsigned j = 0; j < 9; ++j) {
            if (0 == in[i][j]) {
                for (unsigned k = 1; k <= 9; ++k) {
                    if (!(pos[i][j] & (1 << k))) {
                        printf("%d,", k);
                    }
                }
            }
            printf("; ");
        }
        printf("\n");
    }
    */
    printf("-----------------\n");
    if (solve(0)) {
        for (unsigned i = 0; i < 9; ++i) {
            for (unsigned j = 0; j < 9; ++j) {
                printf("%d, ", out[i][j]);
            }
            printf("\n");
        }
    }
    else {
        printf("No solution.");
    }
    return 0;
}

Comments