/*
 * To recursively calculate the number of configurations of n rooks
 * on an n-by-n chessboard such that no two rooks can capture each other in the
 * next move (i.e., no two rooks lie on the same row or same column).
 * Configurations where all the rooks are on the main diagonal or all of
 * them are on the main cross-diagonal are not valid. 
 * @author-Karan Narain(karan@iitk.ac.in)
 *
*/
#include <stdio.h>

void check(int r, int c, char board[20][20]);

int no_of_rooks, rook = 2;
int count = 0;

int main()
{
   int row, col, i , j;
   char board[20][20];
   printf("Enter the number of rooks : ");
   scanf("%d", &no_of_rooks);
   if(no_of_rooks < 2)
   {
      printf("\nThe number of rooks must be greater than 1.\n");
      return (0);
   }
   //Initialize the board
   for(i = 0; i < no_of_rooks; i++)
      for(j = 0;j < no_of_rooks;j++)
	board[i][j] = '-';


   // This for-loop is used for checking all the columns of row 0 only...
   for(col = 0; col < no_of_rooks; col++)
   {
      check( 0, col, board );
   }
   
   //Subtract the all-rooks-in-same-diagonal(main diagonal or cross diagonal) configurations from the total configurations
   count=count-2;
   printf("\nOn a %d X %d chessboard,the total no. of configurations in which the %d rooks don't attack each other and are not all present along the diagonals, is ....%d\n",no_of_rooks,no_of_rooks,no_of_rooks,count);
   return (0);
}

void check( int r, int c, char board[20][20] )
{
   int i,j,p,h;

   // Terminating condition for the recursion...
   if ( ( r == no_of_rooks )  && ( c == 0 ))
   {
      	count++;
   }

   // Vertical check...
   for(i = 0; i < r; i++)
   {
      if ( board[i][c] == rook)
         return;
   }

   // Horizontal check...
   for(j = 0; j < c; j++)
   {
      if ( board[r][j] == rook)
         return;
   }

   // Placing the rook if the checked position is OK...
   board[r][c] = rook;
   r++;
   
   // This for-loop is used for checking all the columns for each row
   //starting from 1 upto the end...
   for(p = 0; p < no_of_rooks; p++)
      check(r, p, board);
   for(h = 0; h < no_of_rooks; h++)
      board[r - 1][h] = '-';

}