中国象棋将帅问题

http://book.51cto.com/art/200909/150032.htm

1.2 中国象棋将帅问题

下过中国象棋的朋友都知道，双方的"将"和"帅"相隔遥远，并且它们不能照面。在象棋残局中，许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有"将"和"帅"二子（如图1-3所示）（为了下面叙述方便，我们约定用A表示"将"，B表示"帅"）：

A、B二子被限制在己方3×3的格子里运动。例如,在如上的表格里，A被正方形{d10, f10, d8, f8}包围，而B被正方形{d3, f3, d1, f1}包围。每一步，A、B分别可以横向或纵向移动一格，但不能沿对角线移动。另外，A不能面对B，也就是说，A和B不能处于同一纵向直线上（比如A在d10的位置，那么B就不能在d1、d2以及d3）。

请写出一个程序，输出A、B所有合法位置。要求在代码中只能使用一个变量。

分析与解法

问题的本身并不复杂，只要把所有A、B互相排斥的条件列举出来就可以完成本题的要求。由于本题要求只能使用一个变量，所以必须首先想清楚在写代码的时候，有哪些信息需要存储，并且尽量高效率地存储信息。稍微思考一下，可以知道这个程序的大体框架是：

因此，需要存储的是A、B的位置信息，并且每次循环都要更新。为了能够进行判断，首先需要创建一个逻辑的坐标系统，以便检测A何时会面对B。这里我们想到的方法是用1~9的数字，按照行优先的顺序来表示每个格点的位置（如图1-4所示）。这样，只需要用模余运算就可以得到当前的列号，从而判断A、B是否互斥。

第二，题目要求只用一个变量，但是我们却要存储A和B两个子的位置信息，该怎么办呢？

可以先把已知变量类型列举一下，然后做些分析。

对于bool类型，估计没有办法做任何扩展了，因为它只能表示true和false两个值；而byte或者int类型，它们能够表达的信息则更多。事实上，对本题来说，每个子都只需要9个数字就可以表达它的全部位置。

一个8位的byte类型能够表达28=256个值，所以用它来表示A、B的位置信息绰绰有余，因此可以把这个字节的变量（设为b）分成两部分。用前面的4 bit表示A的位置，用后面的4 bit表示B的位置，那么4个bit可以表示16个数，这已经足够了。

问题在于：如何使用bit级的运算将数据从这一byte变量的左边和右边分别存入和读出。

下面是做法：

http://15838341661-139-com.iteye.com/blog/1601987

创建一个逻辑坐标系统，用 1-9 的数字，按照行优先的顺序来表示每个格点的位置。

要证明 A 和 B 不在同一列上，只要 A 和 B 所处的格子点数 mod3 不相等就可以。

分析解法一：

该书中提到的解法一的思想是通过位运算来解决上面的问题。一个 8 位的 byte 类型能够表达 2 的 8 次方=256 个值，所以用它来表示 A 、 B 的位置信息绰绰有余，因此可以把这个字节分成两部分，用前面的 4bit 表示A 的位置，用后面的 4bit 表示 B 的位置，而 4 个 bit 可以表示 16 个数，这已经够了。

    JAVA 中用 byte 来表示位置，可以实现，但只用一个变量，就没了思路（请高手指点） …

分析解法二 ( 这里用 Java 代码实现 ) ：

   

Java代码  

1. int i = 81;  
2.   
3. while(i--!=0){  
4.   
5.      if(i/9%3 == i%9%3)  
6.         continue;  
7.   
8.      System.out.println("A="+(i/9+1)+" B="+(i%9+1));  
9.   
10. }  

从上面可以看出来， i/9 类似于双层循环的外层循环，保持值不变，直到内层循环循环了 9 次后，值再改变。而i%9 正好类似于内层循环，值循环依次改变 9 次。

后面都带有 %3 正好是上面提到的 A 和 B 格子对应的数字 mod3 判断是否相等，相等则在一条直线上（ A 和 B 碰面）。

1. for(int i=1;i<=9;i++){  
2.   
3.            for(int j=1;j<=9;j++){  
4.   
5.               if(i%3!=j%3)  
6.   
7.                   System.out.println("a="+i+",b="+j);  
8.   
9.            }  
10.   
11. }

http://blog.csdn.net/zgljl2012/article/details/48636963

解法2

char i = 81;
 while (i--){
  if (i / 9 % 3 == i % 9 % 3) //以81-73为例，前半截i/9一直是8，后半截i%9是0,8-1
   continue;
  printf("A = %d, B = %d\n", i / 9 + 1, i % 9 + 1);
 }

第一种解法是利用位运算，第二种解法利用的是数学运算，如代码中的那行注释： 
以81-73为例，i/9一直是8，i%9是0,8-1 ，通过这种普通（巧妙）的数学运算就到达了遍历的目的。

解法3

相比前面两种解法，解法比较就“简单”了

struct{
  unsigned char a : 4;
  unsigned char b : 4;
 } i;

 for (i.a = 1; i.a <= 9; i.a++)
      for (i.b = 1; i.b <= 9; i.b++)
          if (i.a % 3 == i.b % 3){
               printf("A = %d, B = %d\n", i.a, i.b);
          }

unsigned char a:4 
表示结构体变量a只使用其中的低4位

http://cstriker1407.info/blog/the-beauty-of-the-programming-reading-notes-chess-player-problem/
最简单的Java实现，4个for循环：

for (int lieA = 1; lieA <= 3; lieA++)

{

for (int hangA = 1; hangA <= 3; hangA++)

{

for (int lieB = 1; lieB <= 3; lieB++)

{

if (lieB == lieA)

{

continue;

}

for (int hangB = 1; hangB <= 3; hangB++)

{

int A = lieA * 100 + hangA;

int B = lieB * 100 + hangB;

System.out.println("A:" + A +"   B:" + B);

}

}

}

}

使用9字格进行遍历方法A：

for (int posA = 1; posA <= 9; posA++)

{

for (int posB = 1; posB <= 9; posB++)

{

if (posA %3 == posB % 3)

{

continue;

}

//      int A = ((posA -1)%3+1) * 100 + ((posA - 1)/3 + 1);

//      int B = ((posB -1)%3+1) * 100 + ((posB - 1)/3 + 1);

//      System.out.println("A:" + A +"   B:" + B);

System.out.println("posA:" + posA +"   posB:" + posB);

}

}

使用9字格进行遍历方法B：

/*

为什么是9*9,考虑到A,B的最大值均为9，那么可以确定，A*B的所有值都不会超过9*9，因此

当totalNum从81开始递减的时候，可以保证totalNum/9的值从9开始递减，

由余法运算规则可知，任何数%9都不会比9大，因此totalNum从81开始递减时，totalNum/9的值从9开始递减。

*/

int totalNum = 9*9;

while (totalNum-- != 0)

{

//  totalNum / 9 =>A

//  totalNum % 9 =>B

if ( totalNum/9 % 3 == totalNum % 9 %3 )

{

continue;

}

System.out.println("posA:" + (totalNum/9+1) +"   posB:" + (totalNum%9+1));

}

一点思考：
从遍历方法A和遍历方法B上我们可以看到，两层for循环其实是可以合成一层的，只是计算量不会缩小。

比如原始两层循环：

int m = 5;

int n = 3;

for (int i = 0; i < m; i++)

{

for (int j = 0; j < n; j++)

{

System.out.println("m:" + i + "   n:" + j);

}

}

 合成一层循环：

view source

for (int idx = 0; idx < m*n; idx++)

{

System.out.println("m:" + idx/n + "   n:" + idx%n);

}