三十六軍官問題

大數學家歐拉曾提出一個問題：即從不同的6個軍團各選6種不同軍階的6名軍官共36人，排成一個6行6列的方隊，使得各行各列的6名軍官恰好來自不同的軍團而且軍階各不相同，應如何排這個方隊？如果用(1，1)表示來自第一個軍團具有第一種軍階的軍官，用(1，2)表示來自第一個軍團具有第二種軍階的軍官，用(6，6)表示來自第六個軍團具有第六種軍階的軍官，則歐拉的問題就是如何將這36個數對排成方陣，使得每行每列的數無論從第一個數看還是從第二個數看，都恰好是由1、2、3、4、5、6組成。歷史上稱這個問題為三十六軍官問題。

基本介紹

• 中文名：三十六軍官問題
• 提出者：歐拉
• 適用領域範圍：工農業生產和科學實驗
• 涉及知識：正交拉丁方

解決

三十六軍官問題提出後，很長一段時間沒有得到解決，直到20世紀初才被證明這樣的方隊是排不起來的。儘管很容易將三十六軍官問題中的軍團數和軍階數推廣到一般的n的情況，而相應的滿足條件的方隊被稱為n階歐拉方。歐拉曾猜測：對任何非負整數t，n=4t+2階歐拉方都不存在。t=1時，這就是三十六軍官問題，而t=2時，n=10，數學家們構造出了10階歐拉方，這說明歐拉猜想不對。但到1960年，數學家們徹底解決了這個問題，證明了n=4t+2(t≥2)階歐拉方都是存在的。

套用

這種方陣在近代組合數學中稱為正交拉丁方，它在工農業生產和科學實驗方面有廣泛的套用。現已經證明，除了2階和6階以外，其它各階3，4，5，7，8，……各階正交拉丁方都是作得出來的。

除了上面的定義外需要注意的是每個組合不能重複，如2階方正會出現類似如下情況：

(1,1) (2,1)

(2,2) (1,2)

由於出現類似(1,1)的重複，問題中36個軍官不可能同時站在不同位置，故不滿足需求，所以2階方正不存在。根據計算機編程能很容易求得3,4,5階的方正，由於組合眾多，現舉例如下：

3階：

(1,1) (2,2) (3,3)

(2,3) (3,1) (1,2)

(3,2) (1,3) (2,1)

4階：

(2,1) (4,4) (3,2) (1,3)

(4,2) (2,3) (1,1) (3,4)

(3,3) (1,2) (2,4) (4,1)

(1,4) (3,1) (4,3) (2,2)

5階：

(1,1) (2,2) (3,5) (4,3) (5,4)

(4,5) (1,3) (5,2) (3,4) (2,1)

(2,4) (5,5) (4,1) (1,2) (3,3)

(5,3) (3,1) (1,4) (2,5) (4,2)

(3,2) (4,4) (2,3) (5,1) (1,5)

c++ 代碼如下：

#include <iostream>#define ARMY_SIZE 5typedef struct snode {    int x;    int y;}node;void set_value(int x, int y);bool can_set(int x, int y, int i, int j);void set_next(int x, int y); node nodes[ARMY_SIZE][ARMY_SIZE];int main(void){    memset(nodes, 0, sizeof(nodes));    set_value(0, 0);    std::cout << "end..." << std::endl;     std::cin.get();     return 0; }void set_value(int x, int y){    for (int i = 1; i < ARMY_SIZE + 1; ++i) {        for (int j = 1; j < ARMY_SIZE + 1; ++j) {            if (can_set(x, y, i, j)) {                nodes[x][y].x = i;                nodes[x][y].y = j;                set_next(x, y);                nodes[x][y].x = 0;                nodes[x][y].y = 0;            }                    }    }}bool can_set(int x, int y, int i, int j){    for (int _x = 0; _x < x; ++_x) {        if (nodes[_x][y].x == i || nodes[_x][y].y == j)            return false;    }    for (int _z = 0; _z < x; ++_z) {        for (int _i = 0; _i < ARMY_SIZE; ++_i) {            if (nodes[_z][_i].x == i && nodes[_z][_i].y == j) {                return false;            }        }    }    for (int _y = 0; _y < y; ++_y) {        if (nodes[x][_y].x == i || nodes[x][_y].y == j)            return false;    }    return true; }void set_next(int x, int y){    if (y + 1 == ARMY_SIZE) {        if (x + 1 == ARMY_SIZE) {            for (int i = 0; i < ARMY_SIZE; ++i) {                for (int j = 0; j < ARMY_SIZE; ++j) {                    std::cout << "(" << nodes[i][j].x << "," << nodes[i][j].y << ") ";                }                std::cout << std::endl;            }            std::cout << "*************************************" << std::endl;        } else {            set_value(x + 1, 0);        }    } else {        set_value(x, y + 1);    }}