中國象棋將帥問題深度解析：單變量實現 N 重循環的巧妙技巧

問題背景

在中國象棋中，若棋盤上僅剩「將」與「帥」兩枚棋子，規則限定：雙方只能在各自的九宮格（3×3 區域）內上下左右移動，不得斜行，且兩將不得「照面」（即不得處於同一列且中間無子）。請列舉所有合法的將帥位置組合，並要求代碼中只能使用一個字節的變量來完成雙重甚至 N 重循環。

三種解決思路

1. 位運算：一字節存兩變量

利用一個 unsigned char（8 位）的高 4 位存儲將的位置，低 4 位存儲帥的位置。通過宏定義實現讀寫操作：

#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 = (b & LMASK) | (n))
#define LSET(b,n) (b = ((b & RMASK) | ((n) << HALF_BITS_LENGTH)))
#define RGET(b) (b & RMASK)
#define LGET(b) ((b & LMASK) >> HALF_BITS_LENGTH)

外層循環遍歷將的 9 個位置，內層遍歷帥的 9 個位置，判斷列號（%3）不同即合法。

2. 位域結構體

C/C++ 支持位域，可直接聲明兩個 4 位無符號字段：

struct {
    unsigned char a: 4; // 將
    unsigned char b: 4; // 帥
} i;

雖然直觀，但本質上仍佔用一字節，屬於語法糖。

3. 單變量模擬雙重循環（核心亮點）

觀察 9×9=81 種組合，單變量 i 從 81 遞減至 0：

• i / 9 相當於外層循環變量（將的位置 0~8）
• i % 9 相當於內層循環變量（帥的位置 0~8）

代碼極其精簡：

void Solution3() {
    unsigned char i = 81;
    while (i--) {
        if (i / 9 % 3 == i % 9 % 3) continue; // 同列則跳過
        printf("%d,%d\n", i / 9, i % 9);
    }
}

擴展：單變量實現 N 重循環通用公式

假設需實現 a1 × a2 × … × aN 的 N 重循環，總迴圈次數 M = a1*a2*…*aN。單變量 val 從 M 遞減至 0，各層循環變量提取公式：

loop1 = val % a1;                 // 最內層
loop2 = (val / a1) % a2;
loop3 = (val / (a1*a2)) % a3;
...
loopN = (val / (a1*a2*...*a(N-1))) % aN; // 最外層

示例：5 × 4 雙重循環，val = 20，內層 val % 4，外層 (val/4) % 5。

總結

位運算與位域屬於「空間換變量」，而單變量循環展開屬於「時間換空間」，利用整除與取餘將多維索引映射到一維，極大節省棧空間，適合嵌入式或受限環境。掌握此技巧，可靈活應對各類多重循環壓縮需求。