/*
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;
}