- 论坛徽章:
- 0
|
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
class Solution {
public:
bool solveSudoku(vector<vector<char>>& board)
{
if (board.empty()) return false;
total = 0;
return this->solveSudoku_impl(board, 0);
}
int solveSudoku_impl(vector<vector<char>>& board, int id)
{
while (id < 81 && board[id/9][id%9] != '.') ++id;
if (id >= 81) {
++total;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++i) {
std::cout <<board[i][j] <<'\n'
}
}
return total;
}
for (int i = 1; i < 9; ++i) {
if (validSudoku(board, id/9, id%9, '0'+i)) {
board[id/9][id%9] = '0' + i;
if (solveSudoku_impl(board, id+1)) return true;
}
}
board[id/9][id%9] = '.';
}
bool validSudoku(vector<vector<char>>& board, int row, int col, char cc)
{
for (int i = 0; i < 9; ++i) {
if (board[row][i] == cc) return false;
}
for (int j = 0; j < 9; ++j) {
if (board[j][col] == cc) return false;
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (board[(row/3)*3 + i][(col/3)*3 + j] == cc) return false;
}
}
}
private:
int total;
};
int main()
{
char puzzle[][9] = {\
{'.','.','.','5','.','.','.','.','.'}, \
{'.','1','.','.','.','8','.','.','9'}, \
{'.','.','4','.','.','.','6','.','.'}, \
{'.','.','.','8','7','.','.','5','.'}, \
{'4','.','.','.','.','.','.','.','8'}, \
{'.','.','.','9','.','1','.','.','3'}, \
{'.','6','.','.','9','.','2','4','.'}, \
{'.','.','.','.','.','.','.','7','.'}, \
{'5','4','2','.','.','.','.','3','.'} \
};
vector<vector<char> > board(9, vector<char> (9, '.'));
/***
board.resize(9);
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j) {
board[i].push_back(puzzle[i][j]);
}
***/
Solution solve;
int ret = solve.solveSudoku(board);
getchar();
return 0;
}
|
|