In this assignment you will write a Java program that finds all solutions to the
ID: 3667363 • Letter: I
Question
In this assignment you will write a Java program that finds all solutions to the n-Queens problem, for lSns13. Begin by reading the Wikipedia article on the Eight Queens puzzle at: http://en wikipedia org/wiki/Eight queens_puzzle In the game of Chess a queen can move any number of spaces in any linear direction: horizontally, vertically, or along a diagonal. The Eight Queens puzzle is to find a placement of 8 queens on an otherwise empty 8x8 chessboard in such a way that no two queens confront each other. One solution to this problem is pictured below. The n-Queens problem is the natural generalization of placing n queens on an nxn chessboard so that no two queens confront one another. 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 nxn 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.Explanation / Answer
import static java.lang.System.*;
class Queens {
static void findQueens(int num, String[] args) {
int counter = 0;
int j,k;
int [] A = new int[num+1];
for(int i = 0; i< num+1; ++i) {
A[i] = i;
}
if(checkOptionV(args[0])) {
for( j=0; j<doFactorial(num); j++) {
nextPermutation(A);
if(isSolution(A)) {
counter++;
System.out.print("(");
for( k=1; k<A.length-1; k++) {
System.out.print(A[k]+", ");
}
if(k == A.length-1) {
System.out.print(A[k]);
}
System.out.println(")");
}
}
}
else {
for( j=0; j<doFactorial(num); j++) {
nextPermutation(A);
if(isSolution(A)) {
counter++;
}
}
System.out.println(num+"-Queens has "+counter+" solutions.");
}
}
static void nextPermutation(int[] A){
int i, j, k, pivot=0, successor=0;
boolean pivotFound = false;
for(i=A.length-2; i>0; i--) {
if(A[i]<A[i+1]) {
pivot = i;
pivotFound = true;
break;
}
}
if(pivotFound == false) {
reverse(A, 1, A.length-1);
return;
}
for(k=A.length-1; k>0; k--) {
if(A[k]>A[i]) {
successor = k;
break;
}
}
swap(A, pivot, successor);
reverse(A, pivot+1, A.length-1);
return;
}
static boolean isSolution(int[] A){
int i, j;
int n = A.length;
for(i=1; i<=n-1; i++) {
for(j=i+1; j<=n-1; j++) {
if(j-i==Math.abs(A[i]-A[j])) {
return false;
}
}
}
return true;
}
static void swap(int[]A, int i, int j) {
int temp;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
static void reverse(int[]A, int i, int j) {
while(i<j){
swap(A,i,j);
i++;
j--;
}
}
static int doFactorial(int num) {
int ans;
if(num < 0) {
out.println("number must be non-negative integer");
printUsage();
}
if(num == 0 || num == 1) return ans = 1;
ans = num * doFactorial(num-1);
return ans;
}
static boolean checkOptionV(String args) {
if(args.equals("-v")) return true;
else return false;
}
static int parseArgs(String[] args) {
int num = 0;
if(args.length == 1) {
try { num = Integer.parseInt(args[0]); }
catch (NumberFormatException e) { printUsage(); }
}
else if (args.length == 2) {
if(checkOptionV(args[0])) {
try { num = Integer.parseInt(args[1]); }
catch (NumberFormatException e) { printUsage(); }
}
else printUsage();
}
return num;
}
static void printUsage() {
out.println("Usage: java Queens [-v] number");
out.println("Option: -v verbose output, print all solutions");
exit(1);
}
public static void main(String[] args) {
if (args.length > 2) printUsage();
int num = parseArgs(args);
findQueens(num,args);
}
}