[leetcode solution/37]Sudoku Solver

Datetime:2017-04-02 05:28:40         Topic: LeetCode          Share        Original >>
Here to See The Original Article!!!

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;
};







New