#include <iostream>
#include <deque>
#include <vector>
using namespace std;
bool no_num(vector<char> num, char ch_num)
{
for (int i = 0; i<num.size(); i++)
{
if (num[i] == ch_num)return false;
}
return true;
}
bool no_num2d(vector<vector<char>> num, char ch_num)
{
for (int i = 0; i < num.size(); i++)
{
for (int j = 0; j < num.size(); j++)
{
if (num[i][j] == ch_num)return false;
}
}
return true;
}
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
vector<int> flag;
vector<vector<char>> num_all;
for (int i = 0; i<9; i++)
{
for (int j = 0; j<9; j++)
{
if (board[i][j] == '.')
{
flag.push_back(i);
flag.push_back(j);
int rectx = i / 3 * 3;
int recty = j / 3 * 3;
vector<char> num;
for (int row = 0; row<9; row++)
{
if (board[i][row] != '.'&&no_num(num, board[i][row]))
{
num.push_back(board[i][row]);
}
if (board[row][j] != '.'&&no_num(num, board[row][j]))
{
num.push_back(board[row][j]);
}
if (board[rectx + row / 3][recty + row % 3] != '.'&&no_num(num, board[rectx + row / 3][recty + row % 3]))
{
num.push_back(board[rectx + row / 3][recty + row % 3]);
}
}
num_all.push_back(num);
}
}
}
int flag1 = 0, flag2 = 0;
vector<int> num_size;
for (int i = 0; i<flag.size(); i++)
{
if (i % 2 == 1)
{
num_size.push_back(num_all[i / 2].size());
}
}
if (num_size.size()>0)
{
sort(num_size.begin(), num_size.end());
for (int i = 0; i < num_size.size();i++)
{
if (num_size[num_size.size() - 1] == 9)
{
return;
}
}
}
vector<char> temp;
while (!no_num2d(board, '.'))
{
/*cout << "===========================" << endl;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << " " << board[i][j];
}
cout << endl;
}
cout << "===========================" << endl;
cout << endl;*/
for (int i = 0; i < flag.size(); i++)
{
if (i % 2 == 1)
{
/*cout<<"board["<<flag[i-1]<<"]["<<flag[i]<<"]:";
for(int j=0;j<num_all[i/2].size();j++)
{
cout<<num_all[i/2][j]<<" ";
}
cout<<endl;*/
if (num_all[i / 2].size() == num_size[num_size.size() - 1] && num_all[i / 2].size() < 9)
{
int flag_num9 = 0;
for (int num9 = 0; num9 < 9; num9++)
{
char ch_num = '1' + num9;
if (no_num(num_all[i / 2], ch_num) && no_num(temp, ch_num))
{
board[flag[i - 1]][flag[i]] = ch_num;
temp.push_back(ch_num);
flag_num9 = 1;
break;
}
}
if (flag_num9 == 0)
{
board[flag[i - 1]][flag[i]] = '.';
return;
}
break;
}
}
}
solveSudoku(board);
}
return;
// else
// return;
}
};
评论0