编程之美 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的位置

　　　　　　判断是否满足不在一列的条件

　　　　　　　　满足，输出AB。

方法一：

AB分别在3x3的区域内移动，各有9个位置，总共81种可能。

选取合适的数据类型，一个8位的byte类型可以表达2的8次方256个数字，表示AB的位置。可以用2进制1-9表示AB的9个位置

1为0001

9为1001

8位中，前4位表示A的位置，后四位表示B的位置。现在需要解决的问题是如何对一个变量的左边和右边分别读取。

将 byte b（10100101）的右边 4 bit（0101）设为 n（0011）：

11110000（LMASK）
& 10100101（b）
--------------
10100000

然后将上一步得到的结果与 n 做或运算
10100000（LMASK & b）
^ 00000011（n）
------------
10100011

将 byte b（10100101）左边的 4 bit（1010）设为 n（0011）：
首先，清除 b 左边的 bits，同时保持右边的 bits:
　00001111（RMASK）
& 10100101（b）
--------------
00000101

现在，把 n 移动到 byte 数据的左边
n << 4 = 00110000
然后对以上两步得到的结果做或运算，从而得到最终结果。
00000101（RMASK & b）
^ 00110000（n << 4）
--------------
00110101

得到 byte 数据的右边 4 bits 或左边 4 bits（e.g. 10100101 中的 1010 以及 0101）：
清除 b 左边的 bits，同时保持右边的 bits
00001111（RMASK）
& 10100101（b）
--------------
00000101
清除 b 的右边的 bits，同时保持左边的 bits
11110000（LMASK）
& 10100101（b）
--------------
10100000
将结果右移 4 bits
10100000 >> 4 = 00000101

代码：

#include "stdio.h"
#define HALF_BITS_LENGTH 4 
// 这个值是记忆存储单元长度的一半，在这道题里是4bit
#define FULLMASK 255
// 这个数字表示一个全部bit的mask，在二进制表示中，它是11111111。

#define LMASK (FULLMASK<<HALF_BITS_LENGTH) 
// 这个宏表示左bits的mask，在二进制表示中，它是11110000。
#define RMASK (FULLMASK>>HALF_BITS_LENGTH) 
// 这个宏表示左bits的mask，在二进制表示中，它是11110000。

#define RSET(b,n) (b=((RMASK&b)^(n))) // 这个宏，将b的右边设置成n
#define LSET(b,n) (b=((RMASK&b)^((n)<<HALF_BITS_LENGTH)))  // 这个宏，将b的左边设置成n

#define RGET(b) (RMASK&b)  // 这个宏，将b的右边设置成n
#define LGET(b) ((LMASK&b)>>HALF_BITS_LENGTH)  // 这个宏得到b的左边的值
#define GRIDW 3  // 这个数字表示将帅移动范围的行宽度。

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
", LGET(b), RGET(b));
    return 0;
}

方法二：

使用结构体数据类型，结构体的定义如下

在C语言中，结构体(struct)指的是一种数据结构，是C语言中聚合数据类型(aggregate data type)的一类。结构体可以被声明为变量、指针或数组等，用以实现较复杂的数据结构。结构体同时也是一些元素的集合，这些元素称为结构体的成员(member)，且这些成员可以为不同的类型，成员一般用名字访问。

特点是几个变量共用一个内存位置。

我们定义一个结构体，包含a，b两个变量，用来记录AB的位置，他们共用一片存储位置。

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

代码如下：

#include "stdio.h"

struct kk{
    unsigned char a:4;
    unsigned char b:4;
};
    
int main(){
    struct kk 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 		",i.a,i.b);
    return 0;
}

输出：