努力使算法生成益智遊戲板

我正在尋找一個數字益智遊戲。爲了這個問題，我們假設該板是一個由4 x 4個正方形組成的網格。（在實際的益智遊戲中，這個數字將是1..15）努力使算法生成益智遊戲板

一個數字可能只發生在每列一次，每行一次，有點像數獨，但沒有「方塊」。

有效期：

[1, 2, 3, 4 
2, 3, 4, 1 
3, 4, 1, 2 
4, 1, 2, 3]

我似乎無法拿出一個算法，將持續產生有效的，隨機的N×N的主板。

我正在用C＃寫這篇文章。

來源

2011-03-03 abrkn

您已經在4x4的情況下解決了它。正如你所看到的，解決方案不是隨機的。請準確地定義隨機解決方案的含義。 – ThomasMcLeod 2011-03-03 00:58:02

我能想到的最簡單的方法是創建一個局部遊戲並解決它。如果它不可解決，或者如果它是錯誤的，那麼再做一個。 ;-)

來源

2011-03-03 00:51:24 corsiKa

沒有方塊的數獨聽起來有點像數獨。 :)

http://www.codeproject.com/KB/game/sudoku.aspx

有他們使用那裏的車載發電機代碼的解釋。

來源

2011-03-03 00:54:58 Orbit

有沒有太多的組合你需要嘗試。你總是可以重新排列一個有效的棋盤，這樣頂行是1,2,3,4（通過重新映射符號），左列是1,2,3,4（通過重新排列第2到第4行）。在每一行中，其餘3個符號只有6個排列，因此您可以循環查找這216個可能的電路板中的哪一個有效。你可以保存有效的。

然後隨機挑選一塊有效的板子，隨機重新排列這些行，然後隨機重新分配這些符號。

來源

2011-03-03 00:57:47

只是注意到，你會喜歡它，直到15歲。這可能有點乏味。 :) – 2011-03-03 01:01:06

這會迅速停止爲更大的委員會工作，他在他的例子中提到了4x4，但沒有提及實際大小。 – Argote 2011-03-03 01:01:17

他確實說過15 x 15 – Argalatyr 2011-03-03 01:26:33

看來你可以使用這個有效的例子作爲隨機交換兩行隨機數的算法的輸入，然後隨機交換兩個隨機列。

來源

2011-03-03 00:58:29

+1您的解決方案與我的類似（儘管您使用了一些隨機交換，我使用了一個隨機排列）。但我認爲你和我的都不會找到所有有效的安排，請參閱我的答案中的編輯。 – 2011-03-03 15:06:54

退房http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ - 他有幾個謎題，正是這個約束（等等）。

來源

2011-03-03 01:08:21

使用您的第一個有效的例子：

然後，創建隨機2排列中的{1，2，3，4}。

使用第一個置換行，然後使用第二個置換列。

您可以在Knuth的The Art of Computer Programming (TAOCP)，第4卷Fascicle 2，Generating All Tuples and Permutations（2005），v + 128pp中找到創建排列的幾種方法。 ISBN 0-201-85393-0。

如果你不能找到在圖書館的副本，預印本（即討論置換的部分）可在他的網站：fasc2b.ps.gz

編輯 - 修正

的上述解決方案與500-Intenral Server Error相似。但我認爲兩者都不會找到所有有效的安排。

例如他們會發現：

，但不是這一個：需要

一個步驟：重新安排行和列（使用我的還是500的方式）後，創建一個更多的排列（讓我們稱之爲s3）並使用它來排列數組中的所有數字。

s3 = randomPermutation(1 ... n) 
for i=1 to n 
    for j=1 to n 
    array[i,j] = s3(array[i,j])

來源

2011-03-03 01:42:14

我不會說C＃，但下面的算法應該很容易翻譯。

準一組由數字1..N與每個行和列的：

for i = 1 to N 
    row_set[i] = column_set[i] = Set(1 .. N)

然後使通過矩陣單程，從所述一組元件的有效隨機選擇用於每個位置的條目該行和列。刪除從相應的行和列集中選擇的編號。

for r = 1 to N 
    for c = 1 to N 
    k = RandomChoice(Intersection(column_set[c], row_set[r])) 
    puzzle_board[r, c] = k 
    column_set[c] = column_set[c] - k 
    row_set[r] = row_set[r] - k 
    next c 
next r

來源

2011-03-03 01:52:02 librik

開始通過閱讀我的圖着色算法系列：

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

這是要看起來像這樣無關您的問題，而是你做的時候，你會發現它與你的問題有關。

OK，現在你已經讀了，你知道，你可以使用一個圖形着色算法描述一個數獨樣的難題，然後解決這一難題的一個具體實例。但顯然你可以使用相同的算法來生成謎題。

首先定義完全連接的圖形區域。

然後修改算法，以便它試圖找到兩個解決方案。

現在創建一個空白圖並隨機將其中一個區域設置爲隨機顏色。嘗試解決圖表。有兩種解決方案嗎？然後添加另一種隨機顏色。再試一次。有沒有解決方案？然後備份一個步驟並添加一個不同的隨機顏色。

繼續這樣做 - 添加隨機顏色，當你沒有解決方案時回溯，直到你得到一個獨特的解決方案的謎題。你完成了;你有一個隨機的智力發電機。

來源

2011-03-03 03:58:35

我一定會讀這篇文章。 – abrkn 2011-03-04 01:23:50

這將工作，但這種解決方案几乎沒有效率。用這種方式生成15x15圖形不需要多長時間？ – configurator 2011-03-26 20:36:38

@configurator：爲什麼呢？ – 2011-03-26 23:39:07

看起來像你想生成均勻分佈Latin Squares。

這pdf具有由雅各布森和馬修斯的方法的說明（這是在其他地方發表，其中的參考可以在這裏找到：http://designtheory.org/library/encyc/latinsq/z/）

或者你可能預先生成一個人「很多」（在您發貨之前:-)），將其存儲在一個文件中並隨機選擇一個。

希望有所幫助。

來源

2011-03-03 04:12:53

進一步的解決方案是這樣的。假設你有很多解決方案。對於它們中的每一個，只需簡單地置換標識符即可生成新的解決方案（1..15）。這些新的解決方案在邏輯上當然是一樣的，但對於一個玩家來說，他們會顯得不同。

可以通過將初始解決方案中的每個標識符視爲數組中的索引，然後對該數組進行混洗來完成置換。

來源

2011-03-03 06:06:04 Keith

努力使算法生成益智遊戲板

回答

相關問題