【编程之美】中国象棋将帅问题

问题描述

在中国象棋里将和帅是不能碰面的，如下图所示，当将位于d10时，帅就不能在d1,、d2、d3。请写一个程序，输出将、帅所有的合法位置。要求在代码中仅用一个变量。

如果只是输出将、帅的合法位置，那这题就比较容易了，只要二重循环判断一下就行，但后面一个条件就将题目的难度上升了好多。

算法分析

因为是判断两个对象A、B的位置符不符合要求，而且每个对象一共就只有9个位置可选，可以比较快地想到程序的大体框架：

1. 遍历A的位置
2. 遍历B的位置
3. 判断A、B的位置组合是否满足要求
4. 如果满足，则输出

因为每个对象只有9个位置，所以循环次数一共也就81次。

所以，我们需要先给A、B定好坐标系统，下面使用以行优先的顺序使用1-9来表示坐标：

表示位置组合可以这样：
A=1，B=4 ，不合理组合
A=1，B=2 ，合理组合

在编程之美上提出了三种解法：

---

解法1

因为只使用1个变量，而我们要存储的是两个对象的坐标（同时坐标也是循环的计数器），所以我们可以通过分割变量的位达到数据存储的目的。因为char型是8位，可以表示256个数，所以，我们可以用char型变量来表示A、B两个对象的坐标；具体就是使用左边4位表示A坐标，右边4位表示B坐标。

左右两边都要能通过位运算从1遍历到9。下面是编程之美上的代码：

//这个值是记忆存储单元长度的一半
#define HALF_BITS_LENGTH 4
//这个数字表示一个全部bit的mask，在二进制表示中，它是11111111
#define FULLMASK 255
//这个宏表示左bits的mask，在二进制表示中，它是11110000
#define LMASK (FULLMASK << HALF_BITS_LENGTH)
//这个宏表示右bits的mask，在二进制表示中，它表示00001111
#define RMASK (FULLMASK >> HALF_BITS_LENGTH)
//这个宏，将b的右边设置成n
#define RSET(b, n) (b = ((LMASK & b) ^ n))
//这个宏，将b的左边设置为n
#define LSET(b, n) (b = ((RMASK & b) ^ (n << HALF_BITS_LENGTH)))
//这个宏得到b的右边的值
#define RGET(b) (RMASK & b)
//z这个宏得到b左边的值
#define LGET(b) ((LMASK & b) >> HALF_BITS_LENGTH)
//这个数字表示将帅移动范围的行宽度
#define GRIDW 3

#include <stdio.h>

int main(){
	 unsigned char b;
	 for (LSET(b, 1); LGET(b) <= GRIDW * GRIDW; LSET(b, (LGET(b) + 1))){
		  for (RSET(b, 1); RGET(b) <= GRIDW*GRIDW; RSET(b, (RGET(b) + 1))){
			   if (LGET(b) % GRIDW != RGET(b) % GRIDW){
			    printf("A = %d, B = %d\n", LGET(b), RGET(b));
			   }
		  }
	 }
	 getchar();
}

位运算是通过宏实现的，LSET、LGET分别是设置和获取左边四位的值；RSET、RGET分别是设置和获取右边四位的值。

判断A、B坐标是否符合要求是通过求两个位置除以3的余数来判断的。

刚开始看到这题的解法的时候惊呆了，真没有想到那群人竟然能把位运算运用到这地步。。。不过，就在我为这种方法赞叹的时候，编程之美上又有一位仁兄提出下面的解法：

---

解法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位

---