2014-03-05 40 views
-1

我想創建一個程序,打印出n皇后問題的所有解決方案1 <= n <= 13。該程序將從命令行讀取一個整數n,指示要解決的Queens問題的大小。例如,如果n = 5它會打印出功能檢查,如果沒有兩件在同一對角線(爪哇)

(1, 3, 5, 2, 4) 
(1, 4, 2, 5, 3) 
(2, 4, 1, 3, 5) 
(2, 5, 3, 1, 4) 
(3, 1, 4, 2, 5) 
(3, 5, 2, 4, 1) 
(4, 1, 3, 5, 2) 

(4, 2, 5, 3, 1) 
(5, 2, 4, 1, 3) 
(5, 3, 1, 4, 2) 

目前,我只是停留在我的程序的一個功能。我需要創建一個方法,如果(A [1],A [2],A [3],...,A [n])所表示的置換不在棋子上放置兩個皇后(棋子),它將返回true相同的對角線,否則返回false。要檢查(A [i],i)和(A [j],j)上的兩個皇后是否位於同一對角線上,我需要檢查水平距離是否與它們的垂直距離相同。

該函數被稱爲isSolution()並且應該最多比較每對皇后一次。如果在同一對角線上找到一對,則不要進行進一步比較並返回錯誤。如果所有n(n-1)/2比較均未發現對角攻擊,則返回true。

static boolean isSolution(int[] A){ 
    blah blah blah 
} 

我已經有一個產生一組的所有排列字母排序的功能,它的最終置換到原來的狀態。

isSolution()函數的內容是什麼?我非常失落,任何事情都會有所幫助,甚至僞代碼概述了isSolution()的主體。

我知道的事情:ij是兩件之間的水平和垂直距離。我需要製作一對for循環,以便通過每個n(n-1)/2比較。 「i」和「j」應該分別是數組索引和數組元素之間的差異。我也需要使用Math.abs來區別安全。所以在for循環中,初始化爲ij作爲我提到的差異,然後設置一個if檢查if i==j返回false。如果進行了所有比較,並且不返回false,則返回true。

+0

在「我知道的事情」之後,你似乎有一個試圖解決問題的輪廓。你是否嘗試爲此編寫代碼?你是否通過一個例子來看看它是否會起作用? – Dukeling

回答

0

(y1-y2)/(x1-x2)是1或-1,如果X1,Y1和X2,Y2是對角線

它基本上是兩個座標

+1

,它相當於'abs(y1-y2)== abs(x1-x2)'。這種形式更明確地與x軸距離等於y軸距離的事實相關。 (並避免劃分,漂浮等...) –

3

之間線的角度的抑制測試表達,所述水平和垂直距離是相等的,

Abs(A[J] - A[I]) == Abs(J - I) 

你會嘗試每一個不同的(I, J)對。如果你確定I < J,第二Abs是不必要的。

0

有一個稍微更有效的解決方案:

初始化一個數組D[-n+1..+n-1]所有false,然後D[A[i] - i]設置所有條目true。如果發現某個條目已經是true,則檢測到對齊。 (D標記每個對角線的佔用情況。)

對另一個對角線方向(使用D[0..2n-2])對D[A[i] + i]重複此操作。

這是O(n)

在13x13棋盤上,這將需要25個清除,然後13個測試和設置,兩次(按位執行可能是有益的)。與「對」解決方案進行比較,該解決方案需要花費78次對準測試的評估。

0

2元件是在相同的對角線,如果他們的和或差是相同的或MOD差相同

如果A1(I,J)和B1(K,L)是該元素的位置: 如果| LJ | = | i-k |它們在同一條對角線上

另一種方法是檢查i + j = l + k向上對角線,如/或i-j = k-l - 向下對角線像\ - 如果您需要方向。