/*

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;

}