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);
chessBoard[row][col] = true;
if (row == boundary) {
System.out.println("Problem Solved!!");
return true;
} else if (!backTrackRoutine(row + 1, 0)) {
System.out.println("Removing queen at Row- " + row + " , col-" + col);
chessBoard[row][col] = false;
flag = backTrackRoutine(row, col + 1);
}
return flag;
} else {
return backTrackRoutine(row, col + 1);
}
}
public boolean canPlace(int row, int col) {
return !rowAndColhasAQueen(row, col) && !diagonalHasAQueen(row, col);
}
public boolean rowAndColhasAQueen(int row, int col) {
for (int i = 0; i < size; i++) {
if (chessBoard[row][i]) {
return true;
}
}
for (int i = 0; i < size; i++) {
if (chessBoard[i][col]) {
return true;
}
}
return false;
}
public boolean diagonalHasAQueen(int row, int col) {
int flag = 0;
while (row != 0) {
flag++;
row--;
if (col + flag < size)
if (chessBoard[row][col + flag]) {
return true;
}
if (col - flag > -1)
if (chessBoard[row][col - flag]) {
return true;
}
}
return false;
}
}
Output:
Placing queen at Row- 0 , col-0 Placing queen at Row- 1 , col-2 Placing queen at Row- 2 , col-4 Placing queen at Row- 3 , col-1 Placing queen at Row- 4 , col-3 Removing queen at Row- 4 , col-3 Placing queen at Row- 4 , col-7 Removing queen at Row- 4 , col-7 Removing queen at Row- 3 , col-1 Placing queen at Row- 3 , col-6 Placing queen at Row- 4 , col-1 Placing queen at Row- 5 , col-3 Placing queen at Row- 6 , col-5 Removing queen at Row- 6 , col-5 Removing queen at Row- 5 , col-3 Removing queen at Row- 4 , col-1 Placing queen at Row- 4 , col-3 Removing queen at Row- 4 , col-3 Removing queen at Row- 3 , col-6 Placing queen at Row- 3 , col-7 Placing queen at Row- 4 , col-1 Placing queen at Row- 5 , col-3 Placing queen at Row- 6 , col-5 Removing queen at Row- 6 , col-5 Removing queen at Row- 5 , col-3 Removing queen at Row- 4 , col-1 Placing queen at Row- 4 , col-3 Removing queen at Row- 4 , col-3 Removing queen at Row- 3 , col-7 Removing queen at Row- 2 , col-4 Placing queen at Row- 2 , col-5 Placing queen at Row- 3 , col-1 Placing queen at Row- 4 , col-6 Placing queen at Row- 5 , col-4 Removing queen at Row- 5 , col-4 Removing queen at Row- 4 , col-6 Removing queen at Row- 3 , col-1 Placing queen at Row- 3 , col-7 Placing queen at Row- 4 , col-1 Placing queen at Row- 5 , col-3 Removing queen at Row- 5 , col-3 Placing queen at Row- 5 , col-4 Removing queen at Row- 5 , col-4 Removing queen at Row- 4 , col-1 Removing queen at Row- 3 , col-7 Removing queen at Row- 2 , col-5 Placing queen at Row- 2 , col-6 Placing queen at Row- 3 , col-1 Placing queen at Row- 4 , col-3 Placing queen at Row- 5 , col-7 Removing queen at Row- 5 , col-7 Removing queen at Row- 4 , col-3 Placing queen at Row- 4 , col-7 Placing queen at Row- 5 , col-4 Removing queen at Row- 5 , col-4 Removing queen at Row- 4 , col-7 Removing queen at Row- 3 , col-1 Removing queen at Row- 2 , col-6 Placing queen at Row- 2 , col-7 Placing queen at Row- 3 , col-1 Placing queen at Row- 4 , col-3 Removing queen at Row- 4 , col-3 Placing queen at Row- 4 , col-6 Removing queen at Row- 4 , col-6 Removing queen at Row- 3 , col-1 Placing queen at Row- 3 , col-5 Placing queen at Row- 4 , col-1 Removing queen at Row- 4 , col-1 Placing queen at Row- 4 , col-3 Placing queen at Row- 5 , col-1 Placing queen at Row- 6 , col-4 Removing queen at Row- 6 , col-4 Removing queen at Row- 5 , col-1 Removing queen at Row- 4 , col-3 Removing queen at Row- 3 , col-5 Removing queen at Row- 2 , col-7 Removing queen at Row- 1 , col-2 Placing queen at Row- 1 , col-3 Placing queen at Row- 2 , col-1 Placing queen at Row- 3 , col-4 Placing queen at Row- 4 , col-2 Removing queen at Row- 4 , col-2 Placing queen at Row- 4 , col-7 Removing queen at Row- 4 , col-7 Removing queen at Row- 3 , col-4 Placing queen at Row- 3 , col-6 Placing queen at Row- 4 , col-2 Removing queen at Row- 4 , col-2 Removing queen at Row- 3 , col-6 Placing queen at Row- 3 , col-7 Placing queen at Row- 4 , col-2 Placing queen at Row- 5 , col-6 Removing queen at Row- 5 , col-6 Removing queen at Row- 4 , col-2 Placing queen at Row- 4 , col-5 Placing queen at Row- 5 , col-2 Removing queen at Row- 5 , col-2 Removing queen at Row- 4 , col-5 Removing queen at Row- 3 , col-7 Removing queen at Row- 2 , col-1 Placing queen at Row- 2 , col-5 Placing queen at Row- 3 , col-2 Removing queen at Row- 3 , col-2 Placing queen at Row- 3 , col-7 Placing queen at Row- 4 , col-1 Placing queen at Row- 5 , col-4 Placing queen at Row- 6 , col-2 Removing queen at Row- 6 , col-2 Removing queen at Row- 5 , col-4 Placing queen at Row- 5 , col-6 Placing queen at Row- 6 , col-2 Removing queen at Row- 6 , col-2 Removing queen at Row- 5 , col-6 Removing queen at Row- 4 , col-1 Placing queen at Row- 4 , col-2 Placing queen at Row- 5 , col-4 Removing queen at Row- 5 , col-4 Placing queen at Row- 5 , col-6 Removing queen at Row- 5 , col-6 Removing queen at Row- 4 , col-2 Removing queen at Row- 3 , col-7 Removing queen at Row- 2 , col-5 Placing queen at Row- 2 , col-6 Placing queen at Row- 3 , col-2 Placing queen at Row- 4 , col-5 Placing queen at Row- 5 , col-1 Placing queen at Row- 6 , col-4 Removing queen at Row- 6 , col-4 Removing queen at Row- 5 , col-1 Removing queen at Row- 4 , col-5 Placing queen at Row- 4 , col-7 Placing queen at Row- 5 , col-1 Placing queen at Row- 6 , col-4 Removing queen at Row- 6 , col-4 Removing queen at Row- 5 , col-1 Removing queen at Row- 4 , col-7 Removing queen at Row- 3 , col-2 Placing queen at Row- 3 , col-4 Placing queen at Row- 4 , col-1 Removing queen at Row- 4 , col-1 Placing queen at Row- 4 , col-2 Removing queen at Row- 4 , col-2 Placing queen at Row- 4 , col-7 Placing queen at Row- 5 , col-1 Removing queen at Row- 5 , col-1 Removing queen at Row- 4 , col-7 Removing queen at Row- 3 , col-4 Removing queen at Row- 2 , col-6 Placing queen at Row- 2 , col-7 Placing queen at Row- 3 , col-2 Removing queen at Row- 3 , col-2 Placing queen at Row- 3 , col-4 Placing queen at Row- 4 , col-1 Removing queen at Row- 4 , col-1 Placing queen at Row- 4 , col-2 Removing queen at Row- 4 , col-2 Removing queen at Row- 3 , col-4 Removing queen at Row- 2 , col-7 Removing queen at Row- 1 , col-3 Placing queen at Row- 1 , col-4 Placing queen at Row- 2 , col-1 Placing queen at Row- 3 , col-5 Placing queen at Row- 4 , col-2 Placing queen at Row- 5 , col-6 Placing queen at Row- 6 , col-3 Removing queen at Row- 6 , col-3 Removing queen at Row- 5 , col-6 Removing queen at Row- 4 , col-2 Removing queen at Row- 3 , col-5 Placing queen at Row- 3 , col-7 Placing queen at Row- 4 , col-2 Placing queen at Row- 5 , col-6 Placing queen at Row- 6 , col-3 Removing queen at Row- 6 , col-3 Removing queen at Row- 5 , col-6 Removing queen at Row- 4 , col-2 Placing queen at Row- 4 , col-5 Placing queen at Row- 5 , col-2 Removing queen at Row- 5 , col-2 Placing queen at Row- 5 , col-3 Removing queen at Row- 5 , col-3 Removing queen at Row- 4 , col-5 Removing queen at Row- 3 , col-7 Removing queen at Row- 2 , col-1 Placing queen at Row- 2 , col-6 Placing queen at Row- 3 , col-1 Placing queen at Row- 4 , col-3 Placing queen at Row- 5 , col-7 Removing queen at Row- 5 , col-7 Removing queen at Row- 4 , col-3 Placing queen at Row- 4 , col-5 Placing queen at Row- 5 , col-2 Removing queen at Row- 5 , col-2 Placing queen at Row- 5 , col-7 Removing queen at Row- 5 , col-7 Removing queen at Row- 4 , col-5 Removing queen at Row- 3 , col-1 Removing queen at Row- 2 , col-6 Placing queen at Row- 2 , col-7 Placing queen at Row- 3 , col-1 Placing queen at Row- 4 , col-3 Placing queen at Row- 5 , col-6 Placing queen at Row- 6 , col-2 Removing queen at Row- 6 , col-2 Removing queen at Row- 5 , col-6 Removing queen at Row- 4 , col-3 Placing queen at Row- 4 , col-6 Placing queen at Row- 5 , col-2 Placing queen at Row- 6 , col-5 Removing queen at Row- 6 , col-5 Removing queen at Row- 5 , col-2 Removing queen at Row- 4 , col-6 Removing queen at Row- 3 , col-1 Placing queen at Row- 3 , col-5 Placing queen at Row- 4 , col-2 Placing queen at Row- 5 , col-6 Placing queen at Row- 6 , col-1 Placing queen at Row- 7 , col-3 Problem Solved!! {true,false,false,false,false,false,false,false,} {false,false,false,false,true,false,false,false,} {false,false,false,false,false,false,false,true,} {false,false,false,false,false,true,false,false,} {false,false,true,false,false,false,false,false,} {false,false,false,false,false,false,true,false,} {false,true,false,false,false,false,false,false,} {false,false,false,true,false,false,false,false,} Completed in :9 milli sec Took 981 backtrack calls for completion!