前幾天遇到這樣一道數學題：

用四種不同顏色給三棱柱六個頂點涂色,要求每個點涂一種顏色,且每條棱的兩個端點涂不同顏色,則不同的涂色方法有多少種？

當我看完題目后，頓時不知所措。于是我拿起草稿紙在一旁漫無目的地演算了一下，企圖能找到解決方法。結果一無所獲。于是打算通過程序算法解決這個問題。經過2個多小時的研究，終于完成了代碼，并求得了答案。

由于Python寫起來比較方便而且本人比較喜歡Python的語法，所以研究算法時我通常采用Python，此次也不例外。以下就是整個算法的實現過程。

兩種算法

我一共想出了兩種用于解決本題的算法：

??? 算法一： 將所有的涂色情況通過程序的循環計算出來，然后通過程序的條件判斷去除掉不合題意的所有情況，最后得到最終結果。

??? 算法二： 從其中任意一個端點（p0）入手，由于其它所有端點都沒有涂色，所以它可以涂四種顏色。將這四種顏色通過循環分別涂在這個端點上，每涂上一種顏色后，獲取與它相臨的一個端點（p1），并獲取它可以涂上的顏色，然后通過循環將可用顏色涂上（及不能涂上與p0相同的顏色），每涂上一種顏色，又將p1相鄰的未涂色的點涂色（及除p0外其他的相鄰端點）。每個點被涂色后都采用同樣的方法將相鄰的點涂色，以此類推，涂完最后一個點，就記一次情況。所有的遞歸都完成后，就獲得了所有情況。

算法一很直接很粗暴，所以我采用了算法二來解決上述問題。接下來就是具體的代碼了。

算法實現

我寫了大約90行Python代碼來實現這個算法：

            
colorList = [0, 1, 2, 3]
pointList = []
amount = 0


class Point(object):
  def __init__(self):
    super(Point, self).__init__()

    self.neibors = []
    self.color = None

  def paint(self, c):
    self.color = c

  def clean(self):
    self.color = None

  def getLeftOverColors(self):
    copyOfColorList = colorList[0 : 4]

    for neibor in self.neibors:
      nc = neibor.color

      if nc in copyOfColorList:
        copyOfColorList.remove(nc)

    return copyOfColorList


def main():
  global pointList

  p0 = Point()
  p1 = Point()
  p2 = Point()
  p3 = Point()
  p4 = Point()
  p5 = Point()

  p0.neibors = [p1, p2, p4]
  p1.neibors = [p0, p2, p5]
  p2.neibors = [p0, p1, p3]
  p3.neibors = [p2, p4, p5]
  p4.neibors = [p0, p3, p5]
  p5.neibors = [p4, p3, p1]

  pointList = [p0, p1, p2, p3, p4, p5]

  paintPoint(p0)

  print(amount)

def paintPoint(p):
  global amount

  colors = p.getLeftOverColors()
  lastOne = isLastOne()

  for c in colors:
    p.paint(c)

    if lastOne:
      amount += 1
    else:
      for currentNeibor in p.neibors:
        if currentNeibor.color == None:
          paintPoint(currentNeibor)

          break

  p.clean()

def isLastOne():
  global pointList

  paintedNum = 0

  for p in pointList:
    if p.color != None:
      paintedNum += 1

  return paintedNum == 5


if __name__ == "__main__":
  main() 
          

以下是對各段代碼的介紹。

全局變量

??? colorList： 顏色列表

??? pointList： 存放六個點的列表

??? amount : 涂色方案的種數

Point類

用于儲存各個點的信息，如點的顏色（color屬性，None代表無顏色）、相鄰的點（'neibors'屬性）。以及提供 paint 方法用于將點標記顏色； clean 方法用于去除顏色； getLeftOverColors 方法用于獲取可用顏色，及獲取相鄰點沒有使用的顏色。

main函數

程序開始運行時調用的函數，其中構造了所需的六個點，以及分別為這六個點明確了相鄰的三個點。注意，由于這里的點只有相鄰和不相鄰的位置關系，所以不需要在意這些點到底在三棱柱里對應哪個位置，任意設定這些點的位置對結果來說并沒有影響，只需注意它們之間的相鄰關系即可。

isLastOne函數

判斷是不是最后一個未涂色的點。

paintPoint函數

用于對作為參數傳入的點進行著色。其中首先通過調用該點的 getLeftOverColors 方法獲取可用顏色，然后按照上文算法中介紹的，通過遍歷可用顏色列表，為該點著色，如果該點不是最后一個點（通過 isLastOne 函數判斷），就遞歸調用 paintPoint 函數為相鄰的一個未著色的點著色，如果是，則將記下一次涂色方案。

運行代碼，得到結果 - 264：

Ok，于是這道題就在我們的計算機的幫助下，被成功解決掉了～如果大家有更好的方案解決這一算法問題，歡迎留言進行交流～希望本文對大家學習Python和計數原理都能有所幫助。