1. 問題・条件
問題
大きさがN x Nであるチェス盤上にクイーンN個をお互い攻撃出来ないようにする問題です。
Nが与えられる時、クイーンを置く方法の数を求めるプログラムを書いてください。
入力
Nを入力する。(1 ≤ N < 15)
出力
クイーンN個をお互い攻撃出来ないように置く方法の数を出力する。
2. 説明
N-Queenを解放する前に、チェスでクイーンが攻撃できる場所は、クイーンを基準とした直線上のすべての場所と対角線上のすべての場所を攻撃できる言葉です。
攻撃出来ないように置く方法の数を出す流れは下記のようです。
最初の行に1列クイーンを置きます。
2行目で攻撃されない場所には3、4列があり、3列にまずクイーンを置きます。
3行目で攻撃されない場所がないので、2行目に戻ります。
2行目の4列目にクイーンを置きます。
3行目で攻撃されない場所は2列しかないので2列に置きます。
4行目で攻撃されない列がないので、前のナビゲーションに戻りますが、3行目と2行目に配置できる列をすべて経ってきたので、1行目に戻ります。
最初の行の2列目にクイーンを置きます。
2行目で攻撃されない場所は4列しかないので、4列にクイーンを置きます。
3行目で攻撃されない場所は1列しかないので、1列にクイーンを置きます。
4行目で攻撃されない場所は3列しかないので、3列にクイーンを置きます。 これにより、4つのクイーンがすべて置かれたため、ケースの数をカウントします。
上記と同じ方法で、最初の行のクイーンが4列になるまで繰り返します。
3. 解決方法
クイーンは直線上のすべての馬を攻撃できるため、1行にクイーンは1つだけ入ることができます。 したがって、1 行に 1 つの位置情報しか保存できないため、int arr[n] 形式の 1 次元配列に位置を格納する方式を採用しました。
検査行インデックスは、前の行インデックスより常に大きい。
1と同じ理由で、以前の位置情報と同じ位置情報を入れようとするのはクイーンの直線上に置くことなので、arr[前行インデックス] == arr[検査行インデックス]の場合はスキップします。
以前の位置情報と対角線上に置くことはスキップされます。 対角線上に位置するということは、（以前の馬ｘ座標 - 検査位置ｘ座標）絶対値＝＝（以前の馬ｙ座標 - 検査位置ｙ座標）絶対値という規則があり、2回のルールのため、arr[前行インデックス] - arr[検査行インデックス]の絶対値 == 検査行インデックス - 前行インデックスという式で検査します。
4. 코드
import java.util.Scanner;
class Main {
static int count = 0;
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] col = new int[n]; // 각 행에 위치할 퀸의 위치 정보를 저장할 배열
for(int i=0;i<n;i++) {
col[0] = i;
nqueen(0,col);
}
System.out.println(count);
input.close();
}
public static boolean rule(int index, int col[]) {
int k = 0;
while(k < index) {
if(col[k] == col[index] || Math.abs(col[k] - col[index]) == index - k) {
return false;
}
k++;
}
return true;
}
public static void nqueen(int index, int[] col) {
if(rule(index,col)) {
if(index == col.length-1) {
count++;
}
else {
for(int i=0;i<col.length;i++) {
col[index + 1] = i;
nqueen(index+1,col);
}
}
}
}
}
Comments