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

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 中国象棋马控制棋盘问题
12
返回列表 发新帖
楼主: mathe

[擂台] 中国象棋马控制棋盘问题

[复制链接]
hujunhua
发表于 2010-8-8 09:11:09 | 显示全部楼层
第ii)问也存在上限问题：最多能放多少只马，使得不至于因阻塞而产生盲点。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2010-8-8 11:37:15 | 显示全部楼层
的确，实际上问题1也有上限问题。 关于问题i),现在通过计算机已经能够解决了，只是耗用资源比较大，建议在有2G以上物理内存的计算机上运行:
  1. // cs.cpp : Defines the entry point for the console application.
  2. //
  4. #include "stdafx.h"
  5. #include <ctype.h>
  6. #include <algorithm>
  7. using namespace std;
  8. #define NS 47065889
  9. char st[18];
  10. char init[9];
  11. int tc=0;
  12. long long sl[NS];
  13. char bs[9][NS];
  14. long long cc1[NS];
  15. long long cc2[NS];
  16. long long *cp1,*cp2;
  17. #define HASKNIGHT 2
  18. #define ATTACKED 1
  19. #define NOTATTACKED 0
  21. //#define DUMP_DATA
  22. #define ENUM_ALL
  23. #ifdef ENUM_ALL
  25. void show(int index, bool bothline=false)
  26. {
  27. int i;
  28. for(i=0;i<9;i++){
  29. switch((sl[index]>>(2*i+18))&3){
  30. case HASKNIGHT:
  31. printf("N");
  32. break;
  33. case ATTACKED:
  34. case NOTATTACKED:
  35. printf("*");
  36. break;
  37. }
  38. }
  39. printf("\n");
  40. if(bothline){
  41. for(i=0;i<9;i++){
  42. switch((sl[index]>>(2*i))&3){
  43. case HASKNIGHT:
  44. printf("N");
  45. break;
  46. case ATTACKED:
  47. case NOTATTACKED:
  48. printf("*");
  49. break;
  50. }
  51. }
  52. printf("\n");
  53. }
  54. }
  56. void dump(int line, int index)
  57. {
  58. int c;
  59. char st[18];
  60. show(index);
  61. c=bs[line][index];
  62. int i,j,k,bc;
  63. for(i=0;i<NS;i++){
  64. if(bs[line-1][i]==0)continue;
  65. for(j=0;j<18;j++){
  66. st[j]=(sl[i]>>(2*j))&3;
  67. }
  68. for(j=0;j<512;j++){
  69. bc=0;
  70. for(k=0;k<9;k++)if((j&(1<<k))!=0)bc++;
  71. int nc=bs[line-1][i]+bc;
  72. if(nc!=c)
  73. continue;
  74. for(k=0;k<9;k++){
  75. if(st[k]==NOTATTACKED){
  76. int p=0;
  77. if(k>=1&&st[k+9-1]!=HASKNIGHT&&(j&(1<<(k-1)))!=0)p=1;
  78. if(k<8&&st[k+9+1]!=HASKNIGHT&&(j&(1<<(k+1)))!=0)p=1;
  79. if(p==0)break;
  80. }
  81. }
  82. if(k<9)continue;
  83. long long x=0LL;
  84. for(k=0;k<9;k++){
  85. int ns=st[k+9];
  86. if(ns==NOTATTACKED){
  87. int p=0;
  88. if(k>=2&&(j&(1<<(k-1)))==0&&(j&(1<<(k-2)))!=0)p=1;
  89. if(k<7&&(j&(1<<(k+1)))==0&&(j&(1<<(k+2)))!=0)p=1;
  90. if(p)ns=ATTACKED;
  91. }
  92. x|=((long long)ns)<<(2*k);
  93. }
  94. for(k=0;k<9;k++){
  95. int ns;
  96. if((j&(1<<k))!=0)ns=HASKNIGHT;
  97. else ns=0;
  98. if(ns==0){
  99. int p=0;
  100. if(k>=1&&st[k+9-1]!=HASKNIGHT&&st[k-1]==HASKNIGHT)p=1;
  101. if(k<8&&st[k+9+1]!=HASKNIGHT&&st[k+1]==HASKNIGHT)p=1;
  102. if(k>=2&&(st[k+9-1]!=HASKNIGHT)&&st[k+9-2]==HASKNIGHT)p=1;
  103. if(k<7&&(st[k+9+1]!=HASKNIGHT)&&st[k+9+2]==HASKNIGHT)p=1;
  104. if(p==1)ns=1;
  105. }
  106. x|=((long long)ns)<<(2*k+18);
  107. }
  108. if(x!=sl[index])
  109. continue;
  110. if(line>1)
  111. dump(line-1,i);
  112. else{
  113. show(i,true);
  114. }
  115. return;
  116. }
  117. }
  118. }
  120. void update_cp(int line)
  121. {
  122. int i,j,k,bc;
  123. for(i=0;i<NS;i++){
  124. if(bs[line-1][i]==0)continue;
  125. for(j=0;j<18;j++){
  126. st[j]=(sl[i]>>(2*j))&3;
  127. }
  128. for(j=0;j<512;j++){
  129. bc=0;
  130. for(k=0;k<9;k++)if((j&(1<<k))!=0)bc++;
  131. for(k=0;k<9;k++){
  132. if(st[k]==NOTATTACKED){
  133. int p=0;
  134. if(k>=1&&st[k+9-1]!=HASKNIGHT&&(j&(1<<(k-1)))!=0)p=1;
  135. if(k<8&&st[k+9+1]!=HASKNIGHT&&(j&(1<<(k+1)))!=0)p=1;
  136. if(p==0)break;
  137. }
  138. }
  139. if(k<9)continue;
  140. long long x=0LL;
  141. for(k=0;k<9;k++){
  142. int ns=st[k+9];
  143. if(ns==NOTATTACKED){
  144. int p=0;
  145. if(k>=2&&(j&(1<<(k-1)))==0&&(j&(1<<(k-2)))!=0)p=1;
  146. if(k<7&&(j&(1<<(k+1)))==0&&(j&(1<<(k+2)))!=0)p=1;
  147. if(p)ns=ATTACKED;
  148. }
  149. x|=((long long)ns)<<(2*k);
  150. }
  151. for(k=0;k<9;k++){
  152. int ns;
  153. if((j&(1<<k))!=0)ns=HASKNIGHT;
  154. else ns=0;
  155. if(ns==0){
  156. int p=0;
  157. if(k>=1&&st[k+9-1]!=HASKNIGHT&&st[k-1]==HASKNIGHT)p=1;
  158. if(k<8&&st[k+9+1]!=HASKNIGHT&&st[k+1]==HASKNIGHT)p=1;
  159. if(k>=2&&(st[k+9-1]!=HASKNIGHT)&&st[k+9-2]==HASKNIGHT)p=1;
  160. if(k<7&&(st[k+9+1]!=HASKNIGHT)&&st[k+9+2]==HASKNIGHT)p=1;
  161. if(p==1)ns=1;
  162. }
  163. x|=((long long)ns)<<(2*k+18);
  164. }
  165. int nc=bs[line-1][i]+bc;
  166. if(nc>127)nc=127;
  167. long long *p=lower_bound(sl,sl+NS,x);
  168. if(p==NULL||p>=sl+NS)continue;
  169. int index = p-sl;
  170. if(bs[line][index]==nc){
  171. cp2[index]+=cp1[index];
  172. }
  173. }
  174. }
  175. }
  177. void nextline(int line)
  178. {
  179. int i,j,k,bc;
  180. for(i=0;i<NS;i++){
  181. if(bs[line-1][i]==0)continue;
  182. for(j=0;j<18;j++){
  183. st[j]=(sl[i]>>(2*j))&3;
  184. }
  185. for(j=0;j<512;j++){
  186. bc=0;
  187. for(k=0;k<9;k++)if((j&(1<<k))!=0)bc++;
  188. for(k=0;k<9;k++){
  189. if(st[k]==NOTATTACKED){
  190. int p=0;
  191. if(k>=1&&st[k+9-1]!=HASKNIGHT&&(j&(1<<(k-1)))!=0)p=1;
  192. if(k<8&&st[k+9+1]!=HASKNIGHT&&(j&(1<<(k+1)))!=0)p=1;
  193. if(p==0)break;
  194. }
  195. }
  196. if(k<9)continue;
  197. long long x=0LL;
  198. for(k=0;k<9;k++){
  199. int ns=st[k+9];
  200. if(ns==NOTATTACKED){
  201. int p=0;
  202. if(k>=2&&(j&(1<<(k-1)))==0&&(j&(1<<(k-2)))!=0)p=1;
  203. if(k<7&&(j&(1<<(k+1)))==0&&(j&(1<<(k+2)))!=0)p=1;
  204. if(p)ns=ATTACKED;
  205. }
  206. x|=((long long)ns)<<(2*k);
  207. }
  208. for(k=0;k<9;k++){
  209. int ns;
  210. if((j&(1<<k))!=0)ns=HASKNIGHT;
  211. else ns=0;
  212. if(ns==0){
  213. int p=0;
  214. if(k>=1&&st[k+9-1]!=HASKNIGHT&&st[k-1]==HASKNIGHT)p=1;
  215. if(k<8&&st[k+9+1]!=HASKNIGHT&&st[k+1]==HASKNIGHT)p=1;
  216. if(k>=2&&(st[k+9-1]!=HASKNIGHT)&&st[k+9-2]==HASKNIGHT)p=1;
  217. if(k<7&&(st[k+9+1]!=HASKNIGHT)&&st[k+9+2]==HASKNIGHT)p=1;
  218. if(p==1)ns=1;
  219. }
  220. x|=((long long)ns)<<(2*k+18);
  221. }
  222. int nc=bs[line-1][i]+bc;
  223. if(nc>127)nc=127;
  224. long long *p=lower_bound(sl,sl+NS,x);
  225. if(p==NULL||p>=sl+NS)continue;
  226. int index = p-sl;
  227. if(bs[line][index]==0||bs[line][index]>nc){
  228. bs[line][index]=nc;
  229. }
  230. }
  231. }
  232. printf("Finished line %d\n",line+1);
  233. }
  235. #define BEST_COUNT 22
  236. void countall()
  237. {
  238. long long *p;
  239. cp1=cc1,cp2=cc2;
  240. int i,j;
  241. for(i=0;i<NS;i++){
  242. for(j=0;j<18;j++){
  243. if(((sl[i]>>(2*j))&3)==0)
  244. break;
  245. }
  246. if(j<18)continue;
  247. if(bs[8][i]!=BEST_COUNT)continue;
  248. cp1[i]=1LL;
  249. }
  250. for(i=8;i>=1;i--){
  251. update_cp(i);
  252. p=cp2;
  253. cp2=cp1;
  254. cp1=p;
  255. long long tsize=0ll;
  256. for(j=0;j<NS;j++)tsize+=cp2[j];
  257. printf("Total count %lld in step %d\n",tsize,i);
  258. memset(cp2,0,sizeof(cp2[0])*NS);
  259. }
  260. }
  262. int findbestlast()
  263. {
  264. int i,j;
  265. int bc=0;
  266. int index;
  267. for(i=0;i<NS;i++){
  268. for(j=0;j<18;j++){
  269. if(((sl[i]>>(2*j))&3)==0)
  270. break;
  271. }
  272. if(j<18)continue;
  273. if(bs[8][i]==0)continue;
  274. if(bc==0||bs[8][i]<bc){
  275. bc=bs[8][i];
  276. index=i;
  277. }
  278. }
  279. printf("best value %d\n",bc);
  280. dump(8,index);
  281. return bc;
  282. }
  284. void init2()
  285. {
  286. int i,j;
  287. for(i=0;i<tc;i++){
  288. int c2=0;
  289. for(j=0;j<18;j++){
  290. st[j]=(sl[i]>>(2*j))&3;
  291. if(st[j]==2)c2++;
  292. }
  293. for(j=0;j<9;j++){
  294. if(st[j]==ATTACKED){
  295. int p=0;
  296. if(j>=2&&st[9+j-2]==HASKNIGHT&&st[9+j-1]!=HASKNIGHT)
  297. p=1;
  298. if(j<7&&st[9+j+2]==HASKNIGHT&&st[9+j+1]!=HASKNIGHT)
  299. p=1;
  300. if(p==0)break;
  301. }
  302. }
  303. if(j<9){
  304. continue;
  305. }
  306. for(j=0;j<9;j++){
  307. if(st[j+9]==ATTACKED){
  308. int p=0;
  309. if(j>=2&&st[j-2]==HASKNIGHT&&st[j-1]!=HASKNIGHT)
  310. p=1;
  311. if(j<7&&st[j+2]==HASKNIGHT&&st[j+1]!=HASKNIGHT)
  312. p=1;
  313. if(p==0)break;
  314. }
  315. }
  316. if(j==9){
  317. bs[0][i]=c2;
  318. }
  319. }
  320. }
  321. #endif
  322. void putst()
  323. {
  324. #ifdef ENUM_ALL
  325. long long x=0;
  326. int i;
  327. for(i=0;i<18;i++){
  328. x|=((long long)st[i])<<(2*i);
  329. }
  330. sl[tc++]=x;
  331. #else
  332. tc++;
  333. #endif
  334. }
  336. int next9f()
  337. {
  338. int i;
  339. for(i=0;i<9;i++){
  340. if(st[i]==2){
  341. st[i]=0;
  342. }else{
  343. break;
  344. }
  345. }
  346. if(i==9)return 0;
  347. st[i]++;
  348. return 1;
  349. }
  351. int passe()
  352. {
  353. int i;
  354. for(i=0;i<9;i++){
  355. if(st[i]==NOTATTACKED){
  356. int p=1;
  357. if(i>=2&&st[9+i-2]==HASKNIGHT&&st[9+i-1]!=HASKNIGHT)p=0;
  358. if(i<7&&st[9+i+2]==HASKNIGHT&&st[9+i+1]!=HASKNIGHT)p=0;
  359. if(p==0)return 0;
  360. }
  361. }
  362. for(i=0;i<9;i++){
  363. if(st[9+i]==NOTATTACKED){
  364. int p=1;
  365. if(i>=2&&st[i-2]==HASKNIGHT&&st[i-1]!=HASKNIGHT)p=0;
  366. if(i<7&&st[i+2]==HASKNIGHT&&st[i+1]!=HASKNIGHT)p=0;
  367. if(p==0)return 0;
  368. }
  369. }
  370. return 1;
  371. }
  373. int next18()
  374. {
  375. int i;
  376. for(i=0;i<9;i++){
  377. if(st[i+9]==2){
  378. if(init[i]==NOTATTACKED){
  379. st[i+9]=0;
  380. }else{
  381. st[i+9]=1;
  382. }
  383. continue;
  384. }else if(st[i+9]==1){
  385. st[i+9]=2;
  386. return 1;
  387. }else{
  388. st[i+9]=1;
  389. return 1;
  390. }
  391. }
  392. return 0;
  393. }
  395. int first18()
  396. {
  397. int i;
  398. for(i=0;i<9;i++){
  399. switch(init[i]){
  400. case NOTATTACKED:
  401. st[i+9]=NOTATTACKED;
  402. break;
  403. case ATTACKED:
  404. st[i+9]=ATTACKED;
  405. break;
  406. default:
  407. fprintf(stderr,"invalid\n");
  408. exit(-1);
  409. }
  410. }
  411. return 1;
  412. }
  415. void ana18()
  416. {
  417. int i;
  418. for(i=0;i<9;i++)init[i]=0;
  419. for(i=0;i<9;i++){
  420. if(st[i]==HASKNIGHT){
  421. if(i>=2&&st[i-1]!=HASKNIGHT){
  422. init[i-2]=ATTACKED;
  423. }
  424. if(i<7&&st[i+1]!=HASKNIGHT)init[i+2]=ATTACKED;
  425. }
  426. }
  427. if(!first18())
  428. return;
  429. do{
  430. if(passe()){
  431. putst();
  432. }
  433. }while(next18());
  434. }
  436. void checkboard()
  437. {
  438. char status[10][9];
  439. char line[80];
  440. int i,j;
  441. for(i=0;i<10;i++){
  442. gets(line);
  443. int c=0;
  444. char *p=line;
  445. do{
  446. while(isspace(*p))p++;
  447. if(*p=='\0'){
  448. fprintf(stderr,"invalid input\n");
  449. exit(-1);
  450. }
  451. if(*p=='*')
  452. status[i][c++]=NOTATTACKED;
  453. else
  454. status[i][c++]=HASKNIGHT;
  455. p++;
  456. }while(c<9);
  457. }
  458. long long x;
  459. int c=0;
  460. for(i=0;i<9;i++)if(status[0][i]==HASKNIGHT)c++;
  461. for(i=0;i<9;i++){///line i and line i+1
  462. x=0ll;
  463. for(j=0;j<9;j++){
  464. if(status[i+1][j]==HASKNIGHT){
  465. if(j>=2&&status[i+1][j-1]!=HASKNIGHT&&status[i][j-2]==NOTATTACKED){
  466. status[i][j-2]=ATTACKED;
  467. }
  468. if(j<7&&status[i+1][j+1]!=HASKNIGHT&&status[i][j+2]==NOTATTACKED){
  469. status[i][j+2]=ATTACKED;
  470. }
  471. }
  472. if(status[i][j]==HASKNIGHT){
  473. if(j>=2&&status[i][j-1]!=HASKNIGHT&&status[i+1][j-2]==NOTATTACKED){
  474. status[i+1][j-2]=ATTACKED;
  475. }
  476. if(j<7&&status[i][j+1]!=HASKNIGHT&&status[i+1][j+2]==NOTATTACKED){
  477. status[i+1][j+2]=ATTACKED;
  478. }
  479. }
  480. if(i>0&&status[i-1][j]==HASKNIGHT){
  481. if(j>=1&&status[i][j]!=HASKNIGHT&&status[i+1][j-1]==NOTATTACKED){
  482. status[i+1][j-1]=ATTACKED;
  483. }
  484. if(j<8&&status[i][j]!=HASKNIGHT&&status[i+1][j+1]==NOTATTACKED){
  485. status[i+1][j+1]=ATTACKED;
  486. }
  487. }
  489. }
  490. if(i>0){//check line i-1, everything is attacked
  491. for(j=0;j<9;j++){
  492. if(status[i-1][j]==NOTATTACKED){
  493. int p=0;
  494. if(j>=1&&status[i+1][j-1]==HASKNIGHT&&status[i][j-1]!=HASKNIGHT){
  495. p=1;
  496. }
  497. if(j<8&&status[i+1][j+1]==HASKNIGHT&&status[i][j+1]!=HASKNIGHT){
  498. p=1;
  499. }
  500. if(p==0){
  501. fprintf(stderr,"invalid input, location %d,%d not attacked\n",i-1,j);
  502. exit(-1);
  503. }
  504. }
  505. }
  506. }
  507. for(j=0;j<9;j++){
  508. if(status[i+1][j]==HASKNIGHT)c++;
  509. x|=((long long)status[i][j])<<(2*j);
  510. x|=((long long)status[i+1][j])<<(2*j+18);
  511. }
  512. long long *p=lower_bound(sl,sl+NS,x);
  513. if(p==NULL||p>=sl+NS){
  514. fprintf(stderr,"status %llx in line %d~%d not found\n",x,i,i+1);
  515. exit(-1);
  516. }
  517. int index=p-sl;
  518. if(bs[i][index]==0||bs[i][index]>c){
  519. 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[i][index]);
  520. nextline(i);
  521. exit(-1);
  522. }
  523. printf("status %llx(index %d) in line %d~%d use %d knights and limit is %d\n",x,index,i,i+1,c,bs[i][index]);
  524. }
  525. printf("success\n");
  526. }
  529. int _tmain(int argc, _TCHAR* argv[])
  530. {
  531. int i;
  532. #if 0
  533. do{
  534. ana18();
  535. }while(next9f());
  536. printf("total %d states\n",tc);
  537. if(tc!=NS){
  538. fprintf(stderr,"invalid count\n");
  539. return -1;
  540. }
  541. sort(sl,sl+NS);
  542. FILE *f=fopen("stats.dat","wb");
  543. fwrite(sl,sizeof(sl[0]),NS,f);
  544. fclose(f);
  545. tc=NS;
  546. #else
  547. FILE *f=fopen("stats.dat","rb");
  548. fread(sl,sizeof(sl[0]),NS,f);
  549. fclose(f);
  550. tc=NS;
  551. #endif
  552. #ifdef ENUM_ALL
  553. #ifdef DUMP_DATA
  554. init2();
  555. for(i=0;i<8;i++){
  556. nextline(i+1);
  557. }
  558. FILE *q=fopen("data.dat","wb");
  559. fwrite(bs,sizeof(bs[0][0]),9*NS,q);
  560. #else
  561. FILE *q=fopen("data.dat","rb");
  562. fread(bs,sizeof(bs[0][0]),9*NS,q);
  563. #endif
  564. fclose(q);
  565. // checkboard();
  566. findbestlast();
  567. // countall();
  568. #endif
  569. return 0;
  570. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

guxd
发表于 2013-7-6 08:53:15 | 显示全部楼层
楼主的帖子好多
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-11-23 17:35 , Processed in 0.020510 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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