/*
MPI nqueens
Copyright (C) 2000 Sebastien Chauvin, Tarek El-Ghazawi

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 (at your option) 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

#include <stdlib.h>
#include <stdio.h>
#include "defs.h"

#ifdef DEBUG2
# define DEBUG0
# define DEBUGS
#endif

int gen(msk_t i_colstk, int i_row, msk_t i_msk, int n, sol_t *result)
{ 
  msk_t msk = i_msk;
  msk_t mskstk[MAX_N+2] ; 
  msk_t *pmskstk = mskstk+1 ;

  msk_t colmsk ;

  int col = 0 ;
  msk_t colstk = i_colstk ;

  int row = i_row ;
  int nsols = 0 ;

  colmsk = BASECOLMSK ;

#ifdef DEBUG0
  printf("gen(%5x,%1x,", i_colstk, i_row) ;
  printbits(msk >> 34 + n, n) ;
  printf("|") ;
  printbits(msk >> 34, n) ;
  printf("|") ;
  printbits(msk >> 17, n) ;
  printf("|") ;
  printbits(msk >> 0, n) ;
  printf(",%1x,%p)\n", n, result->psol) ;
#endif
  for(;;)
  { 
    // try to place one queen
#ifdef DEBUG0
    printf("(%d,%d)\n", row, col);
    printf("colmsk : ");
    printbits(colmsk>>34+n,n) ; 
    printf("|") ;
    printbits(colmsk>>34,n) ; 
    printf("|") ;
    printbits(colmsk>>17,n);printf("|");
    printbits(colmsk>>0,n);printf("|");
    printf("\n");
    printf("msk    : ");
    printbits(msk>>34+n,n);printf("|");
    printbits(msk>>34,n);printf("|");
    printbits(msk>>17,n);printf("|");
    printbits(msk>>0,n);printf("|");
    printf("\n");
#endif
    if (colmsk & msk) 
    { // Can not place her -> try the next one
      col++;
      if (col<n)
        colmsk<<=1;
      else
      { // Go back
        while ((row>i_row) && (col>=n))
        { col=(int)((colstk&0xf))+1;
          colstk>>=4;
          msk=*(pmskstk--);
          colmsk=BASECOLMSK<<col;
          row--;
        };
        if (col>=n)  break;
      }
    }
    else
    { // The queen can be placed here
      row++;
      *(++pmskstk)=msk;
      msk |= colmsk; // We place the queen in the masks.
      if (row==n)
      { 
        // We did it ! One solution has been found.
        // The solution is in colstk.
#ifdef DEBUGS
	printf("Solution (%d)\n",nsols);
#endif
        nsols++;
        pmskstk--; // Restitute stacks states
        colmsk=((msk_t)-1); row--; 
        col=n;  // To force the way back
      }
      else
      { 
	msk = (msk&CMASK) + ((msk&D1MASK) << 1) + ((msk&D2MASK) >> 1);
        colstk<<=4;
        colstk|=col;
        col=0; colmsk=BASECOLMSK;
      }
    } 
#ifdef DEBUG0
    printf("\n");
#endif
  }

#ifdef DEBUG0
  printf("                                    -> %d\n", nsols);
#endif
  return nsols;
}