如何判斷一個三維正方形是否爲拉丁方格

我需要設計一個算法，告訴給定的整數矩陣是否爲有效的拉丁方格。我之前從未和拉丁廣場合作過，所以我不知道從哪裏開始。經過一番研究，我只找到寫拉丁方塊的算法。唯一發生在我身上的是所有列和行的總和應該是相同的，但是如果它在同一行和列中重複，我必須檢查每個數字。這樣做該計劃將有很大的時間成本。我正在使用C++。如何判斷一個三維正方形是否爲拉丁方格

來源

2013-04-26 Buradi

您能告訴我們「大時間成本」版本嗎？那會給我們一些幫助。 – 2013-04-26 16:51:35

我們所能爲您做的就是Google的答案 - 您可以自己做的事情。如果沒有適當的代碼來幫助你解決問題，那麼沒有其他的答案。 – 2013-04-26 16:51:40

你沒有努力提出一個合適的問題：請提供你迄今爲止的嘗試，以及你期望的結果。 – Escualo 2013-04-26 17:40:46

這樣做，程序會有很大的時間成本。

不，因爲您可以在到達結尾之前拒絕很多矩陣。所以算法會快速失敗。工作算法的最差估計是O(n*(n+1))（我假設你只評估維數爲n * n的方陣）。但平均算法會好得多 - 因爲它會在找到第一個相等的情況下失敗。

更新： 平均複雜度可以粗略和近似估計爲實數拉丁方的數量與可能的平方數。要做到這一點，我們需要引入瞭解normalized廣場。兩個方形波紋管直觀上是相同的：

[ 1 2  [5 7 
    2 1 ]  7 5]

所以正常化這一點，我們可以使用替換爲數字1 ... N * N平方的n個。所以第一種形式獲勝。

正火廣場Wiki provides an estimation enter image description here

你害怕嗎？但平均而言，我們還需要將此公式除以矩陣總數。要做到這一點，請參閱此公式http://en.wikipedia.org/wiki/Combination

來源

2013-04-26 16:57:40 Dewfy

好的，但我的問題是什麼是平均算法，因爲我一直在谷歌搜索幾個小時甚至關於數獨，我仍然不知道該算法的原理 – Buradi 2013-04-26 17:08:02

@Buradi看到我的更新 – Dewfy 2013-04-26 17:38:17

如何判斷一個三維正方形是否爲拉丁方格

回答

相關問題