problem
solution
codes
//(如果你玩数独会怎么填呢)......启发式:把能确定的填上 #include<iostream> using namespace std; const int score[10][10]={ {0,0,0,0,0,0,0,0,0,0}, {0,6,6,6,6,6,6,6,6,6}, {0,6,7,7,7,7,7,7,7,6}, {0,6,7,8,8,8,8,8,7,6}, {0,6,7,8,9,9,9,8,7,6}, {0,6,7,8,9,10,9,8,7,6}, {0,6,7,8,9,9,9,8,7,6}, {0,6,7,8,8,8,8,8,7,6}, {0,6,7,7,7,7,7,7,7,6}, {0,6,6,6,6,6,6,6,6,6} }; //r[i][j],第i行第j个数是否填过...row_cnt[i],第i行填了几个数 int a[11][11], row[11][11], col[11][11], area[11][11]; int row_cnt[11], col_cnt[11], cnt, ans=-1; //得到(r,c)是第几个区域的 inline int id(int r, int c){ return (r-1)/3*3+(c-1)/3+1; } //计算当前得分 inline int calc(){ int sum = 0; for(int i = 1; i <= 9; i++) for(int j = 1; j <= 9; j++) sum += score[i][j]*a[i][j]; return sum; } void dfs(int r, int c, int cc){ if(cc == 81){ ans = max(ans, calc()); return ; }else for(int i = 1; i <= 9; i++){//尝试每个填数 if(row[r][i]||col[c][i]||area[id(r,c)][i]) continue; row[r][i] = col[c][i] = area[id(r,c)][i] = 1; row_cnt[r]++; col_cnt[c]++; a[r][c] = i; //找没有填的最少的行和列 int tr, vr=-1, tc, vc=-1; for(int j = 1; j <= 9; j++) if(row_cnt[j]>vr && row_cnt[j]!=9) vr = row_cnt[tr=j]; for(int j = 1; j <= 9; j++) if(col_cnt[j]>vc && !a[tr][j])//(r,c)未填数 vc = col_cnt[tc=j]; dfs(tr,tc,cc+1); row[r][i] = col[c][i] = area[id(r,c)][i] = 0; row_cnt[r]--; col_cnt[c]--; a[r][c] = 0; } } int main(){ //datein for(int i = 1; i <= 9; i++){ for(int j = 1; j <= 9; j++){ cin>>a[i][j]; if(a[i][j]){ //更新初始数据 row[i][a[i][j]] = col[j][a[i][j]] = area[id(i,j)][a[i][j]] = 1; row_cnt[i]++; col_cnt[j]++; cnt++; } } } //找没有填的最少的行和列。 int tr, vr=-1, tc, vc=-1; for(int i = 1; i <= 9; i++) if(row_cnt[i]>vr && row_cnt[i]!=9) vr = row_cnt[tr=i]; for(int i = 1; i <= 9; i++) if(col_cnt[i]>vc && !a[tr][i]) vc = col_cnt[tc=i]; //dfs dfs(tr,tc,cnt); cout<<ans<<"\n"; return 0; }