控制方格棋盤游戲

吳秦

控制方格棋盤游戲：如圖所示的5×5的方格棋盤，若在一個(gè)方格內(nèi)放入一個(gè)黑子，則與該方格相鄰的上、下、左、右4個(gè)方格中都不可以再放黑子。于是，在棋盤的7個(gè)位置上各方一個(gè)黑子，就可以控制整個(gè)棋盤。請?jiān)O(shè)計(jì)在棋盤上放7個(gè)黑子就可以控制整個(gè)棋盤的所有方案。

	●		●
●		●		●
	●		●

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<math.h>
   
4. #define N 7
   
5. 
   
6. void backtrack(int t);
   
7. int place(int t);
   
8. int sum=0;
   
9. struct st
   
10. {
    
11.     int row;
    
12.     int column;   
    
13. }x[N+1];
    
14. 
    
15. int main()
    
16. {
    
17.     backtrack(1);
    
18.     printf("總共有%d種方案。\n",sum);   
    
19.     system("PAUSE");
    
20.     return 0 ;
    
21. }
    
22. 
    
23. void backtrack(int t)
    
24. {
    
25.      int i,j;
    
26.      if(t>N)
    
27.      {
    
28.          sum++;
    
29.          printf("方案%d:\n",sum);
    
30.          for(i=1;i<=N;i++)
    
31.              printf("(%d %d) ",x[i].row,x[i].column);
    
32.          printf("\n");         
    
33.      }
    
34.      else
    
35.      {
    
36.          for(i=1;i<=5;i++)
    
37.               for(j=1;j<=5;j++)
    
38.               {
    
39.                    x[t].row=i;
    
40.                    x[t].column=j;
    
41.                    if(place(t)) backtrack(t+1);
    
42.               }
    
43.               
    
44.      }
    
45. }
    
46. 
    
47. int place(int t)
    
48. {
    
49.     int i;
    
50.     for(i=1;i<t;i++)
    
51.     {//這里不知道有什么問題？？？
    
52.          if(x[t].row<x[i].row) return 0;
    
53.          if(x[t].row==x[i].row&&x[t].column<x[i].column) return 0;
    
54.          if(x[t].row==x[i].row&&abs(x[t].column-x[i].column)<=1) return 0;
    
55.          if((x[t].row-x[i].row)==1&&abs(x[t].column-x[i].column)<=1) return 0;
    
56.     }
    
57.     return 1;
    
58. }
    

復(fù)制代碼

[ 本帖最后由 吳秦 于 2009-5-10 09:13 編輯 ]

youshuang

7個(gè)就能控制？給個(gè)例子看看。我怎么試不出來阿。

FeCen

樓主算出來怎么會那么多？
我試了一下，當(dāng)限定7個(gè)棋子的時(shí)候，只有兩種方案。
當(dāng)限定8個(gè)棋子的時(shí)候有119種方案。

以下是七個(gè)棋子時(shí)候的運(yùn)行結(jié)果以及程序代碼：
(0, 1)(0, 3)(2, 0)(2, 2)(2, 4)(4, 1)(4, 3)
(0, 2)(1, 0)(1, 4)(2, 2)(3, 0)(3, 4)(4, 2)
count = 2

