جواب «Try It in Python: Search for a Plan» چالش 7 از جلسهی 37
سؤال
«با پایتون امتحان کن» (اختیاری). n را (از ۲ تا ۵) بخوان. برنامه همهی راههای جابهجا کردن را جستوجو کند و complete یا not complete چاپ کند.
تابعِ search(rooms, seen) آماده است جز وسطِ حلقهاش: برای دو اتاقِ a و b، اگر حیوانِ p قبلاً در اتاقِ b نبوده و حیوانِ q در اتاقِ a، جابهجایشان کن و با search ادامه بده؛ اگر به نتیجه رسید True برگردان.
با 4 باید complete چاپ شود.
راهنما
کپی بساز تا حالتِ قبلی خراب نشود: new_rooms = rooms[:] و new_seen = [set(s) for s in seen].
بعد new_rooms[a], new_rooms[b] = q, p و new_seen[p].add(b) و new_seen[q].add(a).
یک جواب درست
from itertools import combinations
n = int(input())
def search(rooms, seen):
# rooms[r]: the animal in room r; seen[p]: the rooms animal p has been in
if all(len(s) == n for s in seen):
return True
for a, b in combinations(range(n), 2):
p, q = rooms[a], rooms[b]
if b not in seen[p] and a not in seen[q]:
new_rooms = rooms[:]
new_rooms[a], new_rooms[b] = q, p
new_seen = [set(s) for s in seen]
new_seen[p].add(b)
new_seen[q].add(a)
if search(new_rooms, new_seen):
return True
return False
start_rooms = list(range(n))
start_seen = [{p} for p in range(n)]
print("complete" if search(start_rooms, start_seen) else "not complete")
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن