ichirin2501's diary

いっちりーん。

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追加