The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Backtracking

Problem :-
Solve the N - Queens problem.
N - Queen is the problem of placing N queens on an N x N chessboard so that no two queens
can attack each other. For e.g, on a 4 x 4 chessboard, one of the possible solution to place 4 queens on the chessboard is shown below :
0  0  1  0
1  0  0  0
0  0  0  1
1  0  0
1s are placed in the cells where queens can be safely placed.

Solution :-
The solution requires that no two queens should share the same row, column or diagonal.
We will start placing queens one by one in different columns starting from the leftmost column and check for clashes with the previously placed queens.
Suppose we are at jth column. This means j - 1 queens are already placed. Now in column j , there are n possible rows in which a queen can be placed.
1 ) We will select one of the rows and check recursively if placing the queen in this row leads to a solution. If a solution exists, then we will proceed to the next column and repeat the same steps.
2 ) If the solution doesn't exist, then we backtrack and select some other row and check if placing the queen in that row leads to a solution. We will keep trying till we find a valid row.
When all the columns are visited and all queens are placed, we have found a solution.
See the implementation below.

#include<iostream>
#define N 4
using namespace std;

/* print the chess_board after placing 'N' queens
  '1' denotes the positions where queens are placed
*/
void printPlacement(int chess_board[N][N]) {
   int i,j;
   cout<<"\nPlacement of N queens :-\n";
   for (i = 0; i < N; i++) {
      for (j = 0; j < N; j++) {
           cout<<chess_board[i][j]<<" ";
      }
      cout<<endl;
   }
}

/* ckeck if a queen can be placed on the chess_board at a specific cell
   (r_idx,c_idx) so that it cannot be attacked by any of the other queens.
   We only need to check whether queens placed in columns [0...c_idx-1] can
   attack this cell or not.     
*/
bool isCellSafe(int chess_board[N][N], int r_idx, int c_idx) {
   int i, j;

   for (i = 0; i < c_idx; i++) {
      // any queen placed cells (r_idx,0) to (r_idx..c_idx-1)
      // can attack this cell i.e. we are checking for queens
      // placed in the left of this cell
      if (chess_board[r_idx][i] == 1) {
         return false;
      }
   }

   i = r_idx; j = c_idx;
   while (i >= 0 && j >= 0) {
      // we are checking if any queen is placed in the
      // upper left diagonal
      if (chess_board[i][j] == 1) {
         return false;
      }
      i--; j--;
   }

   i = r_idx; j = c_idx;
   while (i < N && j >= 0) {
      // we are checking if any queen is placed in the
      // lower left diagonal
      if (chess_board[i][j] == 1) {
         return false;
      }
      i++; j--;
   }

   // queen can be placed in this cell (r_idx,c_idx)
   return true;
}

/* recursive function to solve the N Queens problem  
   Start placing the queens in each column starting from left
   For each recursive call, find the row in which a queen can be 
   placed for a particular column
*/
bool placeNQueens(int chess_board[N][N], int c_idx) {
   if (c_idx >= N) {
      // all N queens are successfully placed on the chess board
      return true;
   }

   int i;
   // look for a feasible cell i.e find a row where a queen
   // can be placed for the current column
   // iterate over each row   
   for (i = 0; i < N; i++) {
      if (isCellSafe(chess_board, i, c_idx)) {
         // cell (i,c_idx) is safe, so place a queen here
         chess_board[i][c_idx] = 1;

         // recursively place other queens in each successive column
         if (placeNQueens(chess_board, c_idx + 1) == true )
            return true;

         // we cannot place the queen in this cell
         // backtrack and try for other possiblities
         chess_board[i][c_idx] = 0;
      }
   }

   // Solution to N queens problem doesn't exist 
   return false;
}


// main
int main() {
   int chess_board[N][N] = { {0, 0, 0, 0},
                             {0, 0, 0, 0},
                             {0, 0, 0, 0},
                             {0, 0, 0, 0} };
   bool n_queens_sol = placeNQueens(chess_board,0);
   if (n_queens_sol == false) {
      cout<<"\n N queens placement not possible";
   }
   else {
      cout<<"\n N queens can be placed on NxN chessboard";
      printPlacement(chess_board);
   }
   cout<<endl;
   return 0;
}

Back | Next

All problems on Backtracking technique
* Given a maze in the form of a matrix of size n x n. A robot is placed at cell ( 0, 0 ). Print all possible paths that robot can take to reach the last cell ( n-1, n-1 ) of the maze
* Given a maze in the form of a matrix of size n x n with all elements as 0 or 1. 0 denotes safe cell & 1 denotes dangerous cell. A rat is placed at cell ( 0, 0 ). Print a safe path ( if exists ) which rat can take to reach last cell ( n-1, n-1 ).
* Solve the Knight's Tour problem
* Solve the N-Queens problem
* Given a set of candidate values in an array & a target x, find all possible ways in which candidate values can be added to get x. We can use each candidate value any number of times