n-Queens backtracking code

I was learning backtracking algorithms earlier today, and was excited and wrote this code for n-Queens problem. Being my first try at backtracking algorithms, I would appreciate if you guys could chip in some suggestions/flaws in my code.

Also, I had a really tough time getting this to work - I struggled mainly in trying to debug so many recursive calls and often got lost in analyzing which ones were waiting for "return value" from the other deeper function calls. — any help on how to get started/thinking about recursion while writing code would be very helpful.

```
package com.komal.backtracking;

import java.util.concurrent.TimeUnit;

public class Nqueens {

static boolean[][] chessBoard;
static int size;
static int boundary;

public void initChessBoard() {
chessBoard = new boolean[size][size];
boundary = size - 1;
}

static int noOfBacktrackCalls;

public static void main(String[] args) {
size = 8;
Nqueens nQueens = new Nqueens();
nQueens.initChessBoard();
long startTime = System.nanoTime();
if (!nQueens.backTrackRoutine(0, 0)) {
System.out.println("Cannot be solved!!");
}

for (boolean[] i : chessBoard) {
System.out.print("\n{");
for (boolean i1 : i) {
System.out.print(i1 + ",");
}
System.out.print("}");
}
long timeTaken = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime);
System.out.println("\nCompleted in :" + timeTaken + " milli sec");
System.out.println("\nTook " + noOfBacktrackCalls + " backtrack calls for completion!");
}

public boolean backTrackRoutine(int row, int col) {
noOfBacktrackCalls++;
boolean flag = true;
if (col == size || row == size) {
return false;
}
if (canPlace(row, col)) {
System.out.println("Placing queen at Row- " + row + " , col-" + col);

General remarks

• chessBoard, size, boundary and noOfBacktrackCalls should be non-static and private -- since the functions manipulating them are also (correctly!) non-static.

• Naming: I suggest rowOrColHasAQueen instead of rowAndColhasAQueen (also note capitalization)

• Pre-condition checking: at the beginning of backTrackRoutine, I suggest checking also that col and row do not exceed size (now you only check for strict equality). If this does happen, I would throw an exception, and not just return with false, because either the public function was called with wrong parameters, or there is a bug in the implementation (you can use noOfBacktrackCalls to differentiate the two cases).

• flag varible: in the backTrackRoutine, it is not needed (you can directly return the value you are assigning to it), in diagonalHasAQueen, I would give it a more descriptive name (e.g. steps)

• I would make the implementation functions (canPlace, rowAndColhasAQueen, diagonalHasAQueen) private.

Performace

I see one possible way of (maybe?) improving performance (in case it really matters for 9 milli seconds :) ). Namely, caching whether a given row or column has a queen. Let's look at rows (cols would be similar): you need an array of booleans, with the size of size, with originally all elements set to false. When you put a queen in row #i, you also set the element at position i to true, in the array. And set it back to false, in case the queen is removed. In this way, rowAndColhasAQueen does not have to iterate on the whole table, but can look up the rows/cols arrays instead. (I am not sure if there is such an optimization for diagonals as well, maybe...)

StackExchange Code Review Q#131159, answer score: 7