Đây là bài toán đố khá nổi tiếng xuất hiện trên mạng với nhiều biến thể khác nhau. Các bài viết đều cho rằng Albert Einstein chính là tác giả của bài toán đố này. Các bài viết cũng tuyên bố rằng 98% dân số (trên trái đất này?) không giải được nó. Một số nhà bình luận cho rằng Einstein tạo ra các câu đố kiểu như vậy không phải để kiểm tra trí thông minh của những sinh viên muốn được ông nhận làm học trò nghiên cứu sinh, mà là thách đố để từ chối yêu cầu của họ. Tất cả những câu chuyện trên không có gì để đảm bảo sự thật cả. Riêng tôi nghĩ, tác giả bài viết khơi mào (và những người sau dựa vào bài viết đó để lan truyền đi) khẳng định 98% dân số không giải được chỉ là chiêu trò thu hút người đọc, và bài toán đố nếu thực sự do Einstein đưa ra thì có lẽ cũng chỉ là câu đố vui trong giờ giảng bài của ông mà thôi. Tuy nhiên, bất kể nguồn gốc như thế nào, thì đây cũng là một bài toán đố rất thú vị.
Nội dung bài toán đố
Bài toán đố này có nhiều biến thể khác nhau ở vài chi tiết. Dưới đây là nội dung biến thể khá phổ biến đã được dịch ra tiếng Việt mà tôi chọn để trình bày trong bài viết này:
Có 5 ngôi nhà, mỗi nhà có một màu khác nhau. Trong mỗi nhà có một người có quốc tịch khác nhau ở. Mỗi người này đều thích một loại nước uống, hút một loại thuốc lá và nuôi một con vật trong nhà. Cả 5 người đều không có người nào cùng thích loại nước uống, hút loại thuốc lá hay có vật nuôi trong nhà giống như những người hàng xóm của mình. Ngoài ra, sở thích của những người này còn thỏa mãn các điều kiện sau:
- Người Anh ở trong nhà màu đỏ.
- Người Thuỵ Điển nuôi chó.
- Người Đan-mạch thích uống chè.
- Ngôi nhà màu xanh lá cây nằm bên trái ngôi nhà màu trắng.
- Người ở nhà màu xanh lá cây thích uống cafe.
- Người hút thuốc hiệu Pall Mall nuôi chim.
- Người ở nhà nằm giữa thích uống sữa.
- Người ở nhà màu vàng hút thuốc hiệu Dunhill.
- Người Na-uy ở nhà đầu tiên.
- Người hút thuốc hiệu Blend ở cạnh nhà ngườì có nuôi mèo.
- Người có nuôi ngựa ở cạnh nhà người hút thuốc hiệu Dunhill.
- Người hút thuốc hiệu BlueMaster thích uống bia.
- Người Na-uy ở cạnh nhà màu xanh nước biển.
- Người Đức hút thuốc hiệu Prince.
- Người hút thuốc hiệu Blend có ngườì hàng xóm thích uống nước lọc.
Câu hỏi: Ai là người nuôi cá ?
Cách giải phổ biến là kẻ bảng và loại trừ. Tôi đã thử giải bài toán này bằng cách dùng bút chì màu nối các điểm (kiểu mindmap) và mất khoảng 30 phút. Thử search trên google, tôi nhận thấy trong tất cả các kết quả tìm kiếm đều cho đáp án là “người Đức nuôi cá”. Tự hỏi rằng ngoài đáp án trên liệu còn có khả năng nào khác không? Nếu có thì có tất cả bao nhiêu đáp án? Tôi quyết định dùng công cụ phổ biến bây giờ mà khi Einstein đặt ra bài toán chưa có, đó là máy tính, để giải đáp thắc mắc của mình (chứ không phải giải bài toán đâu nhé, dùng giấy bút là đủ tìm được một đáp án rồi bạn ạ).
Lập trình giải bài toán đố
Phương pháp đơn giản nhất (và cũng là dở nhất) để lập trình giải bài toán đố này chính là vét cạn (brute force), tức là kiểm tra tất cả các khả năng kết hợp có thể có. May mắn cho tôi là bài toán đố này có số chiều không lớn - 5 ngôi nhà với 5 đặc điểm khác nhau - nên số lượng các khả năng kết hợp cũng không quá lớn (chính xác là (5!)^5 = 24883200000 trường hợp). Đối với chúng ta, số trường hợp này quả là lớn, nhưng với máy tính, số lượng này chỉ là … muỗi.
Tổ chức dữ liệu
Sử dụng một mảng hai chiều (tạm gọi là mảng P) để lưu trữ một phương án kết hợp màu sắc, người, đồ uống, thuốc lá, vật nuôi cho các ngôi nhà. Mảng này chứa tên của các đặc điểm, mỗi dòng tương ứng với một đặc điểm, mỗi cột tương ứng với một ngôi nhà.
Để thuận tiện cho lập trình, chúng ta dùng số thay cho tên của các đối tượng. Chẳng hạn với màu sắc: “Red”-0, “White”-1, “Yellow”-2, “Green”-3, “Blue”-4; với đồ uống: “Tea”-0, “Coffee”-1, “Milk”-2, “Beer”-3, “Water”-4; tương tự với thuốc lá, vật nuôi và quốc tịch. Chúng ta sử dụng một mảng 2 chiều (tạm gọi là mảng name_matrix) để tương ứng tên đối tượng với số như sau:
Với tương ứng giữa tên và số ở trên, mảng phương án kết hợp P có dạng như sau:
Với phương án kết hợp đang có trong P, chúng ta kiểm tra xem phương án này có thỏa mãn các quy tắc của bài toán hay không. Nếu thỏa mãn, chúng ta in kết quả ra màn hình. Sau đó chuyển sang phương án kết hợp tiếp theo.
Tạo phương án kết hợp tiếp theo
Mỗi phương án kết hợp trong P bao gồm 5 mảng con 5 phần tử, mỗi mảng con thể hiện cho một cách sắp đặt các giá trị của một đặc điểm cho các ngôi nhà. Viết 5 mảng con thành 5 dòng. Giả sử chúng ta đã có cách sinh ra các hoán vị liên tiếp của một mảng 5 phẩn tử (sẽ trình bày bên dưới, trong phần “Thuật toán sinh hoán vị liên tiếp”). Khi đó, hãy hình dung chúng ta viết các hoán vị liên tiếp của 5 mảng con này lần lượt ra bên phải, theo chiều ngang. Chúng ta sẽ có tất cả 120 cột tương ứng với 120 hoán vị của mảng 5 phần tử.
Trong hình vẽ minh họa ở trên, đường mũi tên đỏ & xanh xác định phương án kết hợp hiện tại của ma trận P, là sự kết hợp của hoán vị 1 của Nationalities, 2 của Colors, 58 của Drinks, 57 của Pets và 118 của Cigarettes (1 - 2 - 58 - 57 - 118). Phương án tiếp theo sẽ là kết hợp 1 - 2 - 58 - 57 - 119, tức là dịch chuyển mũi tên xanh về bên phải 1 vị trí. Cứ tiếp tục như vậy cho đến hoán vị cuối cùng của Cigarettes.
Sau khi duyệt đến hoán vị cuối cùng, mũi tên đỏ trỏ vào Pets sẽ chuyển đến hoán vị tiếp theo của Pets, và mũi tên xanh lại trỏ về hoán vị đầu tiên của Cigarettes, bắt đầu chu kỳ mới trên dãy hoán vị này.
Với sự kết hợp này, chúng ta có thể hình dung các phương án kết hợp của P thay đổi như sau:
Tương ứng mũi tên màu xanh duyệt từ hoán vị đầu đến hoán vị cuối của dãy hoán vị Cigarettes (có chỉ số dòng trong ma trận là N_CI=4) chính là vòng lặp:
p[N_CI] = new int[]{0, 1, 2, 3, 4};
do {
// thực hiện kiểm tra các ràng buộc bài toán
} while (genNextPermutation(p[N_CI]));Trong đó, hàm genNextPermutation(a) có nhiệm vụ tạo ra các hoán vị liên tiếp của mảng a. Kết hợp với mũi tên màu đỏ duyệt từ hoán vị đầu đến cuối dãy hoán vị Pets (với chỉ số dòng trong ma trận là N_PE=3), đoạn mã lệnh tương ứng sẽ là 2 vòng lặp lồng nhau:
p[N_PE] = new int[]{0, 1, 2, 3, 4};
do {
// do something ...
p[N_CI] = new int[]{0, 1, 2, 3, 4};
do {
// thực hiện kiểm tra các ràng buộc bài toán
// nếu thỏa mãn thì in kết quả ra màn hình
} while (genNextPermutation(p[N_CI]));
} while (genNextPermutation(p[N_PE]));Kết hợp quá trình duyệt trên các dãy hoán vị còn lại, chúng ta có vòng lặp tạo các phương án kết hợp liên tiếp như sau:
p[N_CO] = new int[]{0, 1, 2, 3, 4};
do {
// do something ...
p[N_DR] = new int[]{0, 1, 2, 3, 4};
do {
// do something ...
p[N_NA] = new int[]{0, 1, 2, 3, 4};
do {
// do something ...
p[N_PE] = new int[]{0, 1, 2, 3, 4};
do {
// do something ...
p[N_CI] = new int[]{0, 1, 2, 3, 4};
do {
// thực hiện kiểm tra các ràng buộc bài toán
// nếu thỏa mãn thì in kết quả ra màn hình
} while (genNextPermutation(p[N_CI]));
} while (genNextPermutation(p[N_PE]));
} while (genNextPermutation(p[N_NA]));
} while (genNextPermutation(p[N_DR]));
} while (genNextPermutation(p[N_CO]));Vấn đề còn lại ở đây là cơ chế vận hành của hàm sinh hoán vị liên tiếp genNextPermutation(a).
Thuật toán sinh hoán vị liên tiếp
Có nhiều thuật toán sinh hoán vị liên tiếp (bạn nào quan tâm xem thêm trong bài viết Permutation). Để thuận lợi cho việc diễn đạt, trong bài viết này tôi chọn thuật toán sinh hoán vị liên tiếp theo thứ tự từ điển.
Thuật toán tìm hoán vị tiếp theo của mảng a theo thứ tự từ điển được mô tả như sau:
- Bước 1: tìm chỉ số j lớn nhất sao cho a(j) < a(j+1). Nếu không tìm thấy, thì đây là hoán vị cuối cùng, thoát khỏi thuật toán.
- Bước 2: tìm chỉ số k lớn nhất sao cho a(j) < a(k).
- Bước 3: hoán đổi giá trị a(j) và a(k).
- Bước 4: đảo ngược danh sách từ phần tử a(j+1) đến phần tử cuối mảng.
Như vậy, để sinh toàn bộ các hoán vị của một mảng, chúng ta bắt đầu từ mảng có thứ tự từ điển nhỏ nhất, trong trường hợp bài toán của chúng ta là {0, 1, 2, 3, 4}. Lặp các bước trong thuật toán mô tả ở trên cho đến khi thuật toán dừng: không tìm thấy j sao cho a(j) < a(j+1), tức là mảng số của chúng ta được sắp theo thứ tự giảm dần {4, 3, 2, 1, 0}.
Theo thuật toán này, hàm genNextPermutation(a) được lập trình như sau:
public static boolean genNextPermutation(int[] a) {
int n = a.length;
if (n < 2) return false;
// tìm j là chỉ số lớn nhất mà a[j] < a[j+1]
int j;
for(j=n-2; j>=0; j--) if (a[j] < a[j+1]) break;
if (j == -1) return false;
// tìm k là chỉ số lớn nhất mà a[j] < a[k]
int k;
for(k=n-1; k>j; k--) if (a[k] > a[j]) break;
// hoán đổi giá trị a[j] và a[k]
int t = a[j]; a[j] = a[k]; a[k] = t;
// đảo danh sách sau a[j] (từ a[j+1] đến hết)
int s = j + 1;
int r = n - 1;
while(r > s) {
t = a[r]; a[r] = a[s]; a[s] = t;
r--;
s++;
}
return true;
}Lưu ý trong chương trình mẫu có phần Unit Test để kiểm thử hàm genNextPermutation(a).
Viết chương trình
Chương trình gồm có 3 phần mã lệnh. Phần thứ nhất là phương thức sinh hoán vị liên tiếp (đã trình bày ở phần phía trên). Phần tiếp theo là khai báo cấu trúc dữ liệu và các hàm truy cập giá trị, in kết quả ra màn hình:
public static final int N_NA = 0;
public static final int N_CO = 1;
public static final int N_DR = 2;
public static final int N_PE = 3;
public static final int N_CI = 4;
public static String[][] name_matrix = {
{"Englishman", "Dane", "Swede", "German", "Norwegian"},
{"Red", "White", "Yellow", "Green", "Blue"},
{"Tea", "Coffee", "Milk", "Beer", "Water"},
{"Dog", "Cat", "Horse", "Fish", "Bird"},
{"PallMall", "Dunhill", "Prince", "BlueMaster", "Blend"}
};
public static HashMap<String, Integer>[] name2number = null;
public static String getNameOfNumber(int number, int type) {
return name_matrix[type][number];
}
public static int getNumberOfName(String name, int type) {
if (name2number == null) {
name2number = new HashMap[name_matrix.length];
for(int i=0; i<name_matrix.length; i++) {
name2number[i] = new HashMap<String, Integer>();
}
}
if (!name2number[type].containsKey(name)) {
for (int i = 0; i < name_matrix[type].length; i++) {
if (name_matrix[type][i].equals(name)) {
name2number[type].put(name, i);
}
}
}
return name2number[type].get(name);
}
public static int findIndexOf(String name, int type, int[][] position) {
for (int i = 0; i < position[type].length; i++) {
if (position[type][i] == getNumberOfName(name, type)) {
return i;
}
}
throw new IllegalArgumentException("findIndexOf() error!");
}
public static void printHouse(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.format("%10d | ", i + 1);
}
System.out.print("\n");
}
public static void printNames(int nameType, int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.format("%10s | ", getNameOfNumber(a[i], nameType));
}
System.out.print("\n");
}Phần cuối cùng làm hàm main() chứa các vòng lặp lồng nhau để vét cạn tất cả các trường hợp:
public static void main(String[] args) {
int count = 0;
int[][] p = {
{0, 1, 2, 3, 4},
{0, 1, 2, 3, 4},
{0, 1, 2, 3, 4},
{0, 1, 2, 3, 4},
{0, 1, 2, 3, 4}
};
p[N_CO] = new int[]{0, 1, 2, 3, 4};
do {
//13. nguoi Na-uy o canh nha mau xanh nuoc bien va
//9. nguoi Na-uy o nha dau tien
int co_blue = findIndexOf("Blue", N_CO, p);
if (co_blue != 1) continue;
//4. ngoi nha xanh la cay nam ben trai nha mau trang
int co_green = findIndexOf("Green", N_CO, p);
int co_white = findIndexOf("White", N_CO, p);
if (co_green > co_white) continue;
int co_yellow = findIndexOf("Yellow", N_CO, p);
int co_red = findIndexOf("Red", N_CO, p);
//Drinks
p[N_DR] = new int[]{0, 1, 2, 3, 4};
do {
//5. nguoi nha xanh la cay thich uong ca phe
int dr_cafe = findIndexOf("Coffee", N_DR, p);
if (dr_cafe != co_green) continue;
//7. nguoi o nha giua thich uong sua
int dr_milk = findIndexOf("Milk", N_DR, p);
if (dr_milk != 2) continue;
int dr_beer = findIndexOf("Beer", N_DR, p);
int dr_tea = findIndexOf("Tea", N_DR, p);
int dr_water = findIndexOf("Water", N_DR, p);
//Cigarettes
p[N_CI] = new int[]{0, 1, 2, 3, 4};
do {
//8.nguoi o nha mau vang hut thuoc hieu Dunhill
int ci_dunhill = findIndexOf("Dunhill", N_CI, p);
if (ci_dunhill != co_yellow) continue;
//12. nguoi hut thuoc hieu bluemaster thich uong bia
int ci_bluemaster = findIndexOf("BlueMaster", N_CI, p);
if (ci_bluemaster != dr_beer) continue;
//15. nguoi hut thuoc Blend co hang xom thich uong nuoc
int ci_blend = findIndexOf("Blend", N_CI, p);
if ((dr_water - ci_blend != 1) &&
(dr_water - ci_blend != -1)) continue;
int ci_pallmall = findIndexOf("PallMall", N_CI, p);
int ci_prince = findIndexOf("Prince", N_CI, p);
// Pets
p[N_PE] = new int[]{0, 1, 2, 3, 4};
do {
//6. nguoi hut thuoc la hieu PallMall nuoi chim
int pe_bird = findIndexOf("Bird", N_PE, p);
if (ci_pallmall != pe_bird) continue;
//10. nguoi hut thuoc Blend o canh nha nguoi nuoi meo
int pe_cat = findIndexOf("Cat", N_PE, p);
if ((pe_cat - ci_blend != 1) &&
(pe_cat - ci_blend != -1)) continue;
//11. nguoi nuoi ngua o canh nha nguoi hut thuoc Dunhill
int pe_horse = findIndexOf("Horse", N_PE, p);
if ((pe_horse - ci_dunhill != 1) &&
(pe_horse - ci_dunhill != -1)) continue;
int pe_dog = findIndexOf("Dog", N_PE, p);
//Nationalities
p[N_NA] = new int[]{0, 1, 2, 3, 4};
do {
//9. nguoi na-uy o nha dau tien
int na_norwe = findIndexOf("Norwegian", N_NA, p);
if (na_norwe != 0) continue;
//1. nguoi anh o nha mau do
int na_engman = findIndexOf("Englishman", N_NA, p);
if (na_engman != co_red) continue;
//2. nguoi thuy dien nuoi cho
int na_swede = findIndexOf("Swede", N_NA, p);
if (na_swede != pe_dog) continue;
//3. nguoi dan mach thich uong che
int na_dane = findIndexOf("Dane", N_NA, p);
if (na_dane != dr_tea) continue;
//14. nguoi duc hut thuoc hieu Prince
int na_german = findIndexOf("German", N_NA, p);
if (na_german != ci_prince) continue;
count++;
System.out.format("Solution #%d:%n", count);
System.out.format("%13s:", "Houses");
printHouse(p[N_CO]);
System.out.format("%13s:", "Colors");
printNames(N_CO, p[N_CO]);
System.out.format("%13s:", "Drinks");
printNames(N_DR, p[N_DR]);
System.out.format("%13s:", "Cigarettes");
printNames(N_CI, p[N_CI]);
System.out.format("%13s:", "Pets");
printNames(N_PE, p[N_PE]);
System.out.format("%13s:", "Nationalities");
printNames(N_NA, p[N_NA]);
System.out.println();
} while (genNextPermutation(p[N_NA]));
} while (genNextPermutation(p[N_PE]));
} while (genNextPermutation(p[N_CI]));
} while (genNextPermutation(p[N_DR]));
} while (genNextPermutation(p[N_CO]));
}Kết quả chạy chương trình
Ấn tượng đầu tiên đó là cảm giác vui sướng vì biết được bài toán đố trên (biến thể tiếng Việt mà tôi mô tả ở trên) có tất cả 7 khả năng, với 3 đáp án cho câu hỏi “ai là người nuôi cá”: Đức, Đan Mạch và Nauy.
Solution #1:
Houses: 1 | 2 | 3 | 4 | 5 |
Colors: Yellow | Blue | Red | Green | White |
Drinks: Water | Tea | Milk | Coffee | Beer |
Cigarettes: Dunhill | Blend | PallMall | Prince | BlueMaster |
Pets: Cat | Horse | Bird | Fish | Dog |
Nationalities: Norwegian | Dane | Englishman | German | Swede |
Solution #2:
Houses: 1 | 2 | 3 | 4 | 5 |
Colors: Green | Blue | Red | Yellow | White |
Drinks: Coffee | Water | Milk | Tea | Beer |
Cigarettes: PallMall | Prince | Blend | Dunhill | BlueMaster |
Pets: Bird | Cat | Horse | Fish | Dog |
Nationalities: Norwegian | German | Englishman | Dane | Swede |
Solution #3:
Houses: 1 | 2 | 3 | 4 | 5 |
Colors: Green | Blue | Red | Yellow | White |
Drinks: Coffee | Water | Milk | Tea | Beer |
Cigarettes: PallMall | Prince | Blend | Dunhill | BlueMaster |
Pets: Bird | Fish | Horse | Cat | Dog |
Nationalities: Norwegian | German | Englishman | Dane | Swede |
Solution #4:
Houses: 1 | 2 | 3 | 4 | 5 |
Colors: Green | Blue | White | Red | Yellow |
Drinks: Coffee | Water | Milk | Beer | Tea |
Cigarettes: PallMall | Prince | Blend | BlueMaster | Dunhill |
Pets: Bird | Cat | Dog | Horse | Fish |
Nationalities: Norwegian | German | Swede | Englishman | Dane |
Solution #5:
Houses: 1 | 2 | 3 | 4 | 5 |
Colors: Green | Blue | White | Yellow | Red |
Drinks: Coffee | Water | Milk | Tea | Beer |
Cigarettes: PallMall | Prince | Blend | Dunhill | BlueMaster |
Pets: Bird | Cat | Dog | Fish | Horse |
Nationalities: Norwegian | German | Swede | Dane | Englishman |
Solution #6:
Houses: 1 | 2 | 3 | 4 | 5 |
Colors: Green | Blue | White | Yellow | Red |
Drinks: Coffee | Water | Milk | Tea | Beer |
Cigarettes: PallMall | Prince | Blend | Dunhill | BlueMaster |
Pets: Bird | Fish | Dog | Cat | Horse |
Nationalities: Norwegian | German | Swede | Dane | Englishman |
Solution #7:
Houses: 1 | 2 | 3 | 4 | 5 |
Colors: Green | Blue | Yellow | Red | White |
Drinks: Coffee | Water | Milk | Beer | Tea |
Cigarettes: Blend | Prince | Dunhill | BlueMaster | PallMall |
Pets: Fish | Cat | Dog | Horse | Bird |
Nationalities: Norwegian | German | Swede | Englishman | Dane |Các bạn có thể tải mã nguồn đầy đủ của ví dụ minh họa để chạy thử.
