這個圖能夠一筆畫完嗎？

要求一筆畫完全部灰色方塊，藍色方塊是起點且不可重複經過，灰色方塊不可重複經過，紅色方塊不可經過。

---

不能

如圖，對格子進行黑白染色，可走的格子中，黑色共20個，未染色（簡稱白色）共21個

因此若想要走完全部41個格子，必須按照白黑白黑……白黑白的順序來走，但是指定的起點是黑格子，因此不可能走出

=============以上發表於2014-05-31 23:22===============

有人在評論中詢問[「起點顏色的格子總數僅比另一種顏色的格子總數多一或相等」，這是否為存在無重路徑的充要條件？]

答：不是，例如此圖：

---

搞定~~

反正也沒有說不能出界~~

---

所用工具叫Mathematica，版本10.4.0，這個叫漢密山爾頓路徑問題，從3號出發是不行的，

可以看到給3號留一條邊程序不給出任何一解

g = EdgeDelete[
VertexDelete[
GridGraph[{8, 6},
VertexCoordinates -&> GraphEmbedding[GridGraph[{8, 6}]],
VertexSize -&> Large, VertexShapeFunction -&> "Square",
VertexLabels -&> "Name"], {8, 10, 23, 25, 26, 27,
46}], #] /@ {{3 &<-&> 2, 3 &<-&> 11}, {3 &<-&> 2,
3 &<-&> 4}, {3 &<-&> 4, 3 &<-&> 11}};
FindHamiltonianPath /@ g


{{}, {}, {}}

從45號出發倒是找到一條路徑

g = VertexDelete[
GridGraph[{8, 6},
VertexCoordinates -&> GraphEmbedding[GridGraph[{8, 6}]],
VertexSize -&> Large, VertexShapeFunction -&> "Square",
VertexLabels -&> "Name"], {8, 10, 23, 25, 26, 27, 46}]
path = FindHamiltonianPath@g


下面那個列表是經過的頂點順序

---

原理跟

差不多

---

推薦閱讀：