猜數字遊戲 (電腦猜人)

前幾天午睡時突然被告知要參加公司內部的程式設計比賽，題目是用C寫一支文字模式的4位數字猜數字遊戲，由使用者來猜電腦的數字。在上星期時其實就已經有公佈了，但我沒有注意到所以是臨時加入，還好這是個簡單的題目，不用花多少時間就可以寫出來。

規則：

- 這是一對一比賽，雙方各選擇一4位數字，不讓對方知道。
- 4位數字由數字0至9組成，每位數不得重複。
- 雙方輪流猜對方的數字，直到一方猜中為止。
- A方猜B方的數字後，B方根據A方的猜測回答幾A幾B。
- 一個A表示猜中一個數字且位置正確，一個B表示猜中一個數字但位置不正確。
- 當一方猜中4A0B時即表示猜中對方全部4個數字且位置正確，贏得比賽。
- 例：B的謎底是4208，底下箭頭左測是A的猜測，箭頭右測是B的回答。
　　　1234 ==> 1A1B
　　　5678 ==> 1A0B
　　　2406 ==> 1A2B
　　　...
　　　4208 ==> 4A0B

;

寫個程式讓玩家來猜電腦的數字不難，不過我從來沒有寫過讓電腦來猜玩家數字的版本，所以花了點時間想想怎麼寫。

研究後歸納出二個點。

1, 使用窮舉法將所有可能數字組合列出。
2, 每次猜測後根據結果排除不可能是答案的組合，重複這個動作直到猜中答案為止。

第1點只是實作問題，第2點概念也很簡單，但要過濾不是答案的組合根據的是什麼？乍看之下沒什麼頭緒，不過想通之後就非常簡單了。

它的基本原理如下：假如謎底是4561，如果猜1524則會得到1A2B。從相反的角度來看，如果謎底是1524，則猜4561時也會得到1A2B的回答。

利用這個方法，每一次猜測一個數字X後，再以這個數字當作答案，來和所有剩下來的候選答案作比對，如果得到的結果(幾A幾B)和數字X是一樣的話，就把這個數字保留下來繼續作為候選答案，否則就過把這個數字過濾掉。下一把，繼續從候選答案裡選一個出來猜，重複上面的動作，直到猜中為止。

;

C++ STL的algorithm裡有個叫作next_permutation的函數，可以用來生成排列。

#include <iostream>
#include <algorithm>
using namespace std;

int main () {
  int myints[] = {1,2,3};

  sort(myints, myints+3);

  do {
    cout << myints[0] << " " << myints[1] << " " << myints[2] << endl;
  } while (next_permutation(myints,　myints+3));

  return 0;
}

執行結果如下：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

不過因為我們是要產生4位數字的組合，而這4個數字是由0~9裡選出來的，也就是要作m取n的排列，但是next_permutation只能作n位數排列，所以需要另想辨法。

稍微設計一下之後，把這個操作分為二部份。第一部份首先選擇4位數數組，例如1234或2345等，接著再以next_permutation產生這些數組的所有排列，最後把所有這些數組的排列合拼，就能得到所有可能答案的排列組合。

那麼要怎麼挑出數組？也就是作出10取4的組合。

首先我把每一個數字當作一個位元來看，0x3ff這個數由十個位元1組成，可以表示為0~9十個數字全選。我只需要簡單跑個迴圈，從0開始找到0x3ff，如果找到的數是包含4個為1的位元的話，那就表示找到了一個我要的數組，接著把對應位元為1的位置轉換為數字就可以了。然後再拿它來透過next_permutation產生所有排列。

例：

9876543210
----------
0000001111 ==> 3210
0000010111 ==> 4210
1001001100 ==> 9632
依此類推..

如此就能產生所有可能的排列組合，完成第一部份的工作。至於第二部份就沒什麼好說的了，重點是在於一開始如何想通怎麼作，實作就更簡單了。