/*
 * File: 8queens.c
 * Author: Shankar Chakkere <shankara@erols.com, schakkere@denro.com>
 * Date: 6/14/95
 * Status: Working 6/16/95
 * Tested : Borland C++ v2.0 & GCC cygnus-2.7.2-970404 on WIN95
 * Abstract: This is a classic chess problem of placing 8 queens on a chess 
 * board in a non threatening positions. This program finds eigth of the
 * solutions, but can be modified to find all the solutions. This program 
 * uses backtracking algorithm to solve the problem.
 * Copyright (C) 1999 Shankar Chakkere
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * Visit http://www.fsf.org for more information

 *
 */
#include <stdio.h>

#define DEBUG 0
#define OCCUPIED 1
#define NOTOCCUPIED 0
#define EXCEPTION 20

#define TOPLEFTROW(row,col) ((row - col) <= 0 ? 0: (row - col))
#define TOPLEFTCOL(row,col) ((col - row) <= 0 ? 0: (col - row))
#define BOTLEFTROW(row,col) ((row + col) >= 7 ? 7: (row + col))
#define BOTLEFTCOL(row,col) ((row + col) >= 7 ? (col + row - 7): 0)


char board[8][8];          /* The chess board
                             0 1 2 3 4 5 6 7
                             1
                             2
                             3
                             4
                             5
                             6
                             7
                           */
char hostile[8][8];         /* The mirror of chess board which is marked with
                               all the square occupied by the previous moves.
                             */

/*  prototype of functions.
*/
char makemove(char selrow, char selcol);
char findnonhostile(char selrow, char selcol);
void markmove(char selrow, char selcol);
void printboard(void);
void printhostile(void);
void initboard(void);
void inithostile(void);
void unmark(char selcol);
char previous(char selcol);

void main (void)
{
   char row, col, selrow, x;

   for(x = 7; x >= 0; x--)
      {

      initboard();   /* remove all the queens from the chess board */
      row = x;

      printf("\n Start (%d , 1)", row +1);

      for (col = 0; col < 8 ; col++)   /* for all the column in the chess board */
         {
         #if DEBUG
         printf("\n***forward***\n");
         printf("\n row %d col %d",row, col);
         #endif
         if((selrow = makemove(row,col)) != EXCEPTION)
            {
            /* If possible place the queen */
            #if DEBUG
            printf("\n***place queen***\n");
            printf("\n row %d col %d",selrow, col);
            #endif
            board[selrow][col] = col + 1;
            row = 7; /* start from bottom of the board for next forward move */
            }
         else
            {
            /* back track */
            do
               {
               /* backtrack: Unerase previous queen placement and move the queen
                  further up do it recursively  till you can move forward. Done by
                  do while loop.
                  */
               col--;            /* column of previous queen placed */
               while   ((row = previous(col)) == 0)
                  {
                  board[row][col] = NOTOCCUPIED; /* mark not occupied */
                  col--;          /* get previous row of queen for that col*/
                  };
                  board[row][col] = NOTOCCUPIED; /* mark not occupied */
                  unmark(col);    /* create a new hostile map till this move*/
                  row--;         /* move the queen up */
                  #if DEBUG
                  printf("\n ***backtracking***\n");
                  printf("\n row %d col %d",row, col);
                  #endif
                  }
               while((row = makemove(row,col)) == EXCEPTION);
               board[row][col] = col + 1;      /* place the queen */
               row = 7; /* start from bottom of the board for next forward move */
               }
            }
         /* All the queens are been placed. Print the chess board */
         printboard();
         printf("\n\n");
         }
      }

char   makemove(char selrow,char selcol)
{
   /* if possible to place the queen return the row where the queen
      can be placed, else return EXCEPTION
      */
   char row;
   row =   findnonhostile(selrow, selcol); /* find a non hostile column */

   #if DEBUG
   printf("\n In make move, findnonhostile selected  row %d", row);
   #endif

   if (row != EXCEPTION)
      {
      /* if the queen can be placed mark the move in hostile table */
      markmove(row , selcol);
      }
      return row;
}

