1

注意: NQueens の問題を好きなように変更するように依頼されました。私はこの方法を考え、それを実行したいと考えています。これは宿題の直接的な質問ではなく、自分の変更をどのように実装するかという問題です。

以下に、4 つのクイーンを解決するコードを書きました。したがって、このコードによれば、2 つのクイーンが同じ行、同じ列、同じ対角線にあることはできず、攻撃しないようになっています。クイーンを配置すると、同じ列に配置できますが2行をスキップし、同じ行に2列をスキップして配置でき、同様に2列をスキップして同じ対角線に配置できるように変更しようとしています行と 2 つの列。

つまり、簡単に言えば、クイーンは同じ行、同じ列、同じ対角線に 2 つのブロックをスキップして配置できます。

4 つのクィーンの場合、現在の出力は次のようになります。

* Q * *
* * * Q
Q * * *
* * Q *

* * Q *
Q * * *
* * * Q
* Q * *

ただし、次の出力も得られるはずです。

Q * * Q
* * * *
* * * *
Q * * Q

ここでは、水平、垂直、斜めに 2 ブロックごとにクイーンが配置されています。

コード:

import java.util.*;

public class Queens {

/***************************************…
* Return true if queen placement q[n] does not conflict with
* other queens q[0] through q[n-1]
****************************************/
public static boolean isConsistent(int[] q, int n) {
for (int i = 0; i < n; i++) {
if (q[i] == q[n]) return false; // same column
if ((q[i] - q[n]) == (n - i)) return false; // same major diagonal
if ((q[n] - q[i]) == (n - i)) return false; // same minor diagonal
}
return true;
}

/***************************************…
* Print out N-by-N placement of queens from permutation q in ASCII.
****************************************/
public static void printQueens(int[] q) {
int N = q.length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (q[i] == j) System.out.print("Q ");
else System.out.print("* ");
}
System.out.println();
} 
System.out.println();
}


/***************************************…
* Try all permutations using backtracking
****************************************/
public static void enumerate(int N) {
int[] a = new int[N];
enumerate(a, 0);
}

public static void enumerate(int[] q, int n) {
int N = q.length;
if (n == N) printQueens(q);
else {
for (int i = 0; i < N; i++) {
q[n] = i;
if (isConsistent(q, n)) enumerate(q, n+1);
}
}
} 


public static void main(String[] args) {

enumerate(4);
}

}

私は何を間違っていますか?変更で動作するようにコードを変更するにはどうすればよいですか?

4

1 に答える 1