連接牆算法

Question

我必須找出一個算法，找到連接牆的遊戲的解決方案。

在連接牆我們有矩形形狀板劃分成相等，正方形單元格。在每個單元格中，我們可以放置一個對角牆（從左上角指向右下角或從左下角指向右上角）。我們必須根據以下規則把牆壁中的所有空的空間：

1. 每個單元都必須包含一個牆
2. 牆壁不能形成閉環（我們不能「砌體」）
3. 連接到支柱必須在支柱
4. 書面 數量相匹配。另外一些細胞中可能含有的牆壁，我們不能移動壁的數目。

Connect the walls online game

請幫助。

編輯：

好的。我設法用C編寫了簡化算法。我需要有人來檢查我。它現在這樣工作：Steps

此外，我有一個關於最後的蠻力步驟的問題。 我可以隨機挑選一個細胞嗎？ （也許有更快的方式） 蠻力算法我的理解：

1. 選擇第一個單元格，並將其標誌/或\
2. 檢查它是否符合支柱的標準，如果沒有周期
3. 如果一切都OK轉到空的相鄰小區，如果不是在先前的細胞 備份和 改變牆壁的方向（如果我們之前沒有做）
4. 循環播放，直到我們將不會對空單元格我們的董事會是對的嗎？

還有一個關於快速循環檢查的問題。 我已經想通了，我可以使用不相交的集合和連接組件的圖形功能。 所以...我們在find-union結構中保持圖的連接組件。 如果新近添加的邊（牆）連接來自同一連接組件的點 - 這是一個循環。

Answer 1

有趣的遊戲。有點像掃雷機。

您是否僅對獲得解決方案感興趣？在這種情況下，這是一個簡單的樹搜索。有點像解決迷宮問題。回溯和東西。由於限制非常嚴格，所以易於修剪子樹。

快捷方式？尋找邊界上的所有「2」支柱。首先填滿他們。還要在角落填充「1」柱。將連接「0」柱的所有牆標記爲不可能的，但標記所有其他方向（因爲所有這些方塊都必須標記）。

然後，對於具有所需數量牆的每個支柱，將所有其他連接牆標記爲不可能，標記所有其他方向。然後用一個不可能的牆將所有其他與「3」柱連接的牆標記出來。標記所有其他牆壁連接到「2」柱子與兩個不可能的牆壁。然後是「1」支柱。循環。

這樣簡化了你的電路板之後，你必須在其餘未指定的牆上進行正常的樹搜索。標記一個潛在的牆，然後再次循環以消除可能性。