提供一個電腦能理解的思路吧。
抓貓的時候，和這個貓之前的生活毫無關系，只和這只貓現在有可能在哪兒有關。開哪個門，決定了這只貓明天可能在哪兒。只要你可以不斷壓縮這個可能性，最後壓縮到一個門裏，這問題就解決了。
最開始的時候，這只貓的可能性是1 2 3 4 5 6 7。
如果抓1號門，確定了它不在1，那接下來一天它的可能性還是1 2 3 4 5 6 7。所以這一下是沒意義的。因為貓可以從3到2。
如果抓2號門，確定了它不在2，那接下來一天它的可能性就變成了2 3 4 5 6 7。因為它不在2，所以沒辦法跑到1去。這就壓縮了可能性。
第二天如果抓2，那結果還是2 3 4 5 6 7，毫無進展，所以沒意義。
抓3，結果會變成1 3 4 5 6 7，變個形式，給接下來的一天提供方便。
第三天，抓4，可以確保接下來一天沒有3，然後可能性變成2 4 5 6 7。以此類推，最後就能把門數減少到1個。核心技巧就是如果有一個門，它左邊不可能右邊可能，抓右邊，這樣這個門下次就不可能了。
當然怎麽抓更快這是人類的思路，這個演算法有個好處就是對於電腦來說足夠暴力。你並不需要去教電腦應該抓哪個門，你讓它全抓了然後剪枝加BFS即可。由於結果只和當前狀態有關，所以最多出現
2^n
種可能性，可以有效地剪枝，避免無限深度。配合BFS，總可以最快速度地找到最優解。
import
queue
class
Solution
:
def
__init__
(
self
,
doors
,
path
=
[],
possible
=
set
()):
self
.
path
=
path
self
.
possible
=
possible
self
.
doors
=
doors
def
generate_next_steps
(
self
):
if
not
self
.
possible
:
return
None
next_steps
=
[]
for
i
in
self
.
possible
:
path
=
self
.
path
+
[
i
]
possible
=
set
()
for
elem
in
self
.
possible
:
if
elem
!=
i
:
if
elem
-
1
>=
1
:
possible
.
add
(
elem
-
1
)
if
elem
+
1
<=
self
.
doors
:
possible
.
add
(
elem
+
1
)
s
=
Solution
(
doors
=
self
.
doors
,
path
=
path
,
possible
=
possible
)
next_steps
.
append
(
s
)
return
next_steps
def
find_cat
(
n
):
checked_combination
=
set
()
solutions_queue
=
queue
.
Queue
()
solutions_queue
.
put
(
Solution
(
doors
=
n
,
path
=
[],
possible
=
set
(
i
for
i
in
range
(
1
,
n
+
1
))))
while
True
:
s
=
solutions_queue
.
get
()
next_steps
=
s
.
generate_next_steps
()
if
next_steps
is
None
:
return
s
.
path
for
n
in
next_steps
:
if
tuple
(
n
.
possible
)
not
in
checked_combination
:
checked_combination
.
add
(
tuple
(
n
.
possible
))
solutions_queue
.
put
(
n
)
print
(
find_cat
(
7
))
這裏提供一個隨手寫的程式碼，核心思路就是上面說的，對於每種可能性，分別測試開其中某扇門之後的結果，然後剪去已經試過的狀態，BFS。
python find_cat.py
[2, 3, 4, 5, 6, 2, 3, 4, 5, 6]
