Em đang có bài toán là dùng backtracking để giải Einsteins problem.
Einsteins problem: https://web.stanford.edu/~laurik/fsmbook/examples/Einstein’sPuzzle.html
Facts about Einstein’s problem:
• There are 5 houses (along the street) in 5 different colors:
blue, green, red, white, and yellow.
• In each house lives a person of a different nationality:
Brit, Dane, German, Norwegian and Swede.
• These 5 owners drink a certain of beverage:
beer, coffee, milk, tea and water,
• These 5 owners smoke a certain brand of cigar:
Blue Master, Dunhill, Pall Mall, Prince and Blend,
• These 5 owners keep a certain pet:
cat, bird, dog, fish and horse.
• No owners have the same pet, smoke the same brand of cigar, or drink the
same beverage.
Hints and constraints:
• The Brit lives in a red house.
• The Swede keeps dogs as pets.
• The Dane drinks tea.
• The green house is on the left of the white house (next to it).
• The green house owner drinks coffee.
• The person who smokes Pall Mall rears birds.
• The owner of the yellow house smokes Dunhill.
• The man living in the house right in the center drinks milk.
• The Norwegian lives in the first house.
• The man who smokes Blend lives next to the one who keeps cats.
• The man who keeps horses lives next to the man who smokes Dunhill.
• The owner who smokes Blue Master drinks beer.
• The German smokes Prince.
• The Norwegian lives next to the blue house.
• The man who smokes Blend has a neighbor who drinks water.
Ý tưởng của em là tạo 1 mảng 2 chiều chứa những facts có sẵn rồi so sánh với những ràng buộc và hints để tạo ra cái hàm is_safe. Nhưng ko đc khả quan cho lắm.
Hiện tại em đang kẹt ở chỗ design input đầu vào cho bài toán để match với cái hints và constraints đã cho. Anh nào có cao kiến có thể cho em xin chút gợi ý đc ko ạ? Em cảm ơn ạ!
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?