控制方格棋盘游戏

吴秦

控制方格棋盘游戏：如图所示的5×5的方格棋盘，若在一个方格内放入一个黑子，则与该方格相邻的上、下、左、右4个方格中都不可以再放黑子。于是，在棋盘的7个位置上各方一个黑子，就可以控制整个棋盘。请设计在棋盘上放7个黑子就可以控制整个棋盘的所有方案。

	●		●
●		●		●
	●		●

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. }
    

复制代码

[ 本帖最后由 吴秦 于 2009-5-10 09:13 编辑 ]

youshuang

7个就能控制？给个例子看看。我怎么试不出来阿。

FeCen

楼主算出来怎么会那么多？
我试了一下，当限定7个棋子的时候，只有两种方案。
当限定8个棋子的时候有119种方案。

以下是七个棋子时候的运行结果以及程序代码：
(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的肯定是错的，我的结果是22种

FeCen

有那么多啊？
那能不能把你的棋子摆放的结果或者程序放上来看看啊，看看是不是我考虑疏忽了有问题。

daybreakcx

都是搜索，回溯，楼主是说限定棋子的个数？

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,

我的结果你有空检验一下

daybreakcx

考虑旋转镜射那些的不

FeCen

原帖由 mcemil 于 2009-5-8 17:54 发表
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 ...

好像你这个第一组
0 1,0 4,1 1,2 3,3 0,4 2,4 4,
就有问题啊。

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

其他的没有仔细检查，估计有类似的问题。