[程式之美] 1.2 中國象棋將帥問題 @ Edison.X. Blog

題目說明

在中國象棋中，雙方之「將」與「帥」不能碰面，假設棋盤上只剩「將」與「帥」二子 (約定用 A 表示「將」，B 表示「帥」)，且被限制在己方之 3*3 正方格內移動。

請寫出一程式，輸出 A, B 所有合法位置，並要求只能用一變數。

解法與說明

這份題目由軟體亞洲研究院工程師 Matt Scott 提供。若不考慮為單一變數限制，非常容易解，若用初學的暴力硬破的話長這樣

#include <stdio.h>
int main()
{
    int x1, y1, x2, y2;
    for(x1=0; x1<=2; ++x1){
       for(y1=0; y1<=2; ++y1){
          for(x2=0; x2<=2; ++x2){
             for(y2=0; y2<=2; ++y2){
                /* x1 與 x2 不同時便為合理 */
                if(x1!=x2) printf("A(%d,%d), B(%d,%d)\n", x1, y1, x2, y2);
            }
          }
       }
    }
    return 0;
}

為說明方便，以數字 1~9 表示 A, B 之座標，如下所示

這樣可只使用二個變數完成

#include <stdio.h>
int main()
{
    int A=1, B=1;
    for(A=1; A<=9; ++A){
       for(B=1; B<=9; ++B){
          if(A%3!=B%3) printf("A:%d, B:%d\n", A, B);
       }
    }
    return 0;
}

但仍不是題意所要求的一個變數完成，於是開始考慮另一種方式。由於要求的範圍 A, B 均為 1~9，各需 4 bits，故考慮以下編碼方式

bit7	bit6	bit5	bit4	bit3	bit2	bit1	bit0
a3	a2	a1	a0	b4	b3	b2	b1

這麼做便可將 A, B 都存在一 unsigned char 裡。問題在於如何使用 bit 運算，將資料從此一 byte 變數之左邊與右邊分別存入與讀出。最後之挑戰，乃在於如何不宣告其他變數之前提下，建立一個 for loop。

#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，以二進位表示是00001111。
#define RSET(b, n) (b = ((LMASK & b) ^ n))
// 這個巨集將b 的右邊設置成n
#define LSET(b, n) (b = ((RMASK & b) ^ (n << HALF_BITS_LENGTH)))
// 這個巨集，將b 的左邊設置成n
#define RGET(b) (RMASK & b)
// 這個巨集得到b 的右邊的值
#define LGET(b) ((LMASK & b) >> HALF_BITS_LENGTH)
// 這個巨集得到b 的左邊的值
#define GRIDW 3
// 這個數字表示將帥移動範圍的行寬度。
#include <stdio.h>
#define HALF_BITS_LENGTH 4
#define FULLMASK 255
#define LMASK (FULLMASK << HALF_BITS_LENGTH)
#define RMASK (FULLMASK >> HALF_BITS_LENGTH)
#define RSET(b, n) (b = ((LMASK & b) ^ n))

#define LSET(b, n) (b = ((RMASK & b) ^ (n << HALF_BITS_LENGTH)))
#define RGET(b) (RMASK & b)
#define LGET(b) ((LMASK & b) >> HALF_BITS_LENGTH)
#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\n", LGET(b), RGET(b));
    return 0;
}

然而，於 MSRA 裡有他人說，下面程式碼也能達到同樣目的

BYTE i=81;
while(i--){
    if(i/9 % 3 == i % 9 % 3) continue; /* 不合條件 */
    printf("A=%d, B=%d\n", i/9%3, i%9%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);

[評論]

1. 雖文前使用 Bitwise 是個繞路的方法，於此實用性也不高，但確實可讓人參考，因 Bitwise 確實為加速常用之技巧。

2. 之前寫過「惡搞一行版九九乘法表」， ( 會叫 "惡搞版" 就是實際上別那麼做) ，原始碼大致如下所示

// C99 雙變數版
for(int i=1, j=1; i<=9; printf("%2d*%2d=%2d\n",i,j,i*j),(j==9?j=1,i++:j++));
// C99 單變數版
for(int j=0; j<9*9; printf("%2d*%2d=%2d\n",j/9+1, j%9+1, (j/9+1)*(j%9+1)),j++);

注意到其中一份 code 只有用到一個變數。這二個問題事實上都很像！雖上述是用 int 去存乘數與被乘數，但確實可只用 8 bits 變數存下來，另也可使用 bitwise 方式進行，大致上如下所示

#include <stdio.h>

#define LCLR(x)   ( (x) = (x) & 0x0f) /* clear high 4 bits of x */
#define RCLR(x)   ( (x) = (x) & 0xf0) /* clear low 4 bits of x */
#define LSET(x,v) ( LCLR(x), (x) = (x) | ((v)<<4) ) /* set the value of low 4 bits of x */
#define RSET(x,v) ( RCLR(x), (x) = (x) | (v)) /* set the value of high 4 bits of x */
#define LGET(x)   ( ( (x) & 0xf0) >> 4) /* get the value of high 4 bits of x */
#define RGET(x)   ( ( (x) & 0x0f)     ) /* get the value of low  4 bits of x */
#define INC_L(x)  ( (x) = (x) + 0x10) /* increment one of high 4 bits of x  */
#define INC_R(x)  ( (x) = (x) + 0x01) /* increment one of low  4 bits of x  */

int main()
{
    unsigned char x;

    for(LSET(x, 2); LGET(x)<=9; INC_L(x)){
       for(RSET(x, 1); RGET(x)<=9; INC_R(x)){
          printf("%2d*%2d=%2d  ", LGET(x), RGET(x), LGET(x)*RGET(x));
       }
       putchar('\n');
    }
    return 0;
}

寫得沒原題漂亮，但只為大概之展示。額外補充，事實上「九九乘法表」可以研究到不少東西，除了正常版、一行版、單變數版之外，也有遞迴的九九乘法表。

#include <stdio.h>

void _99(int i, int j)
{
    if(i<=9){
       printf("%d*%d=%2d\t", i, j, i*j);
       if(j<9) _99(i, j+1);
       else putchar('\n'), _99(i+1, 1);
    }
}

int main()
{
    _99(2, 1);
    return 0;
}