序言中的謎語

Question

首先我沒有這個謎語的真名，它簡直就是「ABC」。

在開始時他們給我的大小板（nxm）和n，m =（1,10）和一個字母，例如C，所以我可以在ma解決方案中只用字母A到C.
然後我得到一些形式爲（i，j，k）的三分，我< = n，j < = m和k屬於（A，C）。

例如板它一開始是這樣的：
Example board

對每一個空盒子，我必須以這樣的方式鍵入字母A，B，C，當我打完字，它們必須滿足以下條件：

• 如果在一個行（列）是不同的字母，每個字母的此行中出現（列）相同的次數
• 至少一行（列）中的所有字母都一樣。

你有任何想法如何解決這類謎語？
也許這個難題有它自己的名字，我可以在某處讀到它嗎？

編輯： 我必須從文件中讀取的所有數據。此文件如下所示：

4. 4. 'C'。 （3,1，'B'），（4,1，'A'），（1,2，'B'），（4,2，'C'），（1,3' ），（2,4，'A'）]。

小正確：在只有一行或一列所有字母都是一樣的，不同時。 解決方案我的例子是：

B A B A 
B C B C 
C C C C 
C A C A 

Answer 1

您所描述的問題可以被看作是一種限制問題上的字母有限域。你的變量表示棋盤上的位置，所以你將有n * m個這樣的值。每個變量的範圍在可能值的有限範圍內，由用戶提供的字母表示。最後，用戶輸入的三元組和解決方案要滿足的條件是約束條件。

要實現了有限域不同的工具和庫約束編程都可以使用，例如，SWI-Prolog有clpfd庫。

Answer 2

我想@KarolyHorvath想給大家分享的是如何與你試圖解決這個爲自己的任何想法在Prolog中表示板，在一起。在下面我將使用列表表示的列表，內部列表是行和它們的項目符號或原子（單個小寫字母，以保持簡單）。

的問題在某種意義上拉丁方，這需要準確的每個符號之一，在每一行和每一列的推廣。用一個只包含一些新符號的新行和列來拉丁廣場，拉丁廣場中沒有顯示，並且您將有滿足您問題要求的解決方案。

也就是說，你的問題涉及到一個部分完成的矩形板，不一定是方形的，並且符號頻率可以在行到列和列到列之間變化。

對於像Example Board這樣的小型電路板，3x3陣列，蠻力方法是誘人的。但是有一些簡單的事情可以編碼，以保持搜索效率。

某些行和某些列必須是「常量」，即它們只能包含一個字母。我想我會把它作爲搜索樹的最高選擇，即選擇一個可以是單個字母的行和列。請注意，由於每一行都與每一列相交，因此我們將對該行和列使用相同的字母。

但在開始搜索解決方案之前，您需要輸入表示包含「給定」條目的電路板的數據。使用你自己對此的判斷，但是對於合理大小的板子，你可能會要求用戶輸入行數和列數，然後逐行提示它們。

請記住，Prolog術語讀者希望輸入被句點終止。所以輸入可能工作是這樣的：

Enter a list of all letters: [a,b,c]. 
How many rows? 4. 
How many cols? 4. 
Enter a row as a list: [_,_,b,a]. 
Enter a row as a list: [b,_,_,c]. 
Enter a row as a list: [c,_,_,_]. 
Enter a row as a list: [_,a,_,_]. 

下劃線作爲輸入匿名變量和葉代表董事會作爲自由變量列表中的條目對應的列表。

可以因此與代表你的程序中的所有字母的列表：

Symbols = [a,b,c] 

，並用列表的列表中的板可能看起來像：

Board = [[A1,A2,b,a],[b,B2,B3,c],[c,C2,C3,C4],[D1,a,D3,D4]] 

在具體的例子有隻是將所有行和列設置爲相同字母的一種可能方式，並且通過使第二列和最後一行都具有所有a：

Board = [[A1,a,b,a],[b,a,B3,c],[c,a,C3,C4],[a,a,a,a]] 

但是現在我們發現尋找解決方案的方法會陷入盲目。第二行有三個字母，但是在四行中，三個字母不可能出現相同的次數。這個例子沒有解決方案。

然而，「無解」結果非常有效。

希望這給你一些關於如何在Prolog中編寫一般求解過程的想法。