/*

TSR JANUARY 2003

MALL PROGRAM

 

speed achieved: revisits #48 for first time after 78 seconds on home machine

[6,2] then [5,3]

 

  Being revised to include routine all isolated cells check

 

Part of the magic knights tour series

*/

 

#include <iostream>

#include <iomanip>

#include <fstream>

 

using namespace std;

 

ofstream out1("mall88.txt",ios::out);

 

void init();

int validb(int rowpos,int colpos,int n);

int totcheck(int rowpos,int colpos,int n);

void fixadjcells(int rowpos,int colpos,int flag);

int rccheck(int rowpos,int colpos,int num);

int adjcheck(int rowpos,int colpos,int num);

int moveok(int row,int col);

void displayboard();

void saveboard();

void displayadjboard();

 

int board[9][9];

int adjcellsfree[9][9];

int symrow,symcol=0;

int n,qn,gbn=0;

int lowbnum,highbnum=0;

int lowestnum=64;

int rtot[17][5],ctot[17][5]={0};

int rowmove[9]={0,1,2,2,1,-1,-2,-2,-1};

int colmove[9]={0,2,1,-1,-2,-2,-1,1,2};

 

 

 

int main()

{

      int startrow,startcol,newrow,newcol;

      cout << "STARTING MALL" << endl << endl;

      out1 << "STARTING MALL" << endl << endl;

      lowbnum=1;

      highbnum=64;

//    for (int startrow=1;startrow<=4;startrow++)

//          for (int startcol=1;startcol<=startrow;startcol++)

      startrow=8;

      startcol=8;

            {

                  init();

                  n=highbnum;

                  newrow=startrow;

                  newcol=startcol;

                  board[newrow][newcol]=n;

                        qn=(n+3)/4;

                        if (newrow>4) symrow=9-newrow; else symrow=newrow;

                        if (newcol>4) symcol=9-newcol; else symcol=newcol;

                        rtot[qn][symrow]++;

                        ctot[qn][symcol]++;

                        fixadjcells(newrow,newcol,1);

 

                  while (moveok(startrow,startcol)) {}

            }

      cout << setw(10) << gbn << " magic boards found" << endl;

      cout << endl << "FINISHED MALL" << endl;

      return 0;

}

 

void init()

{

      int row,col,adjrow,adjcol=0;

      for (row=1;row<=8;row++)

            for (col=1;col<=8;col++)

                  board[row][col]=0;

      for (row=1;row<=8;row++)

            for (col=1;col<=8;col++)

            {

                  adjcellsfree[row][col]=0;

                  for (int i=1;i<=8;i++)

                  {

                        adjrow=row+rowmove[i];

                        adjcol=col+colmove[i];

                        if ((adjrow>0)&&(adjrow<=8)&&(adjcol>0)&&(adjcol<=8))

                              adjcellsfree[row][col]++;

                  }

            }

}

 

void displayadjboard()

{

      for (int row=1;row<=8;row++)

      {

            for (int col=1;col<=8;col++)

                  cout << setw(3) << adjcellsfree[row][col];

            cout << endl;

      }

      cout << endl;

 

}

 

int moveok(int row,int col)

{

      int newrow,newcol,ctr=0;

      if (n<=lowbnum)

      {

            gbn++;

            cout << "GBN # " << gbn <<  endl;

            out1 << "GBN # " << gbn <<  endl;      

            displayboard();

            saveboard();

//          cin.get();

            return 0;

      }

      else

      {

            for (ctr=1;ctr<=8;ctr++)

            {

                  newrow=row+rowmove[ctr];

                  newcol=col+colmove[ctr];

                  if (validb(newrow,newcol,n))

                  {

                        n--;

                        board[newrow][newcol]=n;

                        fixadjcells(newrow,newcol,1);

                        qn=(n+3)/4;

                        if (newrow>4) symrow=9-newrow; else symrow=newrow;

                        if (newcol>4) symcol=9-newcol; else symcol=newcol;

                        rtot[qn][symrow]++;

                        ctot[qn][symcol]++;

 

                        if (n==54)

                              {

                              cout << "Revisiting " << n << " at [" <<

                                          newrow << "," << newcol << "]" <<

                                          "   GBN=" << gbn << endl;

                              displayboard();

//                            cin.get();

                              }

 

                        if (!moveok(newrow,newcol))

                        {

                              qn=(n+3)/4;

                              if (newrow>4) symrow=9-newrow; else symrow=newrow;

                              if (newcol>4) symcol=9-newcol; else symcol=newcol;

                              rtot[qn][symrow]--;

                              ctot[qn][symcol]--;

                              n++;

                              board[newrow][newcol]=0;

                              fixadjcells(newrow,newcol,2);

                        }

                  }

            }

            return 0;

      }

}

 

