/********************************************************/
/*                Queens Combinations                   */
/*              18 Oct, 2000 by Allen Lam               */
/********************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#define Max 8
#define MaxSol 10000  /*12 Queens needs 14200, 14 Queens needs 365596*/
#define Empty 255

const char *Fname = "queens";
char FileName[30];

enum TCell{Avail, Used};
enum TStatus {Conflict, NotConflict};

enum TCell Cols[Max][Max];
int Final[Max];
char Num[4]; //integer of Max
int Solutions[MaxSol][Max];
int QueensOK=0, Count, SolCount=0, WriteDiskCount=0;
long TotalSol=0;
DWORD StartTick, EndTick;
float ElapsedTime;
FILE *fileptr;

void init(){
  int i, j;
  for (i=0; i<Max; i++){
    for (j=0; j<Max; j++){
      Cols[i][j] = Avail;
    }
  }
  for (i=0; i<Max; i++) Final[i] = Empty;

  itoa(Max, Num, 10);
  strcpy(FileName, Fname);
  strcat(FileName, Num);
  strcat(FileName, ".txt");
}

int PickFromCol(int x){
  int i;
  for (i=0; i<Max; i++){
    if (Cols[x][i] == Avail){
      Cols[x][i] = Used;
      return i;
    }
  }
  return -1;
}

int IsValid(int x, int y){
  if ((x<0) || (x>=Max) || (y<0) || (y>=Max))
    return 0;       /*False*/
    else return 1;  /*True*/
}

void RenewCol(int x){
  int i;
  for (i=0; i<Max; i++){
    Cols[x][i] = Avail;
  }
}

void TestLeftDown(int x, int y){
  if (IsValid(x-1, y+1)){
    if (Final[x-1] == y+1) Count++;
    TestLeftDown(x-1, y+1);
  }
}

void TestLeftUp(int x, int y){
  if (IsValid(x-1, y-1)){
    if (Final[x-1] == y-1) Count++;
    TestLeftUp(x-1, y-1);
  }
}

void TestRightDown(int x, int y){
  if (IsValid(x+1, y+1)){
    if (Final[x+1] == y+1) Count++;
    TestRightDown(x+1, y+1);
  }
}

void TestRightUp(int x, int y){
  if (IsValid(x+1, y-1)){
    if (Final[x+1] == y-1) Count++;
    TestRightUp(x+1, y-1);
  }
}

TStatus TestConflict (int x, int y){
  int i;
  Count = 0;
  for (i=0; i<Max; i++){
    if (Final[i] == y) return Conflict;
  }

  TestLeftDown(x, y);
  if (Count > 0) return Conflict;

  TestLeftUp(x, y);
  if (Count > 0) return Conflict;

  TestRightDown(x, y);
  if (Count > 0) return Conflict;

  TestRightUp(x, y);
  if (Count > 0) return Conflict; else return NotConflict;
}

void WriteFileOpening(){
  fileptr = fopen(FileName, "w");
  fprintf(fileptr, "%d Queens Combinations\n\n", Max);
  fclose(fileptr);
}

void WriteFileData(){
  int i, c=0;
  fileptr = fopen(FileName, "a");
  for (c=0; c<SolCount; c++){
    for (i=0; i<Max; i++)
      fprintf(fileptr, "%-3d", ++Solutions[c][i]);
    fprintf(fileptr, "\n");
  }
  fclose(fileptr);
}

void WriteFileTag(){
  fileptr = fopen(FileName, "a");
  fprintf(fileptr, "\nSolution Count: %d\n", TotalSol);
  fprintf(fileptr, "Time used: %f seconds\n", ElapsedTime);
  fclose(fileptr);
}

void KeepRecord(){
  int i;
  if (SolCount >= MaxSol){
    WriteFileData();
    SolCount = 0;
    WriteDiskCount++;
  }
  for (i=0; i<Max; i++)
    Solutions[SolCount][i] = Final[i];
  SolCount++;
}

int Picking(int x){
  int i, y;
  enum TStatus status;
  for (i=0; i<Max; i++){
    y = PickFromCol(x);
    if (y < 0){
      RenewCol(x);
      QueensOK--;
      Final[QueensOK] = Empty;
      return 0;
    }
    status = TestConflict(x, y);
    if (status == Conflict){
      Picking(x);
      return 0;
    } else /*(if status = NotConflict)*/
    {
      Final[QueensOK] = y;
      QueensOK++;
      if (QueensOK == Max){
  	        KeepRecord();
		    RenewCol(x);
	      Final[QueensOK-1] = Empty;
	      Final[QueensOK-2] = Empty;
          QueensOK -= 2;
	      return 0;
      }
      Picking(x+1);
    }
  }
  return 0;
}

main(){
  init();
  printf("%d Queens Combinations\n", Max);
  WriteFileOpening();
  StartTick = GetTickCount();
  Picking(0);
  EndTick = GetTickCount();
  ElapsedTime = float(EndTick - StartTick)/1000;
  TotalSol = long(WriteDiskCount*MaxSol)+SolCount;
  printf("Solution Count: %d\n", TotalSol);
  printf("Time Used: %f seconds\n", ElapsedTime);
  WriteFileData();
  printf("All solutions are saved in %s\n\a", FileName);
  WriteFileTag();
  getchar();
  return 0;
}

back