Project Euler 96
http://projecteuler.net/index.php?section=problems&id=96
与えられた数独を解いたときの一番左上の3桁の和を答える問題です。
単純判定で確定部分を埋めて、残りは全探索した。
無駄にコードが長くなってしまった。
#include <iostream> #include <string> using namespace std; typedef struct sudoku{ int kakutei; int kouho[10]; }t_sudoku; t_sudoku table[9][9]; int ok; void input() { string str; for(int i=0; i<9; i++){ getline(cin,str); for(int j=0; j<9; j++){ table[i][j].kakutei = str[j]-'0'; for(int k=0; k<10; k++) table[i][j].kouho[k] = 0; } } } void set_checkno(int x, int y, int w, int h, int* nolist) { for(int i=0; i<h; i++) for(int j=0; j<w; j++) if(table[y+i][x+j].kakutei) nolist[table[y+i][x+j].kakutei] = 1; } int count_checkno(int x, int y, int w, int h, int* nolist) { int bit[10]; memset(bit,0,sizeof(bit)); for(int i=0; i<h; i++) for(int j=0; j<w; j++) if( table[i+y][j+x].kakutei==0 ) for(int k=1; k<=9; k++) bit[k] += !table[i+y][j+x].kouho[k]; for(int k=1; k<=9; k++) if( bit[k]==1 && nolist[k]==0 ) return k; return 0; } bool ischeck(int x, int y, int w, int h, int number) { for(int i=0; i<h; i++) for(int j=0; j<w; j++) if( table[i+y][j+x].kakutei==number ) return false; return true; } void dfs(int n) { if(!n){ ok = 1; return; } for(int i=0; i<9; i++){ for(int j=0; j<9; j++){ if( table[i][j].kakutei==0 ){ for(int k=1; k<=9; k++){ if( table[i][j].kouho[k]==0 && ischeck(j,0,1,9,k) && ischeck(0,i,9,1,k) && ischeck((j/3)*3,(i/3)*3,3,3,k) ){ table[i][j].kakutei = k; dfs(n-1); if(ok)return; table[i][j].kakutei = 0; } } return; } } } } int main() { int ans = 0; string str; while(getline(cin,str)){ input(); ok = 0; for(int i=0; i<9; i++){ for(int j=0; j<9; j++){ if( table[i][j].kakutei==0 ){ set_checkno(j, 0, 1, 9, table[i][j].kouho); set_checkno(0, i, 9, 1, table[i][j].kouho); set_checkno((j/3)*3, (i/3)*3, 3, 3, table[i][j].kouho); } } } for(;;){ int flag = 0; for(int i=0; i<9; i++){ for(int j=0; j<9; j++){ if( table[i][j].kakutei==0 ){ set_checkno(j, 0, 1, 9, table[i][j].kouho); set_checkno(0, i, 9, 1, table[i][j].kouho); set_checkno((j/3)*3, (i/3)*3, 3, 3, table[i][j].kouho); int num=0; num = count_checkno((j/3)*3, (i/3)*3, 3, 3, table[i][j].kouho); if( num ){ table[i][j].kakutei = num; flag=1; continue; } num = count_checkno(j, 0, 1, 9, table[i][j].kouho); if( num ){ table[i][j].kakutei = num; flag=1; continue; } num = count_checkno(0, i, 9, 1, table[i][j].kouho); if( num ){ table[i][j].kakutei = num; flag=1; continue; } } } } if( !flag )break; } if( table[0][0].kakutei==0 || table[0][1].kakutei==0 || table[0][2].kakutei==0 ){ int n = 0; for(int i=0; i<9; i++) for(int j=0; j<9; j++) if( table[i][j].kakutei==0 )n++; dfs(n); } ans += table[0][0].kakutei*100 + table[0][1].kakutei*10 + table[0][2].kakutei; cout<<str<<endl; for(int i=0; i<9; i++){ for(int j=0; j<9; j++){ printf("%d",table[i][j].kakutei); } puts(""); } } printf("ans:%d\n",ans); return 0; }
2010/04/02
少しコードを手直し。
int check() --> bool ischeck()
あと、個人的に不要と思える括弧の排除or追加