Python迭代器Quarto遊戲板的獨特安排

Question

我正在研究涉及棋盤遊戲Quarto的組合問題的編程解決方案。在Quarto中有十六件，每件都有四個二元屬性。這意味着我們可以將每個元素表示爲一個元組（i，j，k，l），其中每個元素爲零或一個元素。爲了解決我的問題，我需要重複每種獨特的方式，以便在4x4的棋盤上安排全部棋子。我可以做類似

from itertools import permutations 
for board_orientation in permutations(pieces, 16): 
    do_stuff(board_orientation) #takes 1 or 2 full seconds 

但是這將意味着16！ （超過20萬億次）迭代。爲了避免這種情況，我試圖創建一個只產生獨特板面方向的發生器 - 即在一個或多個屬性（前兩個屬性由二面角組D4描述）的旋轉，反射和反轉下具有唯一性的方向。我發現了Tic-Tac-Toe的一個類似問題，但我在如何將它擴展到這個更復雜的迭代問題上掙扎。

我認爲解決方案涉及通過散列樹將每個板子方向映射到數值，然後看看數字在各種對稱操作下如何變化，但努力將其轉換爲代碼。

Answer 1

一個電路板通過應用反轉與16個電路板「同構」，並且通過應用旋轉和鏡像至多8個電路板。這是一組同構板最多16 * 8 = 128。至少有15/8（1.6 * 10^11）電路板配置。

使用反轉可以將每塊電路板「轉換」爲一個電路板，左上角爲0。固定一個角落覆蓋除了通過左上角（和右下角）的對角線上的鏡像之外的所有對稱。 通過選擇對稱性上的兩個「相反」字段（如（1,2）和（2， 1）），並要求其中一個值更小（例如B [1,2] < B [2,1]）。這意味着如果B [1,2]> B [2,1]比 執行對角線鏡像。以所描述的方式變換的板可以由15個十六進制數字字符串編碼（左上角字段總是0）。通過左上角調用該編碼標準化。

以同樣的方式，一個電路板可以被其他角落標準化。一塊電路板有4個轉角歸一化，讓電話板ID最小化這些歸一化。該ID唯一編碼等軸測板組。

現在很好的部分:-)，不需要在配置生成過程中存儲生成的ID。以一個角標準化形式（例如，左上角）按字典順序生成棋盤就足夠了， 計算其他三個標準化，並且如果其他三個標準化中的任何一個比生成的標準化低於我們已經通過該配置。這是由於配置按照字典順序生成的。

注意：可以通過檢查創建板過程中的規範化值來優化代碼，而不是創建整個板並執行上面的檢查。類似地，如果第二個角的歸一化必須小於左上角的歸一化（僅檢查前綴），則填充兩個有序的字段（（1,2），（2,1）），而不是填充其它角的兩個有序字段兩個領域），而不需要進一步產生。對於該編碼必須有有序的字段作爲前兩位數字。擴展是接下來填充第三個角落字段，執行檢查，比第四個角落字段並執行檢查。