如何生成5x5數獨拼圖？

Question

我已經寫出算法來生成5x5數獨謎題。下面是它的工作原理。 在我的5x5數獨中只有兩個限制。每行和每列只能有一種項目。

1. 生成隨機位置（0,4）

2. 如果位置被填充回去1.

3. 生成隨機數（1,5）

4. 如果有已將此行數或列數回到3.

5. 用數字填充位置

6. 如果有空位可返回1.

7. 刪除隨機數字。

有兩個主要問題。

1. 該算法產生死鎖，所以我檢查嘗試，如果有超過10次嘗試填充位置，我重置所有事情，然後再試一次。

2. 它太慢了。由於我正在爲移動設備設計我的數獨，因此我需要優化它。 我的聯繫5需要長達五秒鐘，舊三星銀河系統最多需要兩分鐘。

Answer 1

您可以替換通過與已知的有效填充格開始，然後應用轉換它，保持完好的約束步驟1-6。

1 2 3 4 5 
2 3 4 5 1 
3 4 5 1 2 
4 5 1 2 3 
5 1 2 3 4 

然後，如果你交換兩行，你仍然有一個有效的網格，例如：

例如，你可以用這個網格，這是很容易通過設置grid[i][j]到((i + j) % 5) + 1產生開始換行1和3：

1 2 3 4 5 
4 5 1 2 3 < 
3 4 5 1 2 
2 3 4 5 1 < 
5 1 2 3 4 

您也可以交換兩列，仍然有效的格結尾，例如，交換列2和4：

1 2 5 4 3 
4 5 3 2 1 
3 4 2 1 5 
2 3 1 5 4 
5 1 4 3 2 
    ^^

所以只要與常規電網啓動，然後在一個循環內生成一對隨機行和隨機列對，然後交換它們。您也可以交換數字，（例如，將所有5s更改爲3s，反之亦然）。你總是會得到一個有效的結果。

然後你可以移動到第7步。

然而，第7步是比它更復雜看來，因爲你需要你的困惑是solveable。換句話說，在每一點上，玩家都應該可以邏輯推斷至少一個單元格的值而不用猜測。

因此，您需要編寫一個函數，使用約束條件（您只需要列出所有不存在於同一行或列中的值）來計算空單元格的有效值列表。當在步驟7除去號碼，在一個循環內：

• 選擇隨機細胞
• 計算用於基於所述其他非空單元格在柵格
• 該小區的有效可能值是否有隻有一個可能的值（單元格中的值），那麼你可以刪除它

單元格的值可以推斷出來的另一種方式是，如果它是其行或列中唯一的單元格，其中可能的值。爲了驗證這一點，您需要計算單元格所在行或列中每個單元格的有效值列表（不存在於同一行或列中的其他非空單元格中的值），即使單元格包含多個可能的值，如果它是其行中唯一包含該值的單元格或列中唯一的單元格，則可以確定該值，因此可以將其刪除。

您可以重複此操作，直到刪除了所需數量的單元格爲止。因爲你移除的每個單元格在被移除時都能夠被推導出來（因爲它是單元格一旦變空的唯一可能的值），那麼玩家應該能夠通過將值添加回來解決這個難題與之相反的順序。

如果這不會產生「有趣」的謎題，那麼你可以採取「作弊」的方法，這是有一個現有的手工製作謎題的數據庫，然後選擇一個並隨機交換行和列或交換數字。這可能會有一些版權問題作爲「衍生作品」，但這不是一個編程問題。