Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money

N Queen problem

Problem analysis

• Place n queens on a board of n×n squares that are impervious to each other. According to the rules of chess, the queen may attack a piece that is on the same row or column or slash as her. The n post problem is equivalent to placing n queens on an n-by-n checkerboard, and any 2 queens are not on the same row or column or slash.

• X [I] indicates that queen I is placed in the x[I] column of row I of the board

  • It can’t be on the same line
  • X [I] cannot be different in the same column
  • Can’t be on the same slash
    • The slope of 1 is equal to the value
    • The slope is negative 1 and the difference is the same
    • If there are two points (I, j) (k, L), then there are
      • i – j = k – l => i – k = j – l
      • i + j = k + l => i – k = l -j
    • The | | | = | j – I – k l was set up

Java source code

/* * * like dust */
package nqueen;

/** * n queen problem *@author ruochen
 * @version1.0 * /
public class NQueen {

	/** Number of queens */
	static int n;
	/** The current solution */
	static int[] x;
	/** Number of viable options */ when the money has been found
	static long sum;
	
	public static void main(String[] args) {
		nQueen(5);
		System.out.println("The number of feasible schemes is:" + sum);
	}
	
	/** * Initialize and return the number of possible solutions *@returnNumber of possible solutions */
	public static long nQueen(int nn) {
		n = nn;
		sum = 0;
		x = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			/ / initialization
			x[i] = 0;
		}
		backTrack(1);
		return sum;
	}
	
	/** * Feasibility constraints *@param k
	 * @returnIs it feasible */
	public static boolean place(int k) {
		
		for (int j = 1; j < k; j++) {
			/ / the corresponding formula | | | = | j - I - k l && column number cannot be the same
			if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || x[j] == x[k]) return false;
		}
		return true;
	}
	
	/** * backtrace search *@param i
	 */
	public static void backTrack(int t) {
		if (t > n) {
			// A feasible solution has been found
			long temp = sum + 1;
			System.out.print("The first" + temp + "The feasible solutions are:");
			for (int k = 1; k <= n; k++) {
				System.out.print(x[k] + "");
			}
			System.out.println();
			sum++;
		} else {
			for (int i = 1; i <= n; i++) {
				x[t] = i;
				if (place(t)) backTrack(t + 1); }}}}Copy the code

The first feasible solution is: 1 3 5 2 4 The second feasible solution is: 1 4 2 5 3 The third feasible solution is: 2 4 1 3 5 The fourth feasible solution is: 2 5 3 1 4 The fifth feasible solution is: 3 1 4 2 5 the sixth feasible solution is: The seventh feasible solution is: 4 1 3 5 2 The eighth feasible solution is: 4 2 5 3 1 The ninth feasible solution is: 5 2 4 1 3 The tenth feasible solution is: 5 3 1 4 2 The number of feasible solutions is: 10Copy the code

Finally, welcome to pay attention to my personal wechat public account “Little Ape Ruochen”, get more IT technology, dry goods knowledge, hot news