Sudoku is a logic-based number-placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid.

Here I present a solution to solve sudoku with a simple backtracking. I use bitmask to mark the number already used in each row, column and block. I can't estimate what is the time complexity of my code, but I guarantee it's fast enough (< 1 secs on my laptop). There is another efficient solution using dancing link but more harder to code.

Here's the full c++ code:

```
```
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

#include "stdio.h"
int board[9][9];
int fi[9]; // forbidden row
int fj[9]; // forbidden column
int fk[9]; // forbidden block
int solve(int p) {
if(p==0)
{
for(int a=0;a<9;a++) fi[a]=fj[a]=fk[a]=0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(board[i][j]!=0)
{
int x = 1<<(board[i][j]-1);
int k = i / 3 * 3 + (j / 3);
fi[i] |= x;
fj[j] |= x;
fk[k] |= x;
}
}
if(p==81) return 1;
int i = p / 9; // calculate row position
int j = p % 9; // calculate column position
int k = i / 3 * 3 + (j / 3); // calculate block position
if(board[i][j]!=0) return solve(p+1);
for(int no=1;no<=9;no++)
{
int x = 1<<(no-1);
// check the bit
if(fi[i] & x) continue;
if(fj[j] & x) continue;
if(fk[k] & x) continue;
// mark the bit
fi[i] |= x;
fj[j] |= x;
fk[k] |= x;
board[i][j] = no;
// recurse the next level
if(solve(p+1)==1) return 1;
board[i][j] = 0;
// clear the bit
fi[i] &= ~x;
fj[j] &= ~x;
fk[k] &= ~x;
}
return 0;
}
int main() {
// fill the board in here
// end of fill the board
// print the result
if(solve(0)==0) puts("no solution");
else {
for(int i=0;i<9;i++,puts(""))
for(int j=0;j<9;j++)
printf("%d",board[i][j]);
}
return 0;
}

You are right. The program is rather fast in my computer, but compare with dlx method, the dlx program is more faster.

ReplyDeleteThomas,

I need some help with using your code

ReplyDeleteemail me a kmowa298@gmail.com