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 bool solveSudokuHelper(vector<vector<char> > &board,
02 vector<set<char>>& Row, vector<set<char>>&Col,
03                        vector<set<char>> Cub, int k)
04 {
05     if(k>=81)
06         return true;
07     int row=k/9;
08     int col=krow*9;
09     if(board[row][col]!=‘.’)
10     {
11         return
12           solveSudokuHelper(board,Row,Col,Cub,k+1);
13     }
14     int p=row/3;
15     int q=col/3;
16     int cubcnt=p*3+q;
17     for(char c=‘1’;c<=‘9’;c++)
18     {
19         if((Row[row].find(c)==Row[row].end())
20         &&(Col[col].find(c)==Col[col].end())
21         &&(Cub[cubcnt].find(c)==Cub[cubcnt].end()))
22         {
23             Row[row].insert(c);
24             Col[col].insert(c);
25             Cub[cubcnt].insert(c);
26             board[row][col]=c;
27             if(solveSudokuHelper(board,Row,Col,Cub,k+1)
28                ==true)
29                 return true;
30             board[row][col]=‘.’;
31             Row[row].erase(c);
32             Col[col].erase(c);
33             Cub[cubcnt].erase(c);
34         }
35     }
36     return false;
37 }
38 class Solution {
39 public:
40     void solveSudoku(vector<vector<char> > &board) {
41         // Start typing your C/C++ solution below
42         // DO NOT write int main() function
43         vector<set<char>> Row(9);
44         vector<set<char>> Col(9);
45         vector<set<char>> Cub(9);
46         for(int i=0;i<9;i++)
47         {
48             for(int j=0;j<9;j++)
49             {
50                 if(board[i][j]!=‘.’)
51                 {
52                     Row[i].insert(board[i][j]);
53                     Col[j].insert(board[i][j]);
54                     int p=i/3;
55                     int q=j/3;
56                     Cub[p*3+q].insert(board[i][j]);
57                 }
58             }
59         }
60         solveSudokuHelper(board, Row, Col, Cub, 0);
61     }
62 };
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