关于问题i),现在通过计算机已经能够解决了，只是耗用资源比较大，建议在有2G以上物理内存的计算机上运行:// cs.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <ctype.h>
#include <algorithm>
using namespace std;
#define NS 47065889
char st;
char init;
int tc=0;
long long sl;
char bs;
long long cc1;
long long cc2;
long long *cp1,*cp2;
#define HASKNIGHT 2
#define ATTACKED 1
#define NOTATTACKED 0
//#define DUMP_DATA
#define ENUM_ALL
#ifdef ENUM_ALL
void show(int index, bool bothline=false)
{
int i;
for(i=0;i<9;i++){
switch((sl>>(2*i+18))&3){
case HASKNIGHT:
printf("N");
break;
case ATTACKED:
case NOTATTACKED:
printf("*");
break;
}
}
printf("\n");
if(bothline){
for(i=0;i<9;i++){
switch((sl>>(2*i))&3){
case HASKNIGHT:
printf("N");
break;
case ATTACKED:
case NOTATTACKED:
printf("*");
break;
}
}
printf("\n");
}
}
void dump(int line, int index)
{
int c;
char st;
show(index);
c=bs;
int i,j,k,bc;
for(i=0;i<NS;i++){
if(bs==0)continue;
for(j=0;j<18;j++){
st=(sl>>(2*j))&3;
}
for(j=0;j<512;j++){
bc=0;
for(k=0;k<9;k++)if((j&(1<<k))!=0)bc++;
int nc=bs+bc;
if(nc!=c)
continue;
for(k=0;k<9;k++){
if(st==NOTATTACKED){
int p=0;
if(k>=1&&st!=HASKNIGHT&&(j&(1<<(k-1)))!=0)p=1;
if(k<8&&st!=HASKNIGHT&&(j&(1<<(k+1)))!=0)p=1;
if(p==0)break;
}
}
if(k<9)continue;
long long x=0LL;
for(k=0;k<9;k++){
int ns=st;
if(ns==NOTATTACKED){
int p=0;
if(k>=2&&(j&(1<<(k-1)))==0&&(j&(1<<(k-2)))!=0)p=1;
if(k<7&&(j&(1<<(k+1)))==0&&(j&(1<<(k+2)))!=0)p=1;
if(p)ns=ATTACKED;
}
x|=((long long)ns)<<(2*k);
}
for(k=0;k<9;k++){
int ns;
if((j&(1<<k))!=0)ns=HASKNIGHT;
else ns=0;
if(ns==0){
int p=0;
if(k>=1&&st!=HASKNIGHT&&st==HASKNIGHT)p=1;
if(k<8&&st!=HASKNIGHT&&st==HASKNIGHT)p=1;
if(k>=2&&(st!=HASKNIGHT)&&st==HASKNIGHT)p=1;
if(k<7&&(st!=HASKNIGHT)&&st==HASKNIGHT)p=1;
if(p==1)ns=1;
}
x|=((long long)ns)<<(2*k+18);
}
if(x!=sl)
continue;
if(line>1)
dump(line-1,i);
else{
show(i,true);
}
return;
}
}
}
void update_cp(int line)
{
int i,j,k,bc;
for(i=0;i<NS;i++){
if(bs==0)continue;
for(j=0;j<18;j++){
st=(sl>>(2*j))&3;
}
for(j=0;j<512;j++){
bc=0;
for(k=0;k<9;k++)if((j&(1<<k))!=0)bc++;
for(k=0;k<9;k++){
if(st==NOTATTACKED){
int p=0;
if(k>=1&&st!=HASKNIGHT&&(j&(1<<(k-1)))!=0)p=1;
if(k<8&&st!=HASKNIGHT&&(j&(1<<(k+1)))!=0)p=1;
if(p==0)break;
}
}
if(k<9)continue;
long long x=0LL;
for(k=0;k<9;k++){
int ns=st;
if(ns==NOTATTACKED){
int p=0;
if(k>=2&&(j&(1<<(k-1)))==0&&(j&(1<<(k-2)))!=0)p=1;
if(k<7&&(j&(1<<(k+1)))==0&&(j&(1<<(k+2)))!=0)p=1;
if(p)ns=ATTACKED;
}
x|=((long long)ns)<<(2*k);
}
for(k=0;k<9;k++){
int ns;
if((j&(1<<k))!=0)ns=HASKNIGHT;
else ns=0;
if(ns==0){
int p=0;
if(k>=1&&st!=HASKNIGHT&&st==HASKNIGHT)p=1;
if(k<8&&st!=HASKNIGHT&&st==HASKNIGHT)p=1;
if(k>=2&&(st!=HASKNIGHT)&&st==HASKNIGHT)p=1;
if(k<7&&(st!=HASKNIGHT)&&st==HASKNIGHT)p=1;
if(p==1)ns=1;
}
x|=((long long)ns)<<(2*k+18);
}
int nc=bs+bc;
if(nc>127)nc=127;
long long *p=lower_bound(sl,sl+NS,x);
if(p==NULL||p>=sl+NS)continue;
int index = p-sl;
if(bs==nc){
cp2+=cp1;
}
}
}
}
void nextline(int line)
{
int i,j,k,bc;
for(i=0;i<NS;i++){
if(bs==0)continue;
for(j=0;j<18;j++){
st=(sl>>(2*j))&3;
}
for(j=0;j<512;j++){
bc=0;
for(k=0;k<9;k++)if((j&(1<<k))!=0)bc++;
for(k=0;k<9;k++){
if(st==NOTATTACKED){
int p=0;
if(k>=1&&st!=HASKNIGHT&&(j&(1<<(k-1)))!=0)p=1;
if(k<8&&st!=HASKNIGHT&&(j&(1<<(k+1)))!=0)p=1;
if(p==0)break;
}
}
if(k<9)continue;
long long x=0LL;
for(k=0;k<9;k++){
int ns=st;
if(ns==NOTATTACKED){
int p=0;
if(k>=2&&(j&(1<<(k-1)))==0&&(j&(1<<(k-2)))!=0)p=1;
if(k<7&&(j&(1<<(k+1)))==0&&(j&(1<<(k+2)))!=0)p=1;
if(p)ns=ATTACKED;
}
x|=((long long)ns)<<(2*k);
}
for(k=0;k<9;k++){
int ns;
if((j&(1<<k))!=0)ns=HASKNIGHT;
else ns=0;
if(ns==0){
int p=0;
if(k>=1&&st!=HASKNIGHT&&st==HASKNIGHT)p=1;
if(k<8&&st!=HASKNIGHT&&st==HASKNIGHT)p=1;
if(k>=2&&(st!=HASKNIGHT)&&st==HASKNIGHT)p=1;
if(k<7&&(st!=HASKNIGHT)&&st==HASKNIGHT)p=1;
if(p==1)ns=1;
}
x|=((long long)ns)<<(2*k+18);
}
int nc=bs+bc;
if(nc>127)nc=127;
long long *p=lower_bound(sl,sl+NS,x);
if(p==NULL||p>=sl+NS)continue;
int index = p-sl;
if(bs==0||bs>nc){
bs=nc;
}
}
}
printf("Finished line %d\n",line+1);
}
#define BEST_COUNT 22
void countall()
{
long long *p;
cp1=cc1,cp2=cc2;
int i,j;
for(i=0;i<NS;i++){
for(j=0;j<18;j++){
if(((sl>>(2*j))&3)==0)
break;
}
if(j<18)continue;
if(bs!=BEST_COUNT)continue;
cp1=1LL;
}
for(i=8;i>=1;i--){
update_cp(i);
p=cp2;
cp2=cp1;
cp1=p;
long long tsize=0ll;
for(j=0;j<NS;j++)tsize+=cp2;
printf("Total count %lld in step %d\n",tsize,i);
memset(cp2,0,sizeof(cp2)*NS);
}
}
int findbestlast()
{
int i,j;
int bc=0;
int index;
for(i=0;i<NS;i++){
for(j=0;j<18;j++){
if(((sl>>(2*j))&3)==0)
break;
}
if(j<18)continue;
if(bs==0)continue;
if(bc==0||bs<bc){
bc=bs;
index=i;
}
}
printf("best value %d\n",bc);
dump(8,index);
return bc;
}
void init2()
{
int i,j;
for(i=0;i<tc;i++){
int c2=0;
for(j=0;j<18;j++){
st=(sl>>(2*j))&3;
if(st==2)c2++;
}
for(j=0;j<9;j++){
if(st==ATTACKED){
int p=0;
if(j>=2&&st==HASKNIGHT&&st!=HASKNIGHT)
p=1;
if(j<7&&st==HASKNIGHT&&st!=HASKNIGHT)
p=1;
if(p==0)break;
}
}
if(j<9){
continue;
}
for(j=0;j<9;j++){
if(st==ATTACKED){
int p=0;
if(j>=2&&st==HASKNIGHT&&st!=HASKNIGHT)
p=1;
if(j<7&&st==HASKNIGHT&&st!=HASKNIGHT)
p=1;
if(p==0)break;
}
}
if(j==9){
bs=c2;
}
}
}
#endif
void putst()
{
#ifdef ENUM_ALL
long long x=0;
int i;
for(i=0;i<18;i++){
x|=((long long)st)<<(2*i);
}
sl=x;
#else
tc++;
#endif
}
int next9f()
{
int i;
for(i=0;i<9;i++){
if(st==2){
st=0;
}else{
break;
}
}
if(i==9)return 0;
st++;
return 1;
}
int passe()
{
int i;
for(i=0;i<9;i++){
if(st==NOTATTACKED){
int p=1;
if(i>=2&&st==HASKNIGHT&&st!=HASKNIGHT)p=0;
if(i<7&&st==HASKNIGHT&&st!=HASKNIGHT)p=0;
if(p==0)return 0;
}
}
for(i=0;i<9;i++){
if(st==NOTATTACKED){
int p=1;
if(i>=2&&st==HASKNIGHT&&st!=HASKNIGHT)p=0;
if(i<7&&st==HASKNIGHT&&st!=HASKNIGHT)p=0;
if(p==0)return 0;
}
}
return 1;
}
int next18()
{
int i;
for(i=0;i<9;i++){
if(st==2){
if(init==NOTATTACKED){
st=0;
}else{
st=1;
}
continue;
}else if(st==1){
st=2;
return 1;
}else{
st=1;
return 1;
}
}
return 0;
}
int first18()
{
int i;
for(i=0;i<9;i++){
switch(init){
case NOTATTACKED:
st=NOTATTACKED;
break;
case ATTACKED:
st=ATTACKED;
break;
default:
fprintf(stderr,"invalid\n");
exit(-1);
}
}
return 1;
}
void ana18()
{
int i;
for(i=0;i<9;i++)init=0;
for(i=0;i<9;i++){
if(st==HASKNIGHT){
if(i>=2&&st!=HASKNIGHT){
init=ATTACKED;
}
if(i<7&&st!=HASKNIGHT)init=ATTACKED;
}
}
if(!first18())
return;
do{
if(passe()){
putst();
}
}while(next18());
}
void checkboard()
{
char status;
char line;
int i,j;
for(i=0;i<10;i++){
gets(line);
int c=0;
char *p=line;
do{
while(isspace(*p))p++;
if(*p=='\0'){
fprintf(stderr,"invalid input\n");
exit(-1);
}
if(*p=='*')
status=NOTATTACKED;
else
status=HASKNIGHT;
p++;
}while(c<9);
}
long long x;
int c=0;
for(i=0;i<9;i++)if(status==HASKNIGHT)c++;
for(i=0;i<9;i++){///line i and line i+1
x=0ll;
for(j=0;j<9;j++){
if(status==HASKNIGHT){
if(j>=2&&status!=HASKNIGHT&&status==NOTATTACKED){
status=ATTACKED;
}
if(j<7&&status!=HASKNIGHT&&status==NOTATTACKED){
status=ATTACKED;
}
}
if(status==HASKNIGHT){
if(j>=2&&status!=HASKNIGHT&&status==NOTATTACKED){
status=ATTACKED;
}
if(j<7&&status!=HASKNIGHT&&status==NOTATTACKED){
status=ATTACKED;
}
}
if(i>0&&status==HASKNIGHT){
if(j>=1&&status!=HASKNIGHT&&status==NOTATTACKED){
status=ATTACKED;
}
if(j<8&&status!=HASKNIGHT&&status==NOTATTACKED){
status=ATTACKED;
}
}
}
if(i>0){//check line i-1, everything is attacked
for(j=0;j<9;j++){
if(status==NOTATTACKED){
int p=0;
if(j>=1&&status==HASKNIGHT&&status!=HASKNIGHT){
p=1;
}
if(j<8&&status==HASKNIGHT&&status!=HASKNIGHT){
p=1;
}
if(p==0){
fprintf(stderr,"invalid input, location %d,%d not attacked\n",i-1,j);
exit(-1);
}
}
}
}
for(j=0;j<9;j++){
if(status==HASKNIGHT)c++;
x|=((long long)status)<<(2*j);
x|=((long long)status)<<(2*j+18);
}
long long *p=lower_bound(sl,sl+NS,x);
if(p==NULL||p>=sl+NS){
fprintf(stderr,"status %llx in line %d~%d not found\n",x,i,i+1);
exit(-1);
}
int index=p-sl;
if(bs==0||bs>c){
fprintf(stderr,"status %llx(index %d) in line %d~%d only use %d knights while limit is %d\n",x,index,i,i+1,c,bs);
nextline(i);
exit(-1);
}
printf("status %llx(index %d) in line %d~%d use %d knights and limit is %d\n",x,index,i,i+1,c,bs);
}
printf("success\n");
}
int _tmain(int argc, _TCHAR* argv[])
{
int i;
#if 0
do{
ana18();
}while(next9f());
printf("total %d states\n",tc);
if(tc!=NS){
fprintf(stderr,"invalid count\n");
return -1;
}
sort(sl,sl+NS);
FILE *f=fopen("stats.dat","wb");
fwrite(sl,sizeof(sl),NS,f);
fclose(f);
tc=NS;
#else
FILE *f=fopen("stats.dat","rb");
fread(sl,sizeof(sl),NS,f);
fclose(f);
tc=NS;
#endif
#ifdef ENUM_ALL
#ifdef DUMP_DATA
init2();
for(i=0;i<8;i++){
nextline(i+1);
}
FILE *q=fopen("data.dat","wb");
fwrite(bs,sizeof(bs),9*NS,q);
#else
FILE *q=fopen("data.dat","rb");
fread(bs,sizeof(bs),9*NS,q);
#endif
fclose(q);
// checkboard();
findbestlast();
// countall();
#endif
return 0;
}
楼主的帖子好多
页:
1
[2]