#include <stdio.h>
#include <stdlib.h>
#define XL 8
#define YL 8
#define HN 3
typedef struct s_piclos
{
/* 数字のリスト */
int *xlist;
int *ylist;
/* 行数 */
int xline;
int yline;
int hnum; // ヒントの最大数
/* data */
int *data;
} PICLOS;
int xh[XL][HN] = {
0,0,4,
0,0,6,
2,1,2,
1,1,1,
1,1,1,
2,1,2,
0,3,2,
0,2,1,
};
int yh[YL][HN] = {
0,0,4,
0,2,2,
0,2,2,
0,0,8,
0,0,2,
0,2,2,
0,2,2,
0,0,4,
};
void init(PICLOS *p)
{
p->xline = XL;
p->yline = YL;
p->hnum = HN;
p->xlist = (int*)xh;
p->ylist = (int*)yh;
p->data = (int*)calloc(p->xline*p->yline, sizeof(int));
}
void final(PICLOS *p)
{
free(p->data);
}
void pprint(PICLOS *p)
{
int i,j,k;
const char* const s[20] = {" ", "1","2","3","4","5","6","7","8", "9","10","11","12","13","14","15","16","17","18","19",};
for(j=0;j<p->hnum;j++)
{
for(i=0;i<p->hnum;i++)
{
printf(s[0]);
}
for(i=0;i<p->xline;i++)
{
printf(s[p->xlist[p->hnum*i+j]]);
}
printf("\n");
}
for(j=0;j<p->yline;j++)
{
for(i=0;i<p->hnum;i++)
{
printf(s[p->ylist[p->hnum*j+i]]);
}
for(i=0;i<p->xline;i++)
{
k = p->data[p->xline*j+i];
if(k == 0) printf("□");
if(k == 1) printf("■");
if(k == 2) printf("×");
}
printf("\n");
}
}
int kakutei_sum = 0;
int test_sum(int* dat, int num)
{
int i, res=0;
for(i=0;i<2*num;i++)
{
res += dat[i];
}
return res;
}
/* それ以上の大きさのパターンの有無を確かめる */
int test_chk(int *dat, int cnt, int num)
{
int p = cnt*2 + 2;
while(p<2*num)
{
if(dat[p]!=1) return 0;
p+=2;
}
return(dat[p]<0);
}/* それ以上の大きさのパターンの有無を確かめるための状態をリセット */
void test_reset(int *dat, int cnt, int num)
{
int p = cnt*2 + 2;
while(p<2*num)
{
dat[p] = 0;
p+=2;
}
dat[p] = 0;
}
// void test_sub(int* dat, int cnt, int num, int max, int* kakutei, int* test, int* temp)
// dat:黒+白のデータ
// cnt:現在処理中の白の番号
// num:数字リストの長さ
// max:行の長さ
// kakutei:確定済みのマス
// test:パターンテストのデータ
// temp:テスト用の計算領域
void test_sub(int* dat, int cnt, int num, int max, int* kakutei, int* test, int* temp)
{
int i,j,k;
int p = cnt*2;
if(cnt==0)
{
dat[p] = -1;
test_reset(dat,cnt,num);
}
else if(cnt==num)
{
dat[p] = max - test_sum(dat,num);
if(dat[p]<0)
{
return;
}
// make temp data
i = 0;
for(j=0;j<=2*num;j++)
{
for(k=0;k<dat[j];k++)
{
temp[i++] = 2-j%2;
}
}
// pattern test 1 (確定データと矛盾しないか)
for(i=0;i<max;i++)
{
if(kakutei[i]!=0)
{
if(kakutei[i] != temp[i]) return;
}
}
// pattern test 2 (共通項探索)
for(i=0;i<max;i++)
{
if(test[i]==-1)
{
test[i] = temp[i];
}
else
{
if(test[i] != temp[i])
{
test[i] = 0;
}
}
}
return;
}
else
{
dat[p] = 0;
test_reset(dat,cnt,num);
}
while(!test_chk(dat,cnt,num))
{
dat[p]++;
test_sub(dat, cnt+1, num, max, kakutei, test, temp);
}
}
void test(PICLOS *p)
{
int i,j,num,cnt,max;
int *dat,*kakutei,*test,*temp;
// X
max = p->yline;
cnt = 0;
kakutei = (int*)calloc(max,sizeof(int));
test = (int*)calloc(max,sizeof(int));
temp = (int*)calloc(max,sizeof(int));
for(i=0;i<p->xline;i++)
{
// set dat
num = 0;
for(j=0;j<p->hnum;j++)
{
if(p->xlist[i*p->hnum+j]!=0) num++;
}
dat = (int*)calloc(2*num+1,sizeof(int));
for(j=0;j<num;j++)
{
dat[2*j+1] = p->xlist[(i+1)*p->hnum-num+j];
}
// set kakutei
// set test
for(j=0;j<max;j++)
{
kakutei[j] = p->data[j*max+i];
test[j] = -1;
}
test_sub(dat,cnt,num,max,kakutei,test,temp);
free(dat);
// return kakutei from test
for(j=0;j<max;j++)
{
if(test[j]>0)
{
kakutei[j] = test[j];
}
p->data[j*max+i] = kakutei[j];
}
}
free(kakutei);
free(test);
free(temp);
// Y
max = p->xline;
cnt = 0;
kakutei = (int*)calloc(max,sizeof(int));
test = (int*)calloc(max,sizeof(int));
temp = (int*)calloc(max,sizeof(int));
for(i=0;i<p->yline;i++)
{
// set dat
num = 0;
for(j=0;j<p->hnum;j++)
{
if(p->ylist[i*p->hnum+j]!=0) num++;
}
dat = (int*)calloc(2*num+1,sizeof(int));
for(j=0;j<num;j++)
{
dat[2*j+1] = p->ylist[(i+1)*p->hnum-num+j];
}
// set kakutei
// set test
for(j=0;j<max;j++)
{
kakutei[j] = p->data[i*max+j];
test[j] = -1;
}
test_sub(dat,cnt,num,max,kakutei,test,temp);
free(dat);
// return kakutei from test
for(j=0;j<max;j++)
{
if(test[j]>0)
{
kakutei[j] = test[j];
}
p->data[i*max+j] = kakutei[j];
}
}
free(kakutei);
free(test);
free(temp);
}
int ksum(PICLOS *p)
{
int i,j,sum;
sum = p->xline * p->yline;
for(j=0;j<p->yline;j++)
{
for(i=0;i<p->xline;i++)
{
if(p->data[p->xline*j+i] == 0) sum--;
}
}
return sum;
}
int main(void)
{
PICLOS p;
init(&p);
while(kakutei_sum!=p.xline * p.yline)
{
pprint(&p);
test(&p);
kakutei_sum = ksum(&p);
}
pprint(&p);
final(&p);
return(0);
}