覆面算、辞書を作って唯一解を量産するfuku8.c

ライブラリ libncurses5-dev が必要

$ sudo apt-get install libncurses5-dev

だったかな

$ gcc -o fuku8 fuku8.c
$ ./fuku8

で実行。計算が長いので、qボタンかESCボタンで中断

$ ./fuku8

で中断したところから再開。辞書ファイルeng2.dicが必要。今からブログにかくよ

実行結果は、fuku8a.txtを見ること

計算が最後まで終わり、再び最初からはじめたい場合は

$ rm fuku8a.try
($ rm fuku8a.txt)





#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <termios.h>  /* ライブラリ libncurses5-dev が必要 */
#include <term.h>
enum {FALSE,TRUE};
#define N 10
#define MAX 128
#define EEOF 0xff

/* 中断データは終わったら削除すること */
/* qボタン、ESCボタンを押すと中断、実行ファイルで再開 */

char  txt[20]="fuku8a.txt"; /* セーブするファイル名 */
char ttry[20]="fuku8a.try"; /* 中断データを入れるファイル名 */
char dict[20]="eng2.dic";

/*
覆面算

参考資料：

技術評論社　奥村晴彦　著
C言語による最新アルゴリズム事典　２３３０円＋税
P238〜239より引用・改変

*/

struct line{
   unsigned char text[128];
   long  count;
   struct line *next;
};

struct line *stt,*start,*last,*gcdata,*info,*gc2;
struct line *node_create();

static struct termios initial_settings, new_settings;
static int peek_character = -1;

void init_keyboard();
void close_keyboard();
int kbhit();
int readch();

int imax,jmax,solution,ch;
int word[ N][128],digit[ 256];
int word1[N][128],digit1[256];
int low[256],ok[256];
FILE *fp;

void found();
void found1();
void try(int sum);
void input(int i,unsigned char buffer[128]);

void found(){
   int i,j,c;

   ++solution;
   if(solution>1) return;
   for(i=0;i<=imax;i++){
      for(j=jmax;j>=0;j--){
         c=word1[i][j]=word[i][j];
         if(0x41<=c&&c<=0x5a) c+=0x20;
         if(c) digit1[c]=digit[c];
         else  digit1[c]=' ';
      }
   }
}

void found1(){
   int i,j,c;

  fp=fopen(txt,"a");
  if(fp==NULL){
     printf("fail\n");
     exit(1);
   }

   printf("\33[2J\33[0;0H");
   printf("\n 唯一解 \n");
   fprintf(fp,"\n 唯一解 \n");
   for(i=0;i<=imax;i++){
      for(j=jmax;j>=0;j--){
         c=word1[i][j];
         if(c){
            printf("%c",c);
            fprintf(fp,"%c",c);
         }
         else{
            printf(" ");
            fprintf(fp," ");
         }
      }
      printf("\n");
      fprintf(fp,"\n");
   }
   printf("\n");
   fprintf(fp,"\n");

   for(i=0;i<=imax;i++){
      for(j=jmax;j>=0;j--){
         c=word1[i][j];
         if(0x41<=c&&c<=0x5a) c+=0x20;
         if(c){
            printf("%d",digit1[c]);
            fprintf(fp,"%d",digit1[c]);
         }
         else{
            printf(" ");
            fprintf(fp," ");
         }
      }
      printf("\n");
      fprintf(fp,"\n");
   }
   printf("\n");
   fprintf(fp,"\n");
   fclose(fp);
}

void try(int sum){
   static int i=0,j=0,carry;
   int c,d;

   c=word[i][j];
   if(0x41<=c&&c<=0x5a) c+=0x20;
   if(i<imax){
      i++;
      if((d=digit[c])<0){
         for(d=low[c];d<=9;d++){
            if(ok[d]){
               digit[c]=d; ok[d]=FALSE;
               try(sum+d); ok[d]=TRUE;
            }
         }
         digit[c]=-1;
      }
      else try(sum+d);
      i--;
   }
   else{
      j++; i=0; d=sum%10; carry=sum/10;
      if(digit[c]==d){
         if(j<=jmax) try(carry);
         else if(carry==0) found();
      }
      else if(digit[c]<0&&ok[d]&&d>=low[c]){
          digit[c]=d; ok[d]=FALSE;
          if(j<=jmax) try(carry);
          else if(carry==0) found();
          digit[c]=-1; ok[d]=TRUE;
      }
      j--; i=imax;
   }
}

