穷举也是一种策略.
不过这里发现还可以优化.
考虑到不同的状态,它们所有棋子所在格子和邻居覆盖的集合可能相同.采用这个集合作为hash表的关键字更加好,应该可以大量降低表格的大小,从而大量节省内存空间
有结果了么
8*8先手败
可以 以n为奇数(n*n的棋盘)来验证程序的正确性。
只有对于所有的n(n为奇数)结果都是先手胜，程序才有可能是正确的。
// chp.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#define N 8
#define BITS (N*N)
typedef unsigned long long SET;
SET nghb;
#define EMPTY_SET 0LL
#define INDEX(x,y) ((x)*N+(y))
#define GET_X(ind) ((ind)/N)
#define GET_Y(ind) ((ind)%N)
#define ADD_INDEX(s, ind)((s)|=1LL<<(ind))
#define TEST_INDEX(s, ind)(((s)&(1LL<<(ind)))!=0)
#define CORNMASK (3|(3<<N))
#define TEST_BIT(x, b) (((x)&(1LL<<(b)))!=0)
#define SET_BIT(x, b) ((x)|=(1LL<<(b)))
#define GET_CORN(x)(((x)&3)| (((x)>>N)&3)<<2)
#define DISP_CORN(x) (((x)&3)| ((((x)>>2)&3)<<N))
#define ECVALUE(x) (((x)&~CORNMASK)|DISP_CORN(cr))
#define STABLE 50000033
#define WALK 1000
int hc;
int ec;
int nec;
int lec;
long long htable;
long long htable2;
char cr={1,-1,-1,-1,-1,-1,-1,-1,4,-1,5,-1,3,-1,11,7};
char rc={-1,0,-1,12,8,10,-1,15,-1,-1,-1,14,-1,-1,-1,-1};
FILE *fout;
void dump(long long v)
{
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(TEST_BIT(v,i*N+j)){
fprintf(fout,"1 ");
}else{
fprintf(fout,"0 ");
}
}
fprintf(fout,"\n");
}
fprintf(fout,"\n");
}
void copy_ec(long long *p)
{
int i,t;
for(i=0,t=0;i<STABLE;i++){
if(htable!=-1LL){
if(cr)]!=-1){
p=htable;
}
}
}
}
void dump_ec(long long htable[])
{
int i;
fout = fopen("dump.txt","w");
for(i=0;i<STABLE;i++){
if(htable!=-1LL){
if(cr)]!=-1){
dump(htable);
}
}
}
fclose(fout);
}
void init()
{
memset(htable,-1,sizeof(htable));
memset(htable2,-1,sizeof(htable2));
}
int hash(SET s)
{
return (int)(s%STABLE);
}
int add_hash(long long htable[],long long key, bool eq)
{
int v=hash(key);
long long ev;
ev=ECVALUE(key);
if(hc>=STABLE){
fprintf(stderr,"out of hash table range\n");
exit(-1);
}
do{
if(htable==-1LL){
if(eq){
htable=ev;nec++;
}else{
htable=key;
ec++;
}
hc++;
return v;
}else if(htable!=key&&htable!=ev){
v=(v+WALK)%STABLE;
}else{
if(eq){
assert(htable==ev);
}else{
assert(htable==key);
}
return v;
}
}while(1);
}
int query_hash_entry(long long htable[],long long key)///return index to hash table
{
long long ev=ECVALUE(key);
int v=hash(key);
do{
if(htable==-1LL)return v;
if(htable==key||htable==ev)
return v;
v=(v+WALK)%STABLE;
}while(1);
}
void init_neighbour()
{
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
SET s=EMPTY_SET;
ADD_INDEX(s,INDEX(i,j));
if(i>0&&j>0){
ADD_INDEX(s,INDEX(i-1,j-1));
}
if(i>0){
ADD_INDEX(s,INDEX(i-1,j));
}
if(j>0){
ADD_INDEX(s,INDEX(i,j-1));
}
if(i>0&&j<N-1){
ADD_INDEX(s,INDEX(i-1,j+1));
}
if(j<N-1){
ADD_INDEX(s,INDEX(i,j+1));
}
if(i<N-1&&j>0){
ADD_INDEX(s,INDEX(i+1,j-1));
}
if(i<N-1){
ADD_INDEX(s,INDEX(i+1,j));
}
if(i<N-1&&j<N-1){
ADD_INDEX(s,INDEX(i+1,j+1));
}
nghb=s;
}
}
}
void visit(long long neighb)
{
int i;
int e=query_hash_entry(htable,neighb);
if(htable==neighb){
int ee=query_hash_entry(htable2,neighb);
if(htable2==-1){
htable2=neighb;
lec++;
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
long long newneighb=neighb;
newneighb|=nghb;
visit(newneighb);
}
}
}
}else{
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
long long newneighb=neighb;
newneighb|=nghb;
int e2=query_hash_entry(htable,newneighb);
if(htable==newneighb){
visit(newneighb);
break;
}
}
}
}
}
int query(long long neighb)
{
int e=query_hash_entry(htable,neighb);
if(htable!=-1)
return e;
int i;
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
long long newneighb=neighb;
newneighb|=nghb;
int r=query(newneighb);
if(htable==newneighb)
break;
}
}
if(i<BITS){///find any status is newneighb
return add_hash(htable,neighb,true);
}else{
return add_hash(htable,neighb,false);
}
}
int cmpll(const void *p,const void *q)
{
const long long *lp=(const long long *)p;
const long long *lq=(const long long *)q;
if(*lp==*lq)return 0;
if(*lp<*lq)return -1;
return 1;
}
int _tmain(int argc, _TCHAR* argv[])
{
int i,j;
init();
init_neighbour();
int s=query(0LL);
if(htable==0LL){
printf("First fail\n");
}else{
printf("First successful\n");
}
printf("Total table size %d\n",hc);
printf("Total eq stat found %d\n",ec);
printf("Total neq stat found %d\n",nec);
visit(0LL);
printf("Total lec stat found %d\n",lec);
// dump_ec(htable2);
#if 0
for(i=0;i<BITS;i++){
long long r=nghb;
printf("%d set={ ",i);
for(j=0;j<BITS;j++){
if(!TEST_BIT(r,j)){
long long newneighb=r;
newneighb|=nghb;
int u=query_hash_entry(htable,newneighb);
if(htable==newneighb){
printf("%d ",j);
}
}
}
printf("}\n");
}
#endif
return 0;
}
15# mathe
用什么编译器编译
C:\vc6>cl ch.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8168 for 80x86
Copyright (C) Microsoft Corp 1984-1998. All rights reserved.
ch.cpp
ch.cpp(4) : fatal error C1083: Cannot open include file: 'stdafx.h': No such file or directory
C:\vc6>cl ch.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8168 for 80x86
Copyright (C) Microsoft Corp 1984-1998. All rights reserved.
ch.cpp
ch.cpp(10) : error C2632: 'long' followed by 'long' is illegal
ch.cpp(32) : error C2632: 'long' followed by 'long' is illegal
ch.cpp(33) : error C2632: 'long' followed by 'long' is illegal
VC7,8,9,gcc
要多大内存啊？我1G内存的电脑都跑不动。
那么把main函数中对visit的调用删除(那部分没有用,是我自己调试用的)然后将全局变量htable2也删除,visit函数删除
如果在vc6下,将所有long long 改为__int64.