Placing n chess queens on an n×n chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
A way to find fast solutions is published by Carl Friedrich Gauss and implemented here.
if you want to execute it local
Download class file
and execute it like this: "java nQueen 8"
Code listing
import java.io.*;
import java.util.*;
public class nQueen {
static public int Sol_Queen=0;
//-----------------------------------------------------------------
static public void solution(byte row[],int max) {
Sol_Queen++;
StringBuffer s = new StringBuffer("Sol "+Sol_Queen+" found");
for (int i=0;i<max;i++) s.append("\t"+row[i]);
System.out.println(s);
}
//-----------------------------------------------------------------
static public boolean checkOK(byte row[],int x) { /* Max Row to search */
for (int i=0;i<x;i++) {
if (row[i] == row[x] ||
row[i] == row[x]+x-i ||
row[i] == row[x]-x+i )
return false; // failed
}
return true; // no problem
}
//-----------------------------------------------------------------
static public boolean nQueens(byte row[],int n) { // Max number of Queens
boolean ok;
byte x; // active queen
x=row[n];
while (x>=0 && x<n) {
ok=false;
while (!ok && row[x] < n-1)
{
row[x]++; // Queen number x GO in column
ok =checkOK(row,x);
}
if (!ok) x--; // try previous queen
else {
if (x==n-1) {
solution(row,n);
x--; // continue with previous queen
}
else { x++; // try next queen */
row[x]=-1; // Init queen position
}
}
}
return false; // all done, return
}
//-----------------------------------------------------------------
static public void calc(int n) {
byte row[] = new byte[n+2];
byte rowPrev[] = new byte[n+2];
row[0]=-1;
row[n]=0;
for (int i=0;i<n;i++) rowPrev[i]=-1;
nQueens(row,n);
}
//-----------------------------------------------------------------
static public void main (String args[]) throws IOException {
Date date;
int MAX;
try {
Integer a=new Integer(args[0]);
MAX= a.intValue();
date=new Date();
System.out.println("Start "+date+" to calculate nQueen for n= "+MAX);
calc(MAX);
date=new Date();
System.out.println("done "+date);
}
catch (ArrayIndexOutOfBoundsException e) {System.out.println("Argument missing!");}
catch (NumberFormatException e) {System.out.println("Needs decimal input!");}
} // end of main
} // end of class