1.对于当前的数独状态,我们可以把每个未填的位置的候选数字全部找出来,可以将候选数字放到一个数组或在vector中
vector <int> find(int x, int y); //找出soudu[x][y]的候选数字2.如果有一些未填位置的候选数字为一个,那么这个就是确定项,我们可以先确定填补这个位置,如果所有的未填位置的候选数字都不唯一,那么选择候选数字最少的那么位置,遍历所有的可能性
3.怎么判断已解出答案,以及无法继续进行下去,要回溯前一步的状态呢, 搜先,设计一个 更新函数,每填补一个位置,就更新所有的未填位置的候补数字, void update(); 其次,设计几个全局变量, 一个用来判断,当前状态是否有更新,如果没有更新,认定为所有的位置已经填满,已解出答案,则输出结果, bool can_update; 还有用bool can_continue来判断是否存在某个未填位置没有候选数字可填,这种情况, 无法继续填数字 ; 另外, 在设计一个pair
#include<iostream> #include<vector> #include<utility> using namespace std; //初始化数独 int soudu[9][9] = { 0,0,0,0,6,0,7,0,0, 0,8,0,0,0,0,0,2,0, 0,0,0,9,0,7,0,0,1, 0,0,0,0,0,0,1,0,0, 0,3,6,0,0,0,4,8,0, 0,0,0,0,7,0,0,0,0, 7,0,0,2,0,0,0,0,0, 0,5,0,0,0,0,0,6,0, 0,0,2,0,4,6,0,0,0}; //用来记录每个位置的候选数字, index = row*9 + col vector <int > pos[81]; // 记录是否更新,若无更新,说明已填满所有数字 bool can_update = true; // 判断是否还可以继续下去,若ok=false, 那么说明存在一个未填位置,没有任何候选数字 bool ok = true; pair < int, int > chosen_item; // (chose_position, the_possible_chose_number) int step = 0; int sol = 0; int is_over = false; vector<int> find(int x, int y); void update(); void print(); void sol_soudu() { step++; update(); if (!can_update) { sol++; if (sol >= 10) is_over = true; // this is a solution print(); } else if (!ok) { // there is a blank can not fill any number return ; } else if (!is_over) { int position = chosen_item.first; int x = position / 9; int y = position - x * 9; //选择用size和k记录下大小和vector,是因为在往下深搜时,chose你_item会发生改变 int size = chosen_item.second; vector <int> k = pos[position]; for (int i = 0; i < size; i++) { soudu[x][y] = k[i]; sol_soudu(); // 回溯, 还原数据, 注意要还原ok, 因为有可能前面的深搜,都没有正确答案,导致ok=false soudu[x][y] = 0; ok = true; } } } vector <int> find(int x, int y) { int a[10] = {0}; vector <int> ret; for (int i = 0; i < 9; i++){ if (soudu[x][i] > 0) a[soudu[x][i]] = 1; if (soudu[i][y] > 0) a[soudu[i][y]] = 1; } int block_row = x / 3, block_col = y / 3; for (int i = block_row*3; i < block_row*3 + 3; i++) for (int j = block_col * 3; j < block_col*3 + 3; j++) { if (soudu[i][j] > 0) a[soudu[i][j]] = 1; } for (int i = 1; i <= 9; i++) if (!a[i]) ret.push_back(i); return ret; } void update() { for (int i = 0; i < 81; i++) pos[i].clear(); chosen_item = make_pair(0, 10); can_update = false; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (!soudu[i][j]) { int k = i * 9 + j; pos[k] = find(i, j); if (pos[k].empty()) ok = false; if (pos[k].size() < chosen_item.second) chosen_item = make_pair(k, pos[k].size()); can_update = true; } } void print() { cout << "-----------------------" << endl; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) { cout << soudu[i][j] << " "; if (j == 8) cout << endl; } cout << "-----------------------" << endl; } int main() { sol_soudu(); cout << "step:" << step << endl; cout << "sol:" << sol << endl; return 0; }