Paradigms for Optimization Problems - A Concise and Practical Introduction to Programming Algorithms in Java - page 199

positions on its given row). Let the i th queen column position be stored in
an integer array queen . That is, the position of the i th queen is stored at
coordinates ( i ,queen[i ]) (with queen indices ranging from 0 to 7 to follow Java
array conventions). Suppose we have already correctly placed l queens on the
first l rows so that these l queens are pairwise safe. For the ( l + 1)th queen
necessarily located at row l + 1, we are going to check in turn all column
positions, starting from column 0 up to column 7 until we find a safe position
for the queen with respect to the previously located ones. Once such a position
found, we proceed to the next queen lying on the next line, and so on. Whenever
we reach at some point all column positions without finding a solution, then
we need to backtrack by increasing the column of the previous queen (located
at the row below the current queen), and so on. The recursive exploration with
backtracking is detailed in the source code below. The recursive procedure is
initially launched by calling in the main procedure function search(0) .

Program 9.5 Eight queen puzzle: Search with backtracking
static boolean search( int row)
boolean result= false ;
if (row==n)
{ displayChessboard () ;
nbsol++; }

else
{ int j=0;
while (! result && j < n)
{ if (safeMove(row , j ) )
{ queen [ row]= j ;
result=search(row+1);
// Backtracking here
j ++; // explore all columns

}
}
return result ;

}

To check whether two queens are in mutually safe positions or not, we check
whether these two queens lie on the same row or column, or whether they share
a common diagonal. This can be compactly written as:

Program 9.6 Check whether two queens are in mutually safe position or not
static boolean wrongPos( int i1 , int j1 , int i2 , int j2)
return (i1==i2 ||
j1==j2

||
Math . abs ( i1 − i2) == Math.abs(j1 − j2) ) ;