char findnonhostile(char selrow, char selcol)
{
   /* returns nonhostile row (where the queen can be placed)
      for the current column.If possible to place the queen
      in this column return the column, else return EXCEPTION.
      */
   char row;
   for ( row = selrow; row >= 0 ; row--)
      {
      if (hostile[row][selcol] == NOTOCCUPIED)
         return row;
      }
      return EXCEPTION;
}

void markmove(char selrow, char selcol)
{
   /* mark all the rows, columns, and diagonal which are visible from the
      current position of the queen.
      */
   char row, col;
   /* mark row */
   for( col = 0; col < 8; col++)
      hostile[selrow][col] = OCCUPIED;
   /* mark col */
   for( row = 0; row < 8; row++)
      hostile[row][selcol] = OCCUPIED;

   #if 0
   /* diagonal up*/
   col = selcol;
   row = selrow;
      /* move to the edge of diagonal if possible*/
   if(selcol > 0 && selrow < 8)
      {
      for(; row < 8 && col > 0 ; row++, col--)
         ;
      }
   for(; row >= 0 && col < 8 ; row--, col++)
      hostile[row][col] = OCCUPIED;
   /* diagonal down*/
   col = selcol;
   row = selrow;
      /* move to the edge of diagonal if possible*/
   if(selcol > 0 && selrow > 0)
      {
      for(; row > 0 && col > 0 ; row--, col--)
         ;
      }
   for(; row < 8 && col < 8 ; row++, col++)
      hostile[row][col] = OCCUPIED;
   #endif

   /* select the top leftmost square on the diagonal (which runs from
      upper left to lower right) on which the current selected square lies.
      */
   row = TOPLEFTROW(selrow,selcol);
   col = TOPLEFTCOL(selrow,selcol);
   for(; row < 8 && col < 8 ; row++, col++)
      hostile[row][col] = OCCUPIED;
   /* select the bottom leftmost square on the diagonal (which runs from
      upper right to lower left) on which the current selected square lies.
      */
   row = BOTLEFTROW(selrow,selcol);
   col = BOTLEFTCOL(selrow,selcol);
   for(; row >= 0 && col < 8 ; row--, col++)
      hostile[row][col] = OCCUPIED;
}

void printboard(void)
{
   char row, col;
   for (row = 0; row < 8; row++)
      {
      printf("\n");
      for (col = 0; col < 8; col++)
        printf("%d ", board[row][col]);
      }
}

void printhostile(void)
{
   char row, col;
   for (row = 0; row < 8; row++)
      {
      printf("\n");
      for (col = 0; col < 8; col++)
        printf("%d ", hostile[row][col]);
      }
      printf("\n");
}

void initboard(void)
{
   char row,col;
   for (row = 0; row < 8; row++)
      for (col = 0; col < 8; col++)
         {
         hostile[row][col] = NOTOCCUPIED;
         board[row][col] = NOTOCCUPIED;
         }
}

void inithostile(void)
{
   char row,col;
   for (row = 0; row < 8; row++)
      for (col = 0; col < 8; col++)
         {
         hostile[row][col] = NOTOCCUPIED;
         }
}

void unmark(char selcol)
{
   char col,row;
   inithostile();      /* Clear the hostile table */
   for (col = 0; col < selcol; col++)
      {
      row = previous(col);   /* Get the row occupied for this column
                              by previous move
                              */
      markmove(row,col);   /* mark the hostile map for this row,column */
      }
}

char previous(char selcol)
{
   /* get the row on which the queen is placed for the current column
      */
   char row;
   for (row = 0; row < 8; row++)
      {
      if (board[row][selcol] != NOTOCCUPIED)
         return row;
      }
   return row;
}