int validb(int rowpos,int colpos,int n)

{

      if ((rowpos<=0)||(rowpos>8)||

            (colpos<=0)||(colpos>8)||

            (board[rowpos][colpos]>0))

            return 0;

      if (!rccheck(rowpos,colpos,n)) return 0;

      if (!totcheck(rowpos,colpos,n)) return 0;

      if (!adjcheck(rowpos,colpos,n)) return 0;

                       

      return 1;

}

 

int totcheck(int rowpos,int colpos,int n)

{

      int totrow,totcol=0;

      int rowfull,colfull=0;

 

      totrow=0;

      rowfull=0;

      for (int c=1;c<=8;c++)

      {

            totrow+=board[rowpos][c];

            if (board[rowpos][c]>0) rowfull++;

      }

      totrow+=n-1;

      if (totrow>260) return 0;

      if ((rowfull==7)&&(totrow<260)) return 0;

      if ((rowfull==6)&&((totrow+(n-3))<260)) return 0;

 

      totcol=0;

      colfull=0;

      for (int r=1;r<=8;r++)

      {

            totcol+=board[r][colpos];

            if (board[r][colpos]>0) colfull++;

      }

      totcol+=n-1;

      if (totcol>260)      return 0;

      if ((colfull==7)&&(totcol<260)) return 0;

      if ((colfull==6)&&((totcol+(n-3))<260)) return 0;

 

      return 1;

}

 

 

 

void fixadjcells(int rowpos,int colpos,int flag)

{

      int adjrow,adjcol=0;

 

      for (int i=1;i<=8;i++)

            {

                  adjrow=rowpos+rowmove[i];

                  adjcol=colpos+colmove[i];

                  if ((adjrow>0)&&(adjrow<=8)&&(adjcol>0)&&(adjcol<=8))

                        if (flag==1) adjcellsfree[adjrow][adjcol]--;

                        else adjcellsfree[adjrow][adjcol]++;

            }

}

 

int adjcheck(int rowpos,int colpos,int num)

{

      int numcells1free=0;

 

      numcells1free=0;

      for (int r=1;r<=8;r++)

            for (int c=1;c<=8;c++)

            {

                  if ((adjcellsfree[r][c]<0)||(adjcellsfree[r][c]>8))

                        cout << "ERROR IN ADJCELLS CALC";

                  if ((board[r][c]==0)&&(adjcellsfree[r][c]==0)&&(num>2)) return 0;

                  if ((board[r][c]==0)&&(adjcellsfree[r][c]==1))

                  {

                        if ((r!=rowpos)||(c!=colpos))

                              numcells1free++;

                  }

                  if (numcells1free>1) return 0;

            }

 

      return 1;

}

 

int rccheck(int rowpos,int colpos,int num)

{

      bool rok,cok=false;

 

      if ((num%4)!=1) return 1;

      qn=(num+3)/4;

      rok=true;

      for (int r=1;r<=4;r++)

            if (rtot[qn][r]!=1) rok=false;

      cok=true;

      for (int c=1;c<=4;c++)

            if (ctot[qn][c]!=1) cok=false;

      if ((rok)||(cok)) return 1; else return 0;

}

 

void displayboard()

{

      int r,c=0;

      for (r=1;r<=8;r++)

            {

                  for (c=1;c<=8;c++)

                  {

                        cout << setw(3) << board[r][c];

                  }

                  cout << endl;

            }

      cout << endl;

}

 

void saveboard()

{

      int r,c=0;

      for (r=1;r<=8;r++)

            {

                  for (c=1;c<=8;c++)

                  {

                        out1 << setw(3) << board[r][c];

                  }

                  out1 << endl;

            }

      out1 << endl;

}