8
\$\begingroup\$

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!
Jamal
35.2k13 gold badges134 silver badges238 bronze badges
asked Jun 5, 2016 at 17:16
\$\endgroup\$
3
  • \$\begingroup\$ I do not understand, why is size 32and not 8? (Output implies 8 to me...) \$\endgroup\$ Commented Jun 5, 2016 at 19:34
  • \$\begingroup\$ Yep, it's 8. Typo. Sorry about that, I'll correct it. Was trying out different inputs and ended up copying different ip/op. \$\endgroup\$ Commented Jun 6, 2016 at 3:50
  • \$\begingroup\$ Do you really "try" another row recursively? It would complicate more the problem... \$\endgroup\$ Commented Jun 6, 2016 at 9:05

3 Answers 3

7
\$\begingroup\$

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...)

answered Jun 5, 2016 at 20:10
\$\endgroup\$
2
  • \$\begingroup\$ Thanks. Caching should definitely save significant time. However, the code runs forever(>10mins- I didn't even wait that long) for size=64. What's the best running time out there in general for this nqueen problem? Any idea? \$\endgroup\$ Commented Jun 6, 2016 at 10:05
  • \$\begingroup\$ Caching, yes. First we should note each queen is placed in a separate row, hence we can describe their positions by int col[] of size N indexed by a row number. Then we can drop the N-by-N square board. And we can cache the columns use with some boolean columnIsUsed[] of size N indexed by a column number; similary for diagonals boolean diagNEisUsed[] of size 2N-1 indexed by col-row+N-1 and boolean diagNWisUsed[] of size 2N-1 indexed by col+row. \$\endgroup\$ Commented Feb 14, 2018 at 20:03
2
\$\begingroup\$

A bit late to answer but since no previous answer was accepted this may still be useful to anyone ending up on this question.

The most important and at the same time hardest part about solving a logic puzzle like NQueens is coming up with a good representation of the solution space.

Your boolean[][] works and looks like the most obvious choice. But it doesn't use any extra information that we know about the solution.
We already know that each row and column will contain exactly 1 queen. So we can change the problem statement from

For each of the N queens, try to find a row and column to place them so they don't attack each other

into an alternative search:

For each of the rows, find the column on which the queen is placed.

or switching rows/columns:

For each of the columns, find the row on which the queen is placed.

This translates nicely into representing the board by an array of n numbers: int[] board = new int[n].

What this means is that the index in that list is the number of the row, and the value is the column (or vice versa).

Notice that just by choosing this representation we don't have to check for the same rows at all. There will always be exactly 1 queen on each row.

Checking for 2 queens on the same column is also as easy as checking if 2 of the values in this array are equal.

For the diagonals it's slightly trickier. 2 queens are attacking diagonally when either the row + column of queen 1 is equal to row + column of queen 2. Or if (row queen 1 + column queen 2) is equal to (row queen 2 + column queen 1).

Since we're gonne put the queens in recursively we can us a method that checks for a given row if any queens placed on the rows above that are attacking her. This looks as follows:

private static boolean isAttacking(int[] board, int row){
 for(int i = 0; i < row; i++){
 //check same column
 if(board[i] == board[row]){
 return true;
 }
 //check diagonals
 if (board[i]+i == board[row]+row) {
 return true;
 }
 if (board[row]+i == board[i]+row) {
 return true;
 }
 }
 return false;
}

The actual recursion can then look like this:

private static boolean placeQueen(int[] board, int queenIndex){
 if(queenIndex >= board.length){
 //we have succesfully placed all N queens
 return true;
 }
 for(int i = 0; i < board.length; i++){
 board[queenIndex] = i;
 if(!isAttacking(board, queenIndex)){
 if(placeQueen(board, queenIndex + 1)) {
 return true;
 }
 }
 }
 return false;
}

Which reads as: For the given row, try to put the queen on each of the columns and check recursively if the remaining queens can still be placed.

To test the program and see if it actually finds a solution let's also write a quick printing method to show us the solution:

private static void print(int[] board) {
 for (int row : board) {
 System.out.print('|');
 for (int col = 0; col < board.length; col++) {
 if (row == col) {
 System.out.print("Q|");
 } else {
 System.out.print(" |");
 }
 }
 System.out.println();
 }
}

And all that's left is writing a simple main method to actually call the solver:

public static void main(String[] args) {
 long start = System.currentTimeMillis();
 final int N = 8;
 int[] board = new int[N];
 placeQueen(board,0);
 print(board);
 System.out.println((System.currentTimeMillis() - start) + " milliseconds");
}

Quick note: I also added a simple timing printout to know how many miliseconds it took to find the solution. For n = 8 this printed out:

|Q| | | | | | | | 
| | | | |Q| | | | 
| | | | | | | |Q| 
| | | | | |Q| | | 
| | |Q| | | | | | 
| | | | | | |Q| | 
| |Q| | | | | | | 
| | | |Q| | | | | 
1 milliseconds

When you want to time your application it's also worth removing all printing of in between steps since printing to console takes a bit more time than the rest of the code.

Just for fun: I added a count on number of backtracks too. For n=8 it takes only 113.

For n=16 it takes 8 milliseconds and 10052 backtracks.

Your solution on my pc took (after removing all prints) 2 milliseconds for n=8 and 19 milliseconds for n=16 (with 170748 backtracks).

Stephen Rauch
4,31412 gold badges24 silver badges36 bronze badges
answered Feb 14, 2018 at 16:14
\$\endgroup\$
1
\$\begingroup\$

Not related to the main issue (recursivity) but the solution could use caches.

Let me explain:

The idea of the original solution is to turn on all the cells that are threatened by a queen. It uses some loops to enable or disable the cells.

That is very precise but it is slow. Instead, you might enable or disable sets. For example rows, columns, diagonals.

There are 8 rows, 8 columns, 8 main-diagonal and its parallels, and 8 counter-diagonal and its parallels.

My purpose is to use that like the code below:

 private void putOn(int row, int col) {
 chessBoard[row][col] = true;
 rows[row] = true;
 cols[col]= true;
 rightDiagonals[row + col] = true;
 leftDiagonals[row - col + size] = true;
 }
 private void removeOn(int row, int col) {
 chessBoard[row][col] = false;
 rows[row] = false;
 cols[col]= false;
 rightDiagonals[row + col] = false;
 leftDiagonals[row - col + size] = false;
 }
 public boolean canPlace(int row, int col) {
 return !chessBoard[row][col] && !rows[row] && !cols[col] && !rightDiagonals[row + col] && !leftDiagonals[row - col + size];
 // 10x slower for big cases return !rowAndColhasAQueen(row, col) && !diagonalHasAQueen(row, col);
 }
answered Jun 6, 2016 at 9:35
\$\endgroup\$
1
  • \$\begingroup\$ please provide detail of your code. \$\endgroup\$ Commented Feb 6, 2020 at 7:34

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.