In this assignment you will write a java program that finds all solutions to the n-Queens problem, for . Essentially, the program will ask the user for n amounts of queens and find all the solutions for that number (n). Highest number that will be required is just 8 so (92 solutions). Important factors that are going to be in consideration is just using the 4 methods that are in bold.

The Eight Queens puzzle is to find a palceent of 8 queens on an otherwise empty 8x8 chessboard in such a way that no two queens confort each ther. One solution to this problem is pictured below.

The n-Queens problem is the natural generalization of placing n queens on an n?n chessboard so that no two queens lie on the same row, column or diagonal. There are many ways of solving this problem. Our approach will be to start with a solution to the n-rooks problem (i.e. place n Rooks on an n ? n chessboard so that no two rooks attack each other) then check if that arrangement is also a solution to n-Queens. The rook move in chess is similar to the queen's move except that it cannot move diagonally.

Solutions to the n-Rooks problem are easy to find since one need only position the rooks so that no two are on the same row and no two are on the same column. Since there are n rows and n columns to choose from, solutions abound.

A natural way to encode solutions to n-Rooks is as permutations of the integers {1, 2, 3, ..., n}. A permutation of a set is an ordered arrangement of the elements in that set. If we number the rows and columns of the n ? n chessboard using the integers 1 through n, each square is then labeled by a unique pair of coordinates (i, j) indicating the square in row i and column j. The permutation (a(1), a(2),a(3) ?,a(N) ) corresponds to the placement of a piece on the square with coordinates ( a(j) , j ) for . For instance, the permutations (2,7,8,5,1,4,6,3) and (2,4,6,8,3,1,7,5) correspond to two the 8-Rooks solutions pictured below. In general, any solution to the n-Queens problem is also a solution to n-Rooks, but the converse is false. Not every solution to n-Rooks is a solution to n-Queens.

Your program will generate all solutions to n-Rooks by systematically producing all permutations of the set {1, 2, 3, ..., n}. It will check each n-Rooks solution for diagonal attacks to see if the given permutation also solves n-Queens. Whenever an n-Queens solution is found, your program will print out the permutation, then move on to the next permutation. Thus when n = 8 , ( 2, 4, 6, 8, 3, 1, 7, 5 ) would be printed while (2,7,8,5,1,4,6,3) would not.

We will represent a permutation (a1, a2, a3,?, an ) of the set {1, 2, 3, ..., n} by an array A[ ] of length n+1, whereA[ j ]= a( j ) for , and the element A[0] is simply not used. Your program will include a function with the following heading.

static void nextPermutation (int [ ] A) {. . . . . .}

This method will alter its argument A by advancing ( A[1], A[2], A[3], ?, A[n] ) to the next permutation in the lexicographic ordering. If ( A[1], A[2], A[3], ?, A[n] ) is already at the end of the sequence, the function will reset A to the initial permutation (1, 2, 3 , ? , n ) in the lexicographic order. The pseudo-code below gives an outline for the body of nextPermutation().

Program will also include another function with the following heading.

static boolean isSolution(int[] A){. . .} This method will return true if the permutation represented by ( A[1], A[2], A[3], ?, A[n] ) places no two queens on the same diagonal, and will return false otherwise. To check if two queens at ( A[ i ], i ) and ( A[ j ], j ) lie on the same diagonal, it is sufficient to check whether their horizontal distance apart is the same as their vertical distance apart.

Function isSolution() will compare each pair of queens at most once. If a pair is found on the same diagonal, do no further comparisons and return false. If all n(n ?1) / 2 comparisons are performed without finding a diagonal attack, return true.

1<>