main(){
   int i,j,k,c,p,q,r,s,t,u,z;
   static unsigned char buffer[128];
   int pos,gyo;
   char cp;

   fp=fopen(dict,"r");
   if(fp==NULL){
      printf("cannot open file %s \n",dict);
      exit(1);
   }
   printf("file name %s \n",dict);

   gyo=1;pos=0;
   gcdata=start=gc2=node_create();
   while( (cp=getc(fp)) != EEOF){
      if(cp=='\n'){
         gcdata->text[pos]='\0';
         gcdata->count=1;
         gcdata->next =node_create();
         gc2          =gcdata;
         gcdata       =gcdata->next;
         pos=0;gyo++;
      }
      else{
         if(pos>=MAX) break;
         gcdata->text[pos++]=cp;
      }
   }
   gc2->next=NULL;;
   gyo--;
   fclose(fp);

   init_keyboard();
   printf("\33[2J\33[0;0H");
   jmax=0;
   imax=3;
   printf("計算式の行数は?: %d",imax); imax--;

   fp=fopen(ttry,"r");
   if(fp==NULL){
      printf("中断データはありません\n");
      fp=fopen(txt,"a");
      if(fp==NULL){
         printf("fail\n");
         exit(1);
      }
       printf(   "辞書の行数は %d\n",gyo);
      fprintf(fp,"辞書の行数は %d\n",gyo);
      fclose(fp);
   }
   else{
      fscanf(fp,"%d,%d,%d",&p,&q,&r);
      r++;
      fclose(fp);

      fp=fopen(txt,"a");
      if(fp==NULL){
         printf("fail\n");
         exit(1);
      }
       printf(   "p=%d q=%d r=%d から再開します\n",p,q,r);
      fprintf(fp,"p=%d q=%d r=%d から再開します\n",p,q,r);
      fclose(fp);
      goto SAIKAI;
   }


   for(p=0;p<gyo;p++){
      for(q=p;q<gyo;q++){
      for(r=0;r<gyo;r++){
SAIKAI:
            z++;
            if(z%256==0){
               printf("\33[0;0Hp=%d q=%d r=%d       \n",p,q,r);
               z=0;
            }
            for(j=0;j<N;j++)
               for(i=0;i<128;i++) word[j][i]=0;
            for(i=0;i<256;i++) digit[i]=0;
            for(i=0;i<256;i++) low[i]=0;
            for(i=0;i<256;i++) ok[i]=0;
            i=0;info=start;
            while(i<p&&info){ info=info->next;i++;}
            input(0,info->text);
            i=0;info=start;
            while(i<q&&info){ info=info->next;i++;}
            input(1,info->text);
            i=0;info=start;
            while(i<r&&info){ info=info->next;i++;}
            input(2,info->text);

            for(i=0;i<=9;i++) ok[i]=TRUE;
            solution=0; try(0);
            if(solution==1) found1();
            if(kbhit()){
               ch = readch();
               if(ch=='q'||ch==0x1b){
                  fp=fopen(ttry,"w");
                  if(fp==NULL){
                     printf("fail\n");
                     exit(1);
                   }
                   printf(   "p=%d q=%d r=%d で中断します\n",p,q,r);
                   fprintf(fp,"%d,%d,%d\n",p,q,r);
                   fclose(fp);
                   close_keyboard();
                   exit(0);
                }
            }
         }
      }
   }

   fp=fopen(ttry,"w");
   if(fp==NULL){
      printf("fail\n");
      exit(1);
   }
   printf(   "p=%d q=%d r=%d で終了しました\n",p,q,r);
   fprintf(fp,"%d,%d,%d\n",p,q,r);
   fclose(fp);

   close_keyboard();
}


void input(int i,unsigned char buffer[128]){
   int k,j,c;

     c=buffer[0];
     if(0x41<=c&&c<=0x5a) c+=0x20;
     low[c]=1;
      k=strlen((char *)buffer)-1;
      if(k>jmax) jmax=k;
      for(j=0;j<=k;j++){
         c=word[i][j]=buffer[k-j];
         if(0x41<=c&&c<=0x5a) c+=0x20;
         if(isalpha(c)) digit[c]=-1;
         else if(isdigit(c)) digit[c]=c-'0';
      }
}



void init_keyboard()
{
    tcgetattr(0, &initial_settings);
    new_settings = initial_settings;
    new_settings.c_lflag &= ~ICANON;
    new_settings.c_lflag &= ~ECHO;
    new_settings.c_lflag &= ~ISIG;
    new_settings.c_cc[VMIN] = 0;
    new_settings.c_cc[VTIME] = 0;
    tcsetattr(0, TCSANOW, &initial_settings);
}

void close_keyboard()
{
    tcsetattr(0, TCSANOW, &initial_settings);
}

int kbhit()
{
    char ch;
    int nread;

    if(peek_character != -1)
        return 1;
    new_settings.c_cc[VMIN]=0;
    tcsetattr(0, TCSANOW, &new_settings);
    nread = read(0, &ch, 1);
    new_settings.c_cc[VMIN]=1;
    tcsetattr(0, TCSANOW, &new_settings);

    if(nread == 1) {
        peek_character = ch;
        return 1;
    }
    return 0;
}


int readch()
{
    char ch;

    if(peek_character != -1) {
        ch = peek_character;
        peek_character = -1;
        return ch;
    }
    read(0, &ch, 1);
    return ch;
}


struct line *node_create()
{
   struct line *from;
   int size;

   size=sizeof(struct line);
   from=(struct line *)malloc(size);
   if(!from){
      printf("out of memory \n");
      exit(1);
   }
   from->next=NULL;

   return from;
}