leetcode037：Sudoku Solver
栏目：php教程时间：2015-05-26 07:50:00
问题描写
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.
问题分析
数独解法基本靠暴力求解，在所有无肯定的位置对所有可能的解进行尝试，直接暴力解运行时间是153ms。所以在此之前先肯定唯1解的位置，唯1解有两种类型。
- 该位置在所在行、列、宫上都满足的情况下的候选集只有1个；
- 该位置在所在行（列、宫）的所有未肯定位置的候选集该值只出现1次。
代码
//Runtime: 17 ms
class Solution {
public:
bool fun(vector<vector<char> > &board, int i, int j, int size) {
for (; i < board.size(); i++){
if (j == board[i].size()) j = 0;
for (; j < board[i].size(); j++){
if (board[i][j] == '.'){
int a[10];
int b[10];
int c[10];
//初始化
memset(a, 0, sizeof(int) * 10);
memset(b, 0, sizeof(int) * 10);
memset(c, 0, sizeof(int) * 10);
for (int m = 0; m < board[i].size(); m++){
int k = board[i][m] - '0';
if (k <= 9 && k >= 1){
a[k] = 1;
}
}
for (int m = 0; m < board.size(); m++){
int k = board[m][j] - '0';
if (k <= 9 && k >= 1){
b[k] = 1;
}
}
int s = i / 3 * 3;
int t = j / 3 * 3;
for (int m = 0; m < 9; m++){
int k = board[s + m / 3][t + m % 3] - '0';
if (k <= 9 && k >= 1){
c[k] = 1;
}
}
for (int k = 1; k <= 9; k++){
if (!a[k] && (!b[k]) && (!c[k])){
board[i][j] = k + '0';
if (j + 1 == board[i].size() && fun(board, i + 1, 0, size)){
return true;
}
else if (fun(board, i, j + 1, size)){
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
void solveSudoku(vector<vector<char> > &board) {
int a[9][10]; //处理行
int b[9][10]; //处理列
int c[9][10]; //处理单元
//初始化
for (int i = 0; i < 9; i++){
memset(a + i, 0, sizeof(int) * 10);
memset(b + i, 0, sizeof(int) * 10);
memset(c + i, 0, sizeof(int) * 10);
}
int m, n;
int size = 0;
for (int i = 0; i < board.size(); i++){
for (int j = 0; j < board[i].size(); j++){
int k = board[i][j] - '0';
if (k <= 9 && k >= 1){
size++;
a[i][k] = 1;
b[j][k] = 1;
m = i / 3 * 3 + j / 3;
c[m][k] = 1;
}
}
}
int x = 0;
map<int, vector<int> > ma;
map<int, vector<int>> mb[9];
map<int, vector<int>> mc[9];
int pre;
do{
pre = size;
for (int i = 0; i < board.size(); i++){
for (int j = 0; j < board[i].size(); j++){
if (board[i][j] == '.'){
int count = 0;
m = i / 3 * 3 + j / 3;
for (int k = 1; k <= 9; k++){
if (!a[i][k] && (!b[j][k]) && (!c[m][k])){
ma[k].push_back(j);
mb[j][k].push_back(i * 9 + j);
mc[m][k].push_back(i * 9 + j);
}
}
}
}
map<int, vector<int> >::iterator it;
for (it = ma.begin(); it != ma.end(); it++){
if (it->second.size() == 1 && board[i][it->second.front()] == '.'){
size++;
board[i][it->second.front()] = '0' + it->first;
a[i][it->first] = 1;
b[it->second.front()][it->first] = 1;
m = i / 3 * 3 + it->second.front() / 3;
c[m][it->first] = 1;
}
}
ma.clear();
}
for (int i = 0; i < 9; i++){
for (auto it : mb[i]){
int x = it.second.front() / 9;
int y = it.second.front() % 9;
if (it.second.size() == 1 && board[x][y] == '.'){
size++;
board[x][y] = '0' + it.first;
a[x][it.first] = 1;
b[y][it.first] = 1;
m = x / 3 * 3 + y / 3;
c[m][it.first] = 1;
}
}
mb[i].clear();
for (auto it : mc[i]){
int x = it.second.front() / 9;
int y = it.second.front() % 9;
if (it.second.size() == 1 && board[x][y] == '.'){
size++;
board[x][y] = '0' + it.first;
a[x][it.first] = 1;
b[y][it.first] = 1;
m = x / 3 * 3 + y / 3;
c[m][it.first] = 1;
}
}
mc[i].clear();
}
//cout << size << endl;
//x++;
} while (pre < size && size < 81);
if (size == 81) return;
fun(board, 0, 0, size);
}
};
------分隔线----------------------------
------分隔线----------------------------