質問する

N-Queen問題の大きさはN× これは,N個のチェス盤上のN個の皇后が互いに攻撃し合うことができない問題である.
Nが与えられた場合,解放後の方法の数を計算するプログラムを作成してください.

入力

1行目はNです.(1 ≤ N < 15)

しゅつりょく

1行目でN個の皇后が互いに攻撃できない場合は、数字を出力します.

に答える

この問題は他人の解答を参照してください.
まず皇后の移動位置を決めなければなりません.->上、下、左、右、対角線
問題では,NxNチェス盤にN個のクイーンがいれば数の問題を求めることができる.
そのため、皇后が移動する範囲内では、他の皇后はいられない.
再帰呼び出し関数により,ケースの数を求め,返す条件がN個であれば返す,それ以外に再帰呼び出しをすればよい.
コール時には、皇后の移動範囲を除いて、他の皇后を置くことができる場合にのみコールすることが条件です.
すなわち,皇后を解放できるか否かを判別する関数が必要である.
1次元配列を使用して配列を表すインデックスが열配列の値(要素)が행です.
カラム(col)値を受信し、まずカラム内のローが存在するか否かを判断する.存在する場合はfalse returnが存在しないと判断し、対角線範囲内に置いてもよいか否かを判断する.対角線範囲に入るとfalseは残りtrueを返します.

ソース

import java.util.*;

public class Main {
	public static int[] arr;
	public static int n;
	public static int count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		arr = new int[n];

		nQueen(0);
		System.out.println(count);

	}

	public static void nQueen(int depth) {
		if (depth == n) {
			count += 1;
			return;
		}

		for (int i = 0; i < n; i++) {
			arr[depth] = i;

			if (possible(depth)) {
				nQueen(depth + 1);
			}
		}
	}

	public static boolean possible(int col) {
		for (int i = 0; i < col; i++) {
			if (arr[col] == arr[i]) {

				return false;
			} else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
				return false;
			}
		}

		return true;
	}
}