Sudoku Solver (C++)

What is Sudoku ?
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;
}