数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【数学研究】 › 难题征解 › 一种棋类游戏
1234下一页
返回列表 发新帖
楼主: 056254628

[讨论] 一种棋类游戏

[复制链接]
mathe
发表于 2009-10-16 09:20:53 | 显示全部楼层
修改后的代码如下: 此外如果内存还是太小,宏STABLE还可以改小一半左右.但是需要注意STABLE和WALK必须互素.
  1. // chp.cpp : Defines the entry point for the console application.
  2. //
  4. #include "stdafx.h"
  5. #include <string.h>
  6. #include <assert.h>
  7. #include <stdlib.h>
  8. #define N 8
  9. #define BITS (N*N)
  10. typedef unsigned long long SET;
  11. SET nghb[BITS];
  12. #define EMPTY_SET 0LL
  13. #define INDEX(x,y) ((x)*N+(y))
  14. #define GET_X(ind) ((ind)/N)
  15. #define GET_Y(ind) ((ind)%N)
  16. #define ADD_INDEX(s, ind) ((s)|=1LL<<(ind))
  17. #define TEST_INDEX(s, ind) (((s)&(1LL<<(ind)))!=0)
  18. #define CORNMASK (3|(3<<N))
  19. #define TEST_BIT(x, b) (((x)&(1LL<<(b)))!=0)
  20. #define SET_BIT(x, b) ((x)|=(1LL<<(b)))
  22. #define GET_CORN(x) (((x)&3)| (((x)>>N)&3)<<2)
  23. #define DISP_CORN(x) (((x)&3)| ((((x)>>2)&3)<<N))
  24. #define ECVALUE(x) (((x)&~CORNMASK)|DISP_CORN(cr[GET_CORN(x)]))
  26. #define STABLE 50000033
  27. #define WALK 1000
  28. int hc;
  29. int ec;
  30. int nec;
  31. int lec;
  32. long long htable[STABLE];
  33. //long long htable2[STABLE];
  34. char cr[16]={1,-1,-1,-1,-1,-1,-1,-1,4,-1,5,-1,3,-1,11,7};
  35. char rc[16]={-1,0,-1,12,8,10,-1,15,-1,-1,-1,14,-1,-1,-1,-1};
  37. FILE *fout;
  38. void dump(long long v)
  39. {
  40. int i,j;
  41. for(i=0;i<N;i++){
  42. for(j=0;j<N;j++){
  43. if(TEST_BIT(v,i*N+j)){
  44. fprintf(fout,"1 ");
  45. }else{
  46. fprintf(fout,"0 ");
  47. }
  48. }
  49. fprintf(fout,"\n");
  50. }
  51. fprintf(fout,"\n");
  52. }
  54. void copy_ec(long long *p)
  55. {
  56. int i,t;
  57. for(i=0,t=0;i<STABLE;i++){
  58. if(htable[i]!=-1LL){
  59. if(cr[GET_CORN(htable[i])]!=-1){
  60. p[t++]=htable[i];
  61. }
  62. }
  63. }
  64. }
  66. void dump_ec(long long htable[])
  67. {
  68. int i;
  69. fout = fopen("dump.txt","w");
  70. for(i=0;i<STABLE;i++){
  71. if(htable[i]!=-1LL){
  72. if(cr[GET_CORN(htable[i])]!=-1){
  73. dump(htable[i]);
  74. }
  75. }
  76. }
  77. fclose(fout);
  78. }
  80. void init()
  81. {
  82. memset(htable,-1,sizeof(htable));
  83. // memset(htable2,-1,sizeof(htable2));
  84. }
  86. int hash(SET s)
  87. {
  88. return (int)(s%STABLE);
  89. }
  91. int add_hash(long long htable[],long long key, bool eq)
  92. {
  93. int v=hash(key);
  94. long long ev;
  95. ev=ECVALUE(key);
  96. if(hc>=STABLE){
  97. fprintf(stderr,"out of hash table range\n");
  98. exit(-1);
  99. }
  100. do{
  101. if(htable[v]==-1LL){
  102. if(eq){
  103. htable[v]=ev;nec++;
  104. }else{
  105. htable[v]=key;
  106. ec++;
  107. }
  108. hc++;
  109. return v;
  110. }else if(htable[v]!=key&&htable[v]!=ev){
  111. v=(v+WALK)%STABLE;
  112. }else{
  113. if(eq){
  114. assert(htable[v]==ev);
  115. }else{
  116. assert(htable[v]==key);
  117. }
  118. return v;
  119. }
  120. }while(1);
  121. }
  123. int query_hash_entry(long long htable[],long long key)///return index to hash table
  124. {
  125. long long ev=ECVALUE(key);
  126. int v=hash(key);
  127. do{
  128. if(htable[v]==-1LL)return v;
  129. if(htable[v]==key||htable[v]==ev)
  130. return v;
  131. v=(v+WALK)%STABLE;
  132. }while(1);
  133. }
  135. void init_neighbour()
  136. {
  137. int i,j;
  138. for(i=0;i<N;i++){
  139. for(j=0;j<N;j++){
  140. SET s=EMPTY_SET;
  141. ADD_INDEX(s,INDEX(i,j));
  142. if(i>0&&j>0){
  143. ADD_INDEX(s,INDEX(i-1,j-1));
  144. }
  145. if(i>0){
  146. ADD_INDEX(s,INDEX(i-1,j));
  147. }
  148. if(j>0){
  149. ADD_INDEX(s,INDEX(i,j-1));
  150. }
  151. if(i>0&&j<N-1){
  152. ADD_INDEX(s,INDEX(i-1,j+1));
  153. }
  154. if(j<N-1){
  155. ADD_INDEX(s,INDEX(i,j+1));
  156. }
  157. if(i<N-1&&j>0){
  158. ADD_INDEX(s,INDEX(i+1,j-1));
  159. }
  160. if(i<N-1){
  161. ADD_INDEX(s,INDEX(i+1,j));
  162. }
  163. if(i<N-1&&j<N-1){
  164. ADD_INDEX(s,INDEX(i+1,j+1));
  165. }
  166. nghb[INDEX(i,j)]=s;
  167. }
  168. }
  169. }
  170. #if 0
  171. void visit(long long neighb)
  172. {
  173. int i;
  174. int e=query_hash_entry(htable,neighb);
  175. if(htable[e]==neighb){
  176. int ee=query_hash_entry(htable2,neighb);
  177. if(htable2[ee]==-1){
  178. htable2[ee]=neighb;
  179. lec++;
  180. for(i=0;i<BITS;i++){
  181. if(TEST_BIT(neighb,i)==0){
  182. long long newneighb=neighb;
  183. newneighb|=nghb[i];
  184. visit(newneighb);
  185. }
  186. }
  187. }
  188. }else{
  189. for(i=0;i<BITS;i++){
  190. if(TEST_BIT(neighb,i)==0){
  191. long long newneighb=neighb;
  192. newneighb|=nghb[i];
  193. int e2=query_hash_entry(htable,newneighb);
  194. if(htable[e2]==newneighb){
  195. visit(newneighb);
  196. break;
  197. }
  198. }
  199. }
  200. }
  201. }
  202. #endif
  203. int query(long long neighb)
  204. {
  205. int e=query_hash_entry(htable,neighb);
  206. if(htable[e]!=-1)
  207. return e;
  208. int i;
  209. for(i=0;i<BITS;i++){
  210. if(TEST_BIT(neighb,i)==0){
  211. long long newneighb=neighb;
  212. newneighb|=nghb[i];
  213. int r=query(newneighb);
  214. if(htable[r]==newneighb)
  215. break;
  216. }
  217. }
  218. if(i<BITS){///find any status is newneighb
  219. return add_hash(htable,neighb,true);
  220. }else{
  221. return add_hash(htable,neighb,false);
  222. }
  223. }
  225. int cmpll(const void *p,const void *q)
  226. {
  227. const long long *lp=(const long long *)p;
  228. const long long *lq=(const long long *)q;
  229. if(*lp==*lq)return 0;
  230. if(*lp<*lq)return -1;
  231. return 1;
  232. }
  234. int _tmain(int argc, _TCHAR* argv[])
  235. {
  236. int i,j;
  237. init();
  238. init_neighbour();
  239. int s=query(0LL);
  240. if(htable[s]==0LL){
  241. printf("First fail\n");
  242. }else{
  243. printf("First successful\n");
  244. }
  245. printf("Total table size %d\n",hc);
  246. printf("Total eq stat found %d\n",ec);
  247. printf("Total neq stat found %d\n",nec);
  248. #if 0
  249. for(i=0;i<BITS;i++){
  250. long long r=nghb[i];
  251. printf("%d set={ ",i);
  252. for(j=0;j<BITS;j++){
  253. if(!TEST_BIT(r,j)){
  254. long long newneighb=r;
  255. newneighb|=nghb[j];
  256. int u=query_hash_entry(htable,newneighb);
  257. if(htable[u]==newneighb){
  258. printf("%d ",j);
  259. }
  260. }
  261. }
  262. printf("}\n");
  263. }
  264. #endif
  265. return 0;
  266. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-10-16 09:23:20 | 显示全部楼层
发现宏STABLE已经不能再小了(除非修改代码再考虑对称性),实际上最后使用的数目为31816105.
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

〇〇
发表于 2009-10-16 14:33:33 | 显示全部楼层
如果在vc6下,将所有long long 改为__int64. mathe 发表于 2009-10-16 09:17
我照做了,但是LL还报错，于是1LL->(__int64)1,0LL->(__int64)0 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 Microsoft (R) Incremental Linker Version 6.00.8168 Copyright (C) Microsoft Corp 1992-1998. All rights reserved. /out:ch.exe ch.obj ch.exe : warning LNK4084: total image size 800043008 exceeds max (268435456); image may not run

ch.cpp

7.25 KB, 下载次数: 3, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-10-16 15:03:57 | 显示全部楼层
你可以试着将htable的内存初始化改成动态分配(用malloc)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

〇〇
发表于 2009-10-16 20:18:53 | 显示全部楼层
堆栈溢出？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

〇〇
发表于 2009-10-16 20:29:29 | 显示全部楼层
不是说运行很长时间？ 我把21楼改成下面，马上运行结束。 First fail Total table size 0 Total eq stat found 0 Total neq stat found 0
  2. // chp.cpp : Defines the entry point for the console application.
  3. //
  5. //#include "stdafx.h"
  6. #include <stdio.h>
  7. #include <string.h>
  8. #include <assert.h>
  9. #include <stdlib.h>
  10. #define N 8
  11. #define BITS (N*N)
  12. typedef unsigned __int64 SET;
  13. SET nghb[BITS];
  14. #define EMPTY_SET (__int64)0
  15. #define INDEX(x,y) ((x)*N+(y))
  16. #define GET_X(ind) ((ind)/N)
  17. #define GET_Y(ind) ((ind)%N)
  18. #define ADD_INDEX(s, ind) ((s)|=(__int64)1<<(ind))
  19. #define TEST_INDEX(s, ind) (((s)&((__int64)1<<(ind)))!=0)
  20. #define CORNMASK (3|(3<<N))
  21. #define TEST_BIT(x, b) (((x)&((__int64)1<<(b)))!=0)
  22. #define SET_BIT(x, b) ((x)|=((__int64)1<<(b)))
  24. #define GET_CORN(x) (((x)&3)| (((x)>>N)&3)<<2)
  25. #define DISP_CORN(x) (((x)&3)| ((((x)>>2)&3)<<N))
  26. #define ECVALUE(x) (((x)&~CORNMASK)|DISP_CORN(cr[GET_CORN(x)]))
  28. #define STABLE 50000033
  29. #define WALK 1000
  30. int hc;
  31. int ec;
  32. int nec;
  33. int lec;
  34. __int64 *htable=(__int64 *)malloc(sizeof(__int64)*STABLE);
  35. //__int64 htable2[STABLE];
  36. char cr[16]={1,-1,-1,-1,-1,-1,-1,-1,4,-1,5,-1,3,-1,11,7};
  37. char rc[16]={-1,0,-1,12,8,10,-1,15,-1,-1,-1,14,-1,-1,-1,-1};
  39. FILE *fout;
  40. void dump(__int64 v)
  41. {
  42. int i,j;
  43. for(i=0;i<N;i++){
  44. for(j=0;j<N;j++){
  45. if(TEST_BIT(v,i*N+j)){
  46. fprintf(fout,"1 ");
  47. }else{
  48. fprintf(fout,"0 ");
  49. }
  50. }
  51. fprintf(fout,"\n");
  52. }
  53. fprintf(fout,"\n");
  54. }
  56. void copy_ec(__int64 *p)
  57. {
  58. int i,t;
  59. for(i=0,t=0;i<STABLE;i++){
  60. if(htable[i]!=-(__int64)1){
  61. if(cr[GET_CORN(htable[i])]!=-1){
  62. p[t++]=htable[i];
  63. }
  64. }
  65. }
  66. }
  68. void dump_ec(__int64 htable[])
  69. {
  70. int i;
  71. fout = fopen("dump.txt","w");
  72. for(i=0;i<STABLE;i++){
  73. if(htable[i]!=-(__int64)1){
  74. if(cr[GET_CORN(htable[i])]!=-1){
  75. dump(htable[i]);
  76. }
  77. }
  78. }
  79. fclose(fout);
  80. }
  82. void init()
  83. {
  84. memset(htable,-1,sizeof(htable));
  85. // memset(htable2,-1,sizeof(htable2));
  86. }
  88. int hash(SET s)
  89. {
  90. return (int)(s%STABLE);
  91. }
  93. int add_hash(__int64 htable[],__int64 key, bool eq)
  94. {
  95. int v=hash(key);
  96. __int64 ev;
  97. ev=ECVALUE(key);
  98. if(hc>=STABLE){
  99. fprintf(stderr,"out of hash table range\n");
  100. exit(-1);
  101. }
  102. do{
  103. if(htable[v]==-(__int64)1){
  104. if(eq){
  105. htable[v]=ev;nec++;
  106. }else{
  107. htable[v]=key;
  108. ec++;
  109. }
  110. hc++;
  111. return v;
  112. }else if(htable[v]!=key&&htable[v]!=ev){
  113. v=(v+WALK)%STABLE;
  114. }else{
  115. if(eq){
  116. assert(htable[v]==ev);
  117. }else{
  118. assert(htable[v]==key);
  119. }
  120. return v;
  121. }
  122. }while(1);
  123. }
  125. int query_hash_entry(__int64 htable[],__int64 key)///return index to hash table
  126. {
  127. __int64 ev=ECVALUE(key);
  128. int v=hash(key);
  129. do{
  130. if(htable[v]==-(__int64)1)return v;
  131. if(htable[v]==key||htable[v]==ev)
  132. return v;
  133. v=(v+WALK)%STABLE;
  134. }while(1);
  135. }
  137. void init_neighbour()
  138. {
  139. int i,j;
  140. for(i=0;i<N;i++){
  141. for(j=0;j<N;j++){
  142. SET s=EMPTY_SET;
  143. ADD_INDEX(s,INDEX(i,j));
  144. if(i>0&&j>0){
  145. ADD_INDEX(s,INDEX(i-1,j-1));
  146. }
  147. if(i>0){
  148. ADD_INDEX(s,INDEX(i-1,j));
  149. }
  150. if(j>0){
  151. ADD_INDEX(s,INDEX(i,j-1));
  152. }
  153. if(i>0&&j<N-1){
  154. ADD_INDEX(s,INDEX(i-1,j+1));
  155. }
  156. if(j<N-1){
  157. ADD_INDEX(s,INDEX(i,j+1));
  158. }
  159. if(i<N-1&&j>0){
  160. ADD_INDEX(s,INDEX(i+1,j-1));
  161. }
  162. if(i<N-1){
  163. ADD_INDEX(s,INDEX(i+1,j));
  164. }
  165. if(i<N-1&&j<N-1){
  166. ADD_INDEX(s,INDEX(i+1,j+1));
  167. }
  168. nghb[INDEX(i,j)]=s;
  169. }
  170. }
  171. }
  172. #if 0
  173. void visit(__int64 neighb)
  174. {
  175. int i;
  176. int e=query_hash_entry(htable,neighb);
  177. if(htable[e]==neighb){
  178. int ee=query_hash_entry(htable2,neighb);
  179. if(htable2[ee]==-1){
  180. htable2[ee]=neighb;
  181. lec++;
  182. for(i=0;i<BITS;i++){
  183. if(TEST_BIT(neighb,i)==0){
  184. __int64 newneighb=neighb;
  185. newneighb|=nghb[i];
  186. visit(newneighb);
  187. }
  188. }
  189. }
  190. }else{
  191. for(i=0;i<BITS;i++){
  192. if(TEST_BIT(neighb,i)==0){
  193. __int64 newneighb=neighb;
  194. newneighb|=nghb[i];
  195. int e2=query_hash_entry(htable,newneighb);
  196. if(htable[e2]==newneighb){
  197. visit(newneighb);
  198. break;
  199. }
  200. }
  201. }
  202. }
  203. }
  204. #endif
  205. int query(__int64 neighb)
  206. {
  207. int e=query_hash_entry(htable,neighb);
  208. if(htable[e]!=-1)
  209. return e;
  210. int i;
  211. for(i=0;i<BITS;i++){
  212. if(TEST_BIT(neighb,i)==0){
  213. __int64 newneighb=neighb;
  214. newneighb|=nghb[i];
  215. int r=query(newneighb);
  216. if(htable[r]==newneighb)
  217. break;
  218. }
  219. }
  220. if(i<BITS){///find any status is newneighb
  221. return add_hash(htable,neighb,true);
  222. }else{
  223. return add_hash(htable,neighb,false);
  224. }
  225. }
  227. int cmpll(const void *p,const void *q)
  228. {
  229. const __int64 *lp=(const __int64 *)p;
  230. const __int64 *lq=(const __int64 *)q;
  231. if(*lp==*lq)return 0;
  232. if(*lp<*lq)return -1;
  233. return 1;
  234. }
  236. int main(int argc, char* argv[])
  237. {
  238. int i,j;
  239. init();
  240. init_neighbour();
  241. int s=query((__int64)0);
  242. if(htable[s]==(__int64)0){
  243. printf("First fail\n");
  244. }else{
  245. printf("First successful\n");
  246. }
  247. printf("Total table size %d\n",hc);
  248. printf("Total eq stat found %d\n",ec);
  249. printf("Total neq stat found %d\n",nec);
  250. #if 0
  251. for(i=0;i<BITS;i++){
  252. __int64 r=nghb[i];
  253. printf("%d set={ ",i);
  254. for(j=0;j<BITS;j++){
  255. if(!TEST_BIT(r,j)){
  256. __int64 newneighb=r;
  257. newneighb|=nghb[j];
  258. int u=query_hash_entry(htable,newneighb);
  259. if(htable[u]==newneighb){
  260. printf("%d ",j);
  261. }
  262. }
  263. }
  264. printf("}\n");
  265. }
  266. #endif
  267. return 0;
  268. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-10-16 21:25:29 | 显示全部楼层
  2. void init()
  4. {
  6. memset(htable,-1,sizeof(htable));
  8. // memset(htable2,-1,sizeof(htable2));
  10. }
复制代码
需要修改
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

〇〇
发表于 2009-10-21 09:08:06 | 显示全部楼层
下载了一个Microsoft Visual C++ Toolkit 2003，可以编译long long了，运行时间确实很长
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

〇〇
发表于 2009-10-21 09:21:02 | 显示全部楼层
First fail Total table size 31816105 Total eq stat found 5732950 Total neq stat found 26083155 Total lec stat found 1869201
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

〇〇
发表于 2009-10-21 14:32:19 | 显示全部楼层
21楼 Timer 3.01 Copyright (c) 2002-2003 Igor Pavlov 2003-07-10 First fail Total table size 31816105 Total eq stat found 5732950 Total neq stat found 26083155 Kernel Time = 0.639 = 00:00:00.639 = 1% User Time = 45.240 = 00:00:45.240 = 98% Process Time = 45.879 = 00:00:45.879 = 99% Global Time = 45.911 = 00:00:45.911 = 100%
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1234下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-22 11:06 , Processed in 0.032464 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表