Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

C++:
01 typedef pair<int, int> Pair;
02 bool sudoku(vector<vector<char> > &board, Pair cur){
03      if(cur.first>=9)
04         return true;
05      int x=cur.first;
06      int y=cur.second;
07      while(board[x][y]!=‘.’){
08          if(y==8){
09              x++;
10              if(x>=9)
11                 return true;
12              y=0;
13          }
14          else
15             y++;
16      }
17      int tmp=0;
18      for(int i=0;i<9;i++){
19          int p=board[i][y]‘0’;
20          int q=board[x][i]‘0’;
21          if((p>=1)&&(p<=9))
22              tmp|=1<<p;
23          if((q>=1)&&(q<=9))
24              tmp|=1<<q;
25      }
26      int a=x/3;
27      int b=y/3;
28      for(int i=3*a;i<3*a+3;i++){
29          for(int j=3*b;j<3*b+3;j++){
30              int p=board[i][j]‘0’;
31              if((p>=1)&&(p<=9))
32                 tmp|=1<<p;
33          }
34      }
35      Pair next;
36      if(y==8){
37          next.first=x+1;
38          next.second=0;
39      }
40      else{
41          next.first=x;
42          next.second=y+1;
43      }
44      for(int i=1;i<=9;i++){
45          if((tmp&(1<<i))==0){
46              board[x][y]=i+‘0’;
47              if(sudoku(board, next)==true)
48                 return true;
49              else
50                 board[x][y]=‘.’;
51          }
52      }
53      return false;
54 }
55 void solveSudoku(vector<vector<char> > &board) {
56       Pair s=Pair(0,0);
57       sudoku(board, s);
58 }
Advertisements
This entry was posted in Array and linked list, Backtrack. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s