#include <iostream>
using namespace std;
#include <vector>
#include <utility>
const int MAX_SIZE = 9;
//int result[MAX_SIZE][MAX_SIZE] = {
// {1, 2, 3, 4, 5, 6, 7, 8, 9},
// {4, 6, 7, 1, 8, 9, 3, 2, 5},
// {5, 8, 9, 2, 3, 7, 1, 4, 6},
// {3, 1, 6, 5, 4, 8, 2, 9, 7},
// {2, 7, 8, 9, 6, 1, 5, 3, 4},
// {9, 4, 5, 7, 2, 3, 8, 6, 1},
// {7, 3, 1, 6, 9, 2, 4, 5, 8},
// {8, 9, 4, 3, 7, 5, 6, 1, 2},
// {6, 5, 2, 8, 1, 4, 9, 7, 3}
//};
int result[MAX_SIZE][MAX_SIZE] = {
{0, 6, 0, 5, 9, 3, 0, 0, 0},
{9, 0, 1, 0, 0, 0, 5, 0, 0},
{0, 3, 0, 4, 0, 0, 0, 9, 0},
{1, 0, 8, 0, 2, 0, 0, 0, 4},
{4, 0, 0, 3, 0, 9, 0, 0, 1},
{2, 0, 0, 0, 1, 0, 6, 0, 9},
{0, 8, 0, 0, 0, 6, 0, 2, 0},
{0, 0, 4, 0, 0, 0, 8, 0, 7},
{0, 0, 0, 7, 8, 5, 0, 1, 0}
};
int index[3][3][2] =
{
{
{0,0},{0,3},{0,6}
},
{
{3,0},{3,3},{3,6}
},
{
{6,0},{6,3},{6,6}
}
};
int one_to_nine[9] = {0};
bool try_number[9];
vector<int> try_number_vector;
vector<vector<vector<int> > > loop_all;
vector<pair<vector<int>,pair<int,int> > > loop_line;
typedef vector<pair<vector<int>,pair<int,int> > >::iterator loop_line_itr_type;
vector<int> loop_array;
vector<int> loop_next;
int loop_length =0;
int total_try = 0;
long long total_case = 1;
void clean_try_number(void);
void get_line_number(int x);
void get_column_number(int y);
void get_mutrix_number(int x, int y);
void print_try_number(void);
bool check_shudu(void);
void clean_try_number(void)
{
for (int i=0; i< 9; ++i)
{
try_number[i] = true;
}
try_number_vector.clear();
}
void get_line_number(int x)
{
for (int i=0; i < 9; ++i)
{
//这个数字已经出现
if (result[x][i] != 0)
{
//cout<<"line_number fined:["<<x<<"]["<<i<<"]: "<<result[x][i]<<endl;
try_number[result[x][i]-1] = false;
}
}
}
void get_column_number(int y)
{
for (int i=0; i < 9; ++i)
{
//这个数字已经出现
if (result[i][y] != 0)
{
//cout<<"column_number fined:["<<i<<"]["<<y<<"]: "<<result[i][y]<<endl;
try_number[result[i][y]-1] = false;
}
}
}
void get_mutrix_number(int x, int y)
{
//cout<<"small matrix: ["<<x<<"] ["<<y<<"]\n";
for (int i=0; i<3; ++i)
{
for (int j=0;j<3;++j)
{
if (result[x+i][y+j] != 0)
{
//cout<<"matrix fined:["<<x+i<<"]["<<y+j<<"]: "<<result[x+i][y+j]<<endl;
try_number[result[x+i][y+j]-1] = false;
}
}
}
}
void get_all_matrix_number(int x, int y)
{
//cout<<"big matrix: ["<<x<<"] ["<<y<<"] ->";
get_mutrix_number(x/3*3,y/3*3);
}
void get_try_number(int x, int y)
{
if(result[x][y] != 0)
{
return;
}
clean_try_number();
get_line_number(x);
get_column_number(y);
get_all_matrix_number(x,y);
for (int i=0; i<9; ++i)
{
if (try_number[i] == true)
{
try_number_vector.push_back(i+1);
}
}
}
void print_try_number(void)
{
cout<<"try_number now is :";
for (int i=0; i<try_number_vector.size();++i)
{
cout<<try_number_vector[i]<<" ";
}
cout<<endl;
}
void use_one_try_number(int x, int y, int vaule)
{
result[x][y] = vaule;
}
void go_back(int x, int y, int value)
{
result[x][y] = value;
}
void print_result(void)
{
for (int i=0; i< 9; ++i)
{
for (int j=0; j<9; ++j)
{
cout<<result[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
void print_loop_line(void)
{
cout<<"loop_line:"<<endl;
for(int i=0;i<loop_line.size();++i)
{
cout<<"loop_line["<<i<<"]:";
for(int j=0;j<loop_line[i].first.size();++j)
{
cout<<loop_line[i].first[j]<<" ";
}
cout<<" ->["<<loop_line[i].second.first<<"]["<<loop_line[i].second.second<<"]\n";
}
}
bool finish_shudu(void)
{
for (int i=0; i< 9; ++i)
{
for (int j=0; j<9; ++j)
{
if (result[i][j] == 0)
{
return false;
}
}
}
}
bool loop_end(void)
{
for(int i=0;i<loop_length;++i)
{
if(loop_next[i] != loop_array[i]-1)
{
return false;
}
}
return true;
}
//
void make_loop_line(void)
{
loop_line.clear();
for(int i=0;i<9; ++i)
{
vector<vector<int> > temp_loop_line;
for(int j=0;j<9; ++j)
{
//cout<<"get_try_number["<<i<<"]["<<j<<"]:";
get_try_number(i,j);
temp_loop_line.push_back(try_number_vector);
if(try_number_vector.size()!=0)
{
loop_line.push_back(make_pair(try_number_vector,make_pair(i,j)));
}
//print_try_number();
clean_try_number();
}
}
}
void init(void)
{
//make loop_line loop_all;
make_loop_line();
//cout<<"loop_all:"<<endl;
for(int i=0;i<loop_all.size();++i)
{
for(int j=0;j<loop_all[i].size();++j)
{
//cout<<"loop_all postion["<<i<<"]["<<j<<"]:";
for(int k=0;k<loop_all[i][j].size();++k)
{
//cout<<loop_all[i][j][k]<<" ";
}
//cout<<endl;
}
//cout<<endl;
}
print_loop_line();
loop_length = loop_line.size();
cout<<"loop_length:"<<loop_length<<endl;
cout<<"init loop_array:";
for(int i=0;i<loop_length;++i)
{
loop_array.push_back(loop_line[i].first.size());
total_case *= loop_line[i].first.size();
}
for(int i=0;i<loop_array.size();++i)
{
cout<<loop_array[i]<<"*";
}
cout<<"\n="<<total_case<<endl;
cout<<"init loop_next:";
for(int i=0;i<loop_length;++i)
{
loop_next.push_back(0);
}
for(int i=0;i<loop_next.size();++i)
{
cout<<loop_next[i]<<" ";
}
cout<<endl;
}
void set_sole_to_position(int x,int y,int sole_value)
{
result[x][y] = sole_value;
}
bool exist_sole(void)
{
for(loop_line_itr_type itr=loop_line.begin();itr != loop_line.end();++itr)
{
if(itr->first.size() == 1)
{
return true;
}
}
return false;
}
void loop_set_sole()
{
int set_sole_times = 0;
while(exist_sole())
{
cout<<"set_sole_to_position "<< ++set_sole_times <<" s time\n";
//把当前loop_line中所有只有一种可能的位置，并将数字放进去
for(loop_line_itr_type itr=loop_line.begin();itr != loop_line.end();)
{
if(itr->first.size() == 1)
{
int erased_value = itr->first[0];
int x = itr->second.first;
int y = itr->second.second;
set_sole_to_position(x,y,erased_value);
itr = loop_line.erase(itr);
cout<<"erased: loop_line["<<x<<"]["<<y<<"]="<<erased_value<<endl;
}
else
{
++itr;
}
}
make_loop_line();
//print_loop_line();
}
}
void do_shudu(void)
{
cout<<"init:"<<endl;
init();
//剪枝
//
loop_set_sole();
cout<<"now result is:"<<endl;
print_result();
if(finish_shudu())
{
cout<<"OK I FINED !"<<endl;
}
else
{
cout<<"cao wrong !"<<endl;
}
}
bool check_one_to_nine(void)
{
bool flag = true;
for(int i=0; i<9; ++i)
{
if(one_to_nine[i]>=2)
{
flag = false;
break;
}
}
for(int i = 0; i< 9; ++i)
{
one_to_nine[i] = 0;
}
return flag;
}
bool check_line(int start)
{
for(int i= 0; i<9; ++i)
{
++one_to_nine[result[start][i]-1];
}
if(check_one_to_nine() == false)
{
//cout<<"check_line:"<<start<<" failed"<<endl;
return false;
}
else
{
//cout<<"check_line:"<<start<<" OK"<<endl;
return true;
}
}
bool check_column(int start)
{
for(int i= 0; i<9; ++i)
{
++one_to_nine[result[i][start]-1];
}
if(check_one_to_nine() == false)
{
//cout<<"check_column:"<<start<<" failed"<<endl;
return false;
}
else
{
//cout<<"check_column:"<<start<<" OK"<<endl;
return true;
}
}
bool check_one_matrix(int xStart, int yStart)
{
for(int i=0; i<3; ++i)
{
for(int j=0; j<3; ++j)
{
++one_to_nine[result[xStart+i][yStart+j]-1];
}
}
if(false == check_one_to_nine())
{
//cout<<"check_one_matrix:"<<xStart<<","<<yStart<<" failed"<<endl;
return false;
}
else
{
//cout<<"check_one_matrix:"<<xStart<<","<<yStart<<" OK"<<endl;
return true;
}
}
bool check_all_matrix()
{
for(int i=0;i<3;++i)
{
for(int j=0;j<3;++j)
{
if(false == check_one_matrix(index[i][j][0], index[i][j][1]))
return false;
}
}
return true;
}
bool check_shudu()
{
for(int i=0;i<9;++i)
{
if(check_line(i) == false || check_column(i) == false)
{
return false;
}
}
if(check_all_matrix() == false)
{
return false;
}
return true;
}
int main(int , char**)
{
cout<<"Hello World!"<<endl;
do_shudu();
return 1;
}
