# [leetcode solution/37]Sudoku Solver

Datetime:2017-04-02 05:28:40         Topic: LeetCode          Share        Original >>

Write a prgram to solve Sodoku puzzle by filling the empty cells.

Empty cells are indicated by character ‘.’

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

A sudoku puzzle

## solution

• There are three limitations in this puzzle
• There are 1 ~ 9 in each row
• There are 1 ~ 9 in each col
• There are 1 ~ 9 in 3 * 3 sub matrix
• There are so many limitatons in this puzzle that we can solve the problem by searching.
• For each empty cell we try 1 ~ 9 for this cell, if it satisfy the limitation above, try the next empty cell.Otherwise we should try the next number.

## code

const int N = 9;
const int M = 10;

struct point {
int r, c;
point() {}
point (int _r, int _c) : r(_r), c(_c) {}
};

class Solution {
public:
voidsolveSudoku(vector<vector<char>>& board){
// mark the used number
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (board[i][j] != '.') {
int val = board[i][j] - '0';
used_row[i][val] = true;
used_col[j][val] = true;
int id = small_id(i, j);
used_small[id][val] = true;
}
}
}
// get the grid id in a special order
for (int i = 0; i < 9; i += 3) {
for (int j = 0; j < 9; j += 3) {
for (int k = 0; k < 3; ++k) {
for (int v = 0; v < 3; ++v) {
int r = i + k;
int c = j + v;
if (board[r][c] == '.') {
//std::cout << "[to_fill]: " << r << " " << c << std::endl;
to_fill.push_back(point(r, c));
}
}
}
}
}
// fill the grids
if (!to_fill.empty()) {
found = false;
ans.resize(to_fill.size());
dfs(0);
for (int i = 0; i < (int)to_fill.size(); ++i) {
int r = to_fill[i].r;
int c = to_fill[i].c;
board[r][c] = ans[i];
}
}
}
voiddfs(intcur){
if (found) {
return;
}
if (cur >= (int)to_fill.size()) {
found = true;
return;
}
const int& r = to_fill[cur].r;
const int& c = to_fill[cur].c;
int id = small_id(r, c);
for (int i = 1; i < M && !found; ++i) {
if (used_row[r][i] || used_col[c][i] || used_small[id][i]) {
continue;
}
used_row[r][i] = used_col[c][i] = used_small[id][i] = true;
ans[cur] = i + '0';
dfs(cur + 1);
used_row[r][i] = used_col[c][i] = used_small[id][i] = false;
}
}
intsmall_id(intr,intc){
int small_r = r / 3;
int small_c = c / 3;
return small_r * 3 + small_c;
}
private:
bool used_row[N][M];
bool used_col[N][M];
bool used_small[N][M];
bool found;
vector<char> ans;
vector<point> to_fill;
};