#include <stdio.h> #include <memory.h> #define POINT_NUM&nbsp;&nbsp;&nbsp;&nbsp;7 void go(unsigned int m, int num, int i, int j, int index[][2], unsigned int *count) { &nbsp;&nbsp;&nbsp;&nbsp;int u, d, l, r; &nbsp;&nbsp;&nbsp;&nbsp;int t; &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;if (num > POINT_NUM - 1) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;u = i - 1; &nbsp;&nbsp;&nbsp;&nbsp;d = i + 1; &nbsp;&nbsp;&nbsp;&nbsp;l = j - 1; &nbsp;&nbsp;&nbsp;&nbsp;r = j + 1; &nbsp;&nbsp;&nbsp;&nbsp;m |= 0x01 << (i * 5 + j); &nbsp;&nbsp;&nbsp;&nbsp;u < 0 ? 0 : (m |= 0x01 << (u * 5 + j)); &nbsp;&nbsp;&nbsp;&nbsp;d >= 5 ? 0 : (m |= 0x01 << (d * 5 + j)); &nbsp;&nbsp;&nbsp;&nbsp;l < 0 ? 0 : (m |= 0x01 << (i * 5 + l)); &nbsp;&nbsp;&nbsp;&nbsp;r >= 5 ? 0 : (m |= 0x01 << (i * 5 + r)); &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;if (!(m ^ 0x01FFFFFF)) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index[num][0] = i; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index[num][1] = j; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*count)++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (num == POINT_NUM - 1) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for (t = 0; t < POINT_NUM; t++) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("(%d, %d)", index[t][0], index[t][1]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("\n"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;index[num][0] = i; &nbsp;&nbsp;&nbsp;&nbsp;index[num][1] = j; &nbsp;&nbsp;&nbsp;&nbsp;while (1) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(j + 1) >= 5 ? (j = 0, i++) : (j++); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (i >= 5) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (m & (1 << (i * 5 + j))) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;go(m, num + 1, i, j, index, count); &nbsp;&nbsp;&nbsp;&nbsp;} } int main(void) { &nbsp;&nbsp;&nbsp;&nbsp;unsigned int matrix; &nbsp;&nbsp;&nbsp;&nbsp;int index[POINT_NUM][2]; &nbsp;&nbsp;&nbsp;&nbsp;unsigned int count; &nbsp;&nbsp;&nbsp;&nbsp;int i, j; &nbsp;&nbsp;&nbsp;&nbsp;matrix = 0; &nbsp;&nbsp;&nbsp;&nbsp;memset(index, 0, sizeof(index)); &nbsp;&nbsp;&nbsp;&nbsp;count = 0; &nbsp;&nbsp;&nbsp;&nbsp;for (i = 0; i < 2; i++) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for (j = 0; j < 5; j++) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;matrix = 0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(index, 0, sizeof(index)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;go(matrix, 0, i, j, index, &count); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;printf("count = %d\n", count); &nbsp;&nbsp;&nbsp;&nbsp;return 0; }

youshuang

厲害。
我居然試不出來，腦袋真是太...爛了。

mcemil

lz的肯定是錯(cuò)的，我的結(jié)果是22種

FeCen

有那么多��？
那能不能把你的棋子擺放的結(jié)果或者程序放上來看看啊，看看是不是我考慮疏忽了有問題。

daybreakcx

都是搜索，回溯，樓主是說限定棋子的個(gè)數(shù)？

mcemil

0 1,0 4,1 1,2 3,3 0,4 2,4 4,
0 1,1 3,1 4,2 0,3 2,4 1,4 4,
0 2,1 0,1 4,2 3,3 1,4 1,4 4,
0 2,0 4,1 0,2 3,3 1,4 1,4 4,
0 1,0 4,2 0,2 2,2 3,4 1,4 4,
0 3,1 0,1 1,2 4,3 2,4 0,4 4,
0 2,1 0,1 4,2 2,3 2,4 0,4 4,
0 1,1 3,1 4,2 0,3 2,4 0,4 4,
0 1,0 3,2 0,2 2,2 4,4 1,4 3,
0 2,1 0,1 4,2 1,3 3,4 0,4 3,
0 0,0 2,1 4,2 1,3 3,4 0,4 3,
0 3,1 0,1 1,2 4,3 2,4 0,4 3,
0 0,0 3,2 1,2 2,2 4,4 0,4 3,
0 0,0 4,1 2,2 4,3 0,3 1,4 3,
0 0,0 3,1 2,2 4,3 0,3 1,4 3,
0 0,0 3,1 3,2 1,3 4,4 0,4 2,
0 1,0 4,1 1,2 3,3 0,3 4,4 2,
0 2,1 0,1 4,2 2,3 0,3 4,4 2,
0 0,0 4,1 2,2 2,3 0,3 4,4 2,
0 0,0 3,1 3,2 1,3 0,3 4,4 2,
0 1,0 4,1 2,2 0,3 3,3 4,4 1,
0 0,0 4,1 2,2 0,3 3,3 4,4 1,

我的結(jié)果你有空檢驗(yàn)一下

daybreakcx

考慮旋轉(zhuǎn)鏡射那些的不

FeCen

原帖由 mcemil 于 2009-5-8 17:54 發(fā)表
0 1,0 4,1 1,2 3,3 0,4 2,4 4,
0 1,1 3,1 4,2 0,3 2,4 1,4 4,
0 2,1 0,1 4,2 3,3 1,4 1,4 4,
0 2,0 4,1 0,2 3,3 1,4 1,4 4,
0 1,0 4,2 0,2 2,2 3,4 1,4 4,
0 3,1 0,1 1,2 4,3 2,4 0,4 4,
0 2,1 0,1 4,2 2 ...

好像你這個(gè)第一組
0 1,0 4,1 1,2 3,3 0,4 2,4 4,
就有問題啊。

放完（0，1）以后，（1，1）位置就不能再放了啊。。。

其他的沒有仔細(xì)檢查，估計(jì)有類似的問題。