程序员人生 网站导航

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个;
  2. 该位置在所在行(列、宫)的所有未肯定位置的候选集该值只出现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); } };


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