#include <allinc.h>
#define OMGLOLWTFBBQ 1337
//#define BOARD_ROWS 23
//#define BOARD_COLS 79
//#define BOMB_COUNT 200
#define DENY_NONZERO 1 //leave this at 1
#define DISPLAY_ENABLED 1
#define PAUSE_BETWEEN_MOVES 1
#define BORDER 1
#define ORIGINAL 0 //user-input data
#define USE_R4 0
#define SHOW_R4 0 //show R4's temp lists
#define SHOW_MISS 1

//Goal: allows user to control minesweeper game played by submain, through main

//Features
//submain allows main to play a game by passing parameters, then returns
//data to be used in statistical analysis
//child of minekiller2.cpp

//v.3: Border is eliminated in this version.
//v.4: starts again from different location if it fails
//v.5: Top two (decisive) rules of R4 have been implemented.
//v.6: Allows user input
//v.7: radical changes

int BOARD_ROWS;
int BOARD_COLS;
int BOMB_COUNT;
apstring targetfilename;

struct _tile
{
	int status;//0~8 number behind marker
	bool bomb;//1 = contains a bomb
   bool flagged;//1 = marked as a bomb
   //bool hidden;//0 = uncovered, show STATUS
   bool cleared;//NEW V.7: all tiles are uncovered, but no mines are shown
};

struct _parcel
//for use with returning data from submain
{
   int  moves;
   bool clear;
};

struct _movelist
{
	apvector <int> ar;
   int index;
};

_parcel submain(int,int,int);
void initialize(apmatrix <_tile> &);
void plantbombs(apmatrix <_tile> &);
void showboard(apmatrix <_tile> &);
//_movelist getmove(apmatrix <_tile> &); //no longer necessary in v.7
bool nextmove(apmatrix <_tile> &);
void clearzeroes(apmatrix <_tile> &);
void clearpalm(apmatrix <_tile> &, int, int); //changed from napalm, v.7
void flagpalm(apmatrix <_tile> &, int, int);
int  countflags(apmatrix <_tile> &, int, int);
int  countunmarked(apmatrix <_tile> &, int, int);
double gettime();
bool r4(apmatrix <_tile> &);
//inline bool r4(apmatrix <_tile> &) {return false;}; //dummy for v.7
int r4_sum(apvector <int> &, bool);
int r4_count(apvector <int> &, int);
int minesleft(apmatrix <_tile> &);

void main()
{
	randomize();
	int counter=0;
   int i,j,k,h;
   _parcel temp;

   if(ORIGINAL)
   {
   	cout<<"Target filename: ";
      getline(cin,targetfilename);
   }

   ofstream ouf;
   ouf.open("minekiller7results.xls");
   ouf<<"ROW\tCOL\tMINES\tWINS\tTRIES\tAVG.LENGTH\tTOTALTIMETAKEN\n";

   int stepcount;
   int CYCLECOUNT=100;
   if(!ORIGINAL)
   {
	   for(i=10; i<=100; i+=1)//number of rows
	   for(j=i; j<=i; j+=1)//number of cols
	   for(k=i*i/2; k<=i*i/2; k+=100)//number of mines
	   {
	   	counter=0;//counts up victories
	      stepcount=0;//number of moves taken by victory
	      double before=gettime();
			for(h=0; h<CYCLECOUNT; h++)
			{
	         temp=submain(i,j,k);
	         if(temp.clear)
	         {
	         	counter++;
	            stepcount+=temp.moves;
	         }
			}
	      if(counter==0) {stepcount=0; counter=-1;}//prevents div.zero
	      ouf<<i<<"\t"<<j<<"\t"<<k<<'\t'<<counter<<'\t'<<h<<'\t'<<stepcount/double(counter)<<'\t'<<gettime()-before<<endl;
	     cout<<i<<"\t"<<j<<"\t"<<k<<'\t'<<counter<<'\t'<<h<<'\t'<<stepcount/double(counter)<<'\t'<<gettime()-before<<endl;
	   }
   }
   else
   {
   	ifstream inf;
      inf.open(targetfilename.c_str());
      inf>>i>>j; k=0; char temps;
      for(int q=0; q<i*j; q++)
      {//quickly get mine count
      	inf>>temps;
         if(temps=='B' || temps=='b')
         	k++;
      }
	   counter=0;//counts up victories
	   stepcount=0;//number of moves taken by victory
	   double before=gettime();
		for(h=0; h<1; h++)
		{
	      temp=submain(i,j,k);
	      if(temp.clear)
	      {
	        	counter++;
	         stepcount+=temp.moves;
	      }
		}
	   if(counter==0) {stepcount=0; counter=-1;}//prevents div.zero
	    ouf<<i<<"x"<<j<<"m"<<k<<'\t'<<counter<<'\t'<<h<<'\t'<<stepcount/double(counter)<<'\t'<<gettime()-before<<endl;
	   cout<<i<<"x"<<j<<"m"<<k<<'\t'<<counter<<'\t'<<h<<'\t'<<stepcount/double(counter)<<'\t'<<gettime()-before<<endl;
   }


   cout<<"\nDone";
   getch();
}
_parcel submain(int BOARD_ROWS_, int BOARD_COLS_, int BOMB_COUNT_)
//Use: plays a game with given parameters
//Args: temp values for rows, cols, and bomb count, which are placed into globals
//Returns: _parcel type: cleared status, number of moves taken.
{
	if(DISPLAY_ENABLED)
	   clrscr();
	BOARD_ROWS=BOARD_ROWS_;
   BOARD_COLS=BOARD_COLS_;
   BOMB_COUNT=BOMB_COUNT_;
	bool repeat;
	apmatrix <_tile> board (BOARD_ROWS,BOARD_COLS);
   _movelist movelist;
   if(!ORIGINAL)
   {
	   initialize(board);
	   plantbombs(board);
		//make initial move
	   //movelist=getmove(board); //deprecated
	   /*
      if(!board[0][0].hidden && (board[0][0].status!=0 || board[0][0].bomb))
	   {//0,0 is uncovered and not zero- sign that this board fails
		   if(DISPLAY_ENABLED)
		   {
	      	cout<<"\nNo opening moves.     ";
			   getch();
		   }
		   _parcel ret;
		   ret.moves=0;
		   ret.clear=false;
		   return ret;
	   }
      *///not sure if I need any of this
   }
   else
   {
   	initialize(board);
		ifstream inf;
      inf.open(targetfilename.c_str());
      int nt;
      char ch;
      inf>>nt>>nt; //get rid of parameter data
      for(int i=0; i<BOARD_ROWS*BOARD_COLS; i++)
      {
      	inf>>ch;
         if(ch=='B' || ch=='b')//bomb
	         board[i/BOARD_COLS][i%BOARD_COLS].bomb=1;
         //increment status numbers in legal adjacent squares
         //use original temp values, 'cause I'm super lazy
         if(board[i/BOARD_COLS][i%BOARD_COLS].bomb==1)
         {
	         int a=i, c=BOARD_COLS, r=BOARD_ROWS;
		      if(BORDER)
		      {
		         if(0<=a/c-1 && 0<=a%c-1) board[a/c-1][a%c-1].status++;
		         if(0<=a/c-1            ) board[a/c-1][a%c  ].status++;
		         if(0<=a/c-1 && a%c+1< c) board[a/c-1][a%c+1].status++;
		         if(            0<=a%c-1) board[a/c  ][a%c-1].status++;
		         if(            a%c+1< c) board[a/c  ][a%c+1].status++;
		         if(a/c+1< r && 0<=a%c-1) board[a/c+1][a%c-1].status++;
		         if(a/c+1< r            ) board[a/c+1][a%c  ].status++;
		         if(a/c+1< r && a%c+1< c) board[a/c+1][a%c+1].status++;
		      }
		      else
		      {//increment status numbers in ALL adjacent squares
				   board[((a/c-1)+r)%r][((a%c-1)+c)%c].status++;
				   board[((a/c-1)+r)%r][a%c          ].status++;
				   board[((a/c-1)+r)%r][(a%c+1)%c    ].status++;
				   board[a/c          ][((a%c-1)+c)%c].status++;
				   board[a/c          ][(a%c+1)%c    ].status++;
				   board[(a/c+1)%r    ][((a%c-1)+c)%c].status++;
				   board[(a/c+1)%r    ][a%c          ].status++;
				   board[(a/c+1)%r    ][(a%c+1)%c    ].status++;
		      }
         }
      }
      /*for(int i=0; i<BOARD_ROWS*BOARD_COLS; i++)
      {
      	inf>>ch;
         if(ch!='.')//hidden
	         board[i/BOARD_COLS][i%BOARD_COLS].hidden=0;
         board[i/BOARD_COLS][i%BOARD_COLS].flagged=0;//no flags to start with
      }*///not needed in v.7
   }
   clearzeroes(board);
   if(DISPLAY_ENABLED)
	   showboard(board);
   bool allcleared;
   int x=1;
   do
   {
      x++;
      if(PAUSE_BETWEEN_MOVES)
	   	getch();

      //make next move
	   repeat=nextmove(board);
	   //clearzeroes(board);
      if(DISPLAY_ENABLED)
      {
		   showboard(board);
	      cout<<"Moves: "<<x<<" Mines left: "<<minesleft(board)<<"  ";
      }

      //check if cleared, if so, break loop
	   allcleared=true;
	   for(int i=0; i<board.numrows(); i++)
	   for(int j=0; j<board.numcols(); j++)
	   	if(!board[i][j].cleared && !board[i][j].flagged)
	      	allcleared=false;

      if(!repeat && !allcleared && USE_R4) //if you're about to give up, try r4.
         if(r4(board))
         {//if you find something, check for clear, and then turn repeat back on.
         	//check if cleared, if so, break loop
			   allcleared=true;
			   for(int i=0; i<board.numrows(); i++)
			   for(int j=0; j<board.numcols(); j++)
			   	if(!board[i][j].cleared && !board[i][j].flagged)
			      	allcleared=false;
            repeat=true;
            if(DISPLAY_ENABLED)
	            cout<<"\nR4 USED ";
         }
         else
         {
            if(DISPLAY_ENABLED)
	            cout<<"\nR4 FAILED ";
         }

      /*if(!repeat && !cleared && movelist.index<movelist.ar.length() && !ORIGINAL)
	   {//try another index, NOT FOR USE WITH ORIGINAL BOARDS
      	int aa,ii,jj;//temps
         do
         {
         	aa=movelist.ar[movelist.index];
	         ii=aa/board.numcols();
	         jj=aa%board.numcols();
            movelist.index++;
         }while((board[ii][jj].bomb || board[ii][jj].status!=0) && movelist.index<movelist.ar.length());

         if(!movelist.index<movelist.ar.length())
         {
         	for(int kk=0; kk<board.numrows(); kk++)
            for(int ll=0; ll<board.numcols(); ll++)
            {
            	board[kk][ll].hidden=1;
               board[kk][ll].flagged=0;
            }
            board[ii][jj].hidden=0;
            clearzeroes(board);
            x=1;
			   if(DISPLAY_ENABLED)
				   showboard(board);
            repeat=true;
			   if(DISPLAY_ENABLED)
	            cout<<"Retrying.        ";
         }
		}*///movelist has been disabled in v.7
   }while(repeat && !allcleared);

   //verification process
   if(allcleared)
   {
   	for(int p=0; p<board.numrows(); p++)
      for(int q=0; q<board.numcols(); q++)
      	if((board[p][q].cleared && board[p][q].bomb) || (!board[p][q].bomb && board[p][q].flagged))
         	allcleared=false;//deny cleared if a bomb is uncovered or a clear tile is flagged
   }
   if(!DISPLAY_ENABLED && SHOW_MISS && allcleared==false)
   {
      clrscr();
   	showboard(board);
	   cout<<"\nFailed...\n";
      getch();
   }
   if(DISPLAY_ENABLED)
   {
	   if(!allcleared)
		   cout<<"\nFailed...      ";
	   else
	   	cout<<"\nCLEARED!       ";
	   getch();
   }
   _parcel ret;
   ret.moves=x;
   ret.clear=allcleared;

   return ret;
}

void initialize(apmatrix <_tile> &board)
//Use: stores initial values into undefined values in each tile
//Args: board to be initialized, of type _tile
//Notes: status=0, bomb=0, flagged=0, hidden=1
{
	for(int i=0; i<board.numrows(); i++)
   for(int j=0; j<board.numcols(); j++)
   {
   	board[i][j].status=0;
      board[i][j].bomb=0;
      board[i][j].flagged=0;
      //board[i][j].hidden=1;
      board[i][j].cleared=0; //added in v.7
   }
}

void plantbombs(apmatrix <_tile> &board)
//Use: determine which positions are to have bombs, then mark off
//     status values of others
//Args: board to be planted, of type _tile
{
   //creates an indepent list of tile indices- 0 to ROW*COL-1
	apvector <int> tiles(board.numrows()*board.numcols());
   for(int i=0; i<tiles.length(); i++)
   	tiles[i]=i;

   //shuffles list, double swap-pass method
   for(int h=1; h<=2; h++)
   for(int i=0; i<tiles.length(); i++)
   {
   	int target=rand()%tiles.length();
      int temp=tiles[target];
      tiles[target]=tiles[i];
      tiles[i]=temp;
   }

   //assign bombs to indicies given starting at the front of tiles[]
   for(int i=0; i<BOMB_COUNT; i++)
    	if(i<tiles.length())//make sure there are no excess bombs
      {
      	int a=tiles[i];        //symbolic temps
         int r=board.numrows();
         int c=board.numcols();
         board[a/c][a%c].bomb=1; //set up us the bomb!

         //increment status numbers in legal adjacent squares
         if(BORDER)
         {
	         if(0<=a/c-1 && 0<=a%c-1) board[a/c-1][a%c-1].status++;
	         if(0<=a/c-1            ) board[a/c-1][a%c  ].status++;
	         if(0<=a/c-1 && a%c+1< c) board[a/c-1][a%c+1].status++;
	         if(            0<=a%c-1) board[a/c  ][a%c-1].status++;
	         if(            a%c+1< c) board[a/c  ][a%c+1].status++;
	         if(a/c+1< r && 0<=a%c-1) board[a/c+1][a%c-1].status++;
	         if(a/c+1< r            ) board[a/c+1][a%c  ].status++;
	         if(a/c+1< r && a%c+1< c) board[a/c+1][a%c+1].status++;
         }
         else
         {//increment status numbers in ALL adjacent squares
			   board[((a/c-1)+r)%r][((a%c-1)+c)%c].status++;
			   board[((a/c-1)+r)%r][a%c          ].status++;
			   board[((a/c-1)+r)%r][(a%c+1)%c    ].status++;
			   board[a/c          ][((a%c-1)+c)%c].status++;
			   board[a/c          ][(a%c+1)%c    ].status++;
			   board[(a/c+1)%r    ][((a%c-1)+c)%c].status++;
			   board[(a/c+1)%r    ][a%c          ].status++;
			   board[(a/c+1)%r    ][(a%c+1)%c    ].status++;
         }
      }
}

void showboard(apmatrix <_tile> &board)
//Use: displays board so far.
{
	//clrscr();
   gotoxy(1,1);
	for(int i=0; i<board.numrows(); i++)
   {
   	for(int j=0; j<board.numcols(); j++)
         if(board[i][j].bomb && board[i][j].flagged)
           	cout<<"M";//marked bomb
         else if(!board[i][j].bomb && board[i][j].flagged)
         	cout<<"F";//false bomb
      	//else if(board[i][j].hidden)
         	//cout<<".";//hidden
         else if(board[i][j].bomb && !board[i][j].flagged)
         	if(board[i][j].cleared)
		      	cout<<board[i][j].status;//bomb
         	else
		      	cout<<char(board[i][j].status+0x60);//bomb
         else
         	if(board[i][j].cleared)
		      	cout<<board[i][j].status;//no bomb
         	else
		      	cout<<char(board[i][j].status+0x60);//no bomb
      cout<<endl;
   }
}

void clearzeroes(apmatrix <_tile> &board)
//Use: "explodes" any zero tiles, like in the game. Automatically clears
//     all 3/5/8 blocks around a zero.
{
	bool repeat;//tells loop that it has found an exploded a zero, and to go
               //back around and check if that made any more zeroes.
	do
   {
   	repeat=false;
		for(int i=0; i<board.numrows(); i++)
	   for(int j=0; j<board.numcols(); j++)
	   	if(board[i][j].status==0 && countunmarked(board,i,j)>0)
	      {//if spot shows a zero and has non-clear tiles around it...
         	repeat=true; //repeat after checking
            clearpalm(board,i,j); //bomb it
	      }
   }while(repeat);
}

void clearpalm(apmatrix <_tile> &board, int i, int j)
//Use: Unhides all tiles in vicinity that are not marked.
//Args: board, and location to napalm
//Note: Changed from napalm for v.7
{
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location
           
   if(!BORDER)
   {
	   if(!board[((a/c-1)+r)%r][((a%c-1)+c)%c].flagged) {board[((a/c-1)+r)%r][((a%c-1)+c)%c].cleared=1;}
	   if(!board[((a/c-1)+r)%r][a%c          ].flagged) {board[((a/c-1)+r)%r][a%c          ].cleared=1;}
	   if(!board[((a/c-1)+r)%r][(a%c+1)%c    ].flagged) {board[((a/c-1)+r)%r][(a%c+1)%c    ].cleared=1;}
	   if(!board[a/c          ][((a%c-1)+c)%c].flagged) {board[a/c          ][((a%c-1)+c)%c].cleared=1;}
	   if(!board[a/c          ][(a%c+1)%c    ].flagged) {board[a/c          ][(a%c+1)%c    ].cleared=1;}
	   if(!board[(a/c+1)%r    ][((a%c-1)+c)%c].flagged) {board[(a/c+1)%r    ][((a%c-1)+c)%c].cleared=1;}
	   if(!board[(a/c+1)%r    ][a%c          ].flagged) {board[(a/c+1)%r    ][a%c          ].cleared=1;}
	   if(!board[(a/c+1)%r    ][(a%c+1)%c    ].flagged) {board[(a/c+1)%r    ][(a%c+1)%c    ].cleared=1;}
   }
   else
	//check nearby positions and uncover them
	{
	   if(0<=a/c-1 && 0<=a%c-1) if(!board[a/c-1][a%c-1].flagged) {board[a/c-1][a%c-1].cleared=1;}
	   if(0<=a/c-1            ) if(!board[a/c-1][a%c  ].flagged) {board[a/c-1][a%c  ].cleared=1;}
	   if(0<=a/c-1 && a%c+1< c) if(!board[a/c-1][a%c+1].flagged) {board[a/c-1][a%c+1].cleared=1;}
	   if(            0<=a%c-1) if(!board[a/c  ][a%c-1].flagged) {board[a/c  ][a%c-1].cleared=1;}
	   if(            a%c+1< c) if(!board[a/c  ][a%c+1].flagged) {board[a/c  ][a%c+1].cleared=1;}
	   if(a/c+1< r && 0<=a%c-1) if(!board[a/c+1][a%c-1].flagged) {board[a/c+1][a%c-1].cleared=1;}
	   if(a/c+1< r            ) if(!board[a/c+1][a%c  ].flagged) {board[a/c+1][a%c  ].cleared=1;}
	   if(a/c+1< r && a%c+1< c) if(!board[a/c+1][a%c+1].flagged) {board[a/c+1][a%c+1].cleared=1;}
   }
}

void flagpalm(apmatrix <_tile> &board, int i, int j)
//Use: Flags all tiles in vicinity that are hidden
//Args: board, and location to flagpalm
{
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   if(!BORDER)
   {
	   if(!board[((a/c-1)+r)%r][((a%c-1)+c)%c].cleared && !board[((a/c-1)+r)%r][((a%c-1)+c)%c].flagged) {board[((a/c-1)+r)%r][((a%c-1)+c)%c].flagged=1;}
	   if(!board[((a/c-1)+r)%r][a%c          ].cleared && !board[((a/c-1)+r)%r][a%c          ].flagged) {board[((a/c-1)+r)%r][a%c          ].flagged=1;}
	   if(!board[((a/c-1)+r)%r][(a%c+1)%c    ].cleared && !board[((a/c-1)+r)%r][(a%c+1)%c    ].flagged) {board[((a/c-1)+r)%r][(a%c+1)%c    ].flagged=1;}
	   if(!board[a/c          ][((a%c-1)+c)%c].cleared && !board[a/c          ][((a%c-1)+c)%c].flagged) {board[a/c          ][((a%c-1)+c)%c].flagged=1;}
	   if(!board[a/c          ][(a%c+1)%c    ].cleared && !board[a/c          ][(a%c+1)%c    ].flagged) {board[a/c          ][(a%c+1)%c    ].flagged=1;}
	   if(!board[(a/c+1)%r    ][((a%c-1)+c)%c].cleared && !board[(a/c+1)%r    ][((a%c-1)+c)%c].flagged) {board[(a/c+1)%r    ][((a%c-1)+c)%c].flagged=1;}
	   if(!board[(a/c+1)%r    ][a%c          ].cleared && !board[(a/c+1)%r    ][a%c          ].flagged) {board[(a/c+1)%r    ][a%c          ].flagged=1;}
	   if(!board[(a/c+1)%r    ][(a%c+1)%c    ].cleared && !board[(a/c+1)%r    ][(a%c+1)%c    ].flagged) {board[(a/c+1)%r    ][(a%c+1)%c    ].flagged=1;}
   }
   //check nearby positions and flag them
   else
   {
	   if(0<=a/c-1 && 0<=a%c-1) if(!board[a/c-1][a%c-1].cleared && !board[a/c-1][a%c-1].flagged) {board[a/c-1][a%c-1].flagged=1;}
	   if(0<=a/c-1            ) if(!board[a/c-1][a%c  ].cleared && !board[a/c-1][a%c  ].flagged) {board[a/c-1][a%c  ].flagged=1;}
	   if(0<=a/c-1 && a%c+1< c) if(!board[a/c-1][a%c+1].cleared && !board[a/c-1][a%c+1].flagged) {board[a/c-1][a%c+1].flagged=1;}
	   if(            0<=a%c-1) if(!board[a/c  ][a%c-1].cleared && !board[a/c  ][a%c-1].flagged) {board[a/c  ][a%c-1].flagged=1;}
	   if(            a%c+1< c) if(!board[a/c  ][a%c+1].cleared && !board[a/c  ][a%c+1].flagged) {board[a/c  ][a%c+1].flagged=1;}
	   if(a/c+1< r && 0<=a%c-1) if(!board[a/c+1][a%c-1].cleared && !board[a/c+1][a%c-1].flagged) {board[a/c+1][a%c-1].flagged=1;}
	   if(a/c+1< r            ) if(!board[a/c+1][a%c  ].cleared && !board[a/c+1][a%c  ].flagged) {board[a/c+1][a%c  ].flagged=1;}
	   if(a/c+1< r && a%c+1< c) if(!board[a/c+1][a%c+1].cleared && !board[a/c+1][a%c+1].flagged) {board[a/c+1][a%c+1].flagged=1;}
   }
}

bool nextmove(apmatrix <_tile> &board)
//Use: sequentially checks each tile for potential moves.
{
	int unmarkedcount;
	for(int i=0; i<board.numrows(); i++)
   for(int j=0; j<board.numcols(); j++)
   	if(1)//always check in v.7 //!board[i][j].hidden) //ignore tile if it's hidden
   	{
	   	unmarkedcount=countunmarked(board,i,j);
	      if(unmarkedcount>0) //ignore if there's nothing unmarked around it
         {
		   	int flagcount=countflags(board,i,j);
            if(flagcount+unmarkedcount==board[i][j].status)
            {
            	flagpalm(board,i,j);
               return true;
            }
	         if(flagcount==board[i][j].status)
            {
            	clearpalm(board,i,j);
               return true;
            }
	      }
      }
   return false;
}

int countflags(apmatrix <_tile> &board, int i, int j)
//Use: counts marked bombs in nearby area
//Args: board, location around which to check
//Returns: number of flags in vicinity
{
	int markcount=0; //returned value
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   if(!BORDER)
   {
	   if(board[((a/c-1)+r)%r][((a%c-1)+c)%c].flagged) {markcount++;}
	   if(board[((a/c-1)+r)%r][a%c          ].flagged) {markcount++;}
	   if(board[((a/c-1)+r)%r][(a%c+1)%c    ].flagged) {markcount++;}
	   if(board[a/c          ][((a%c-1)+c)%c].flagged) {markcount++;}
	   if(board[a/c          ][(a%c+1)%c    ].flagged) {markcount++;}
	   if(board[(a/c+1)%r    ][((a%c-1)+c)%c].flagged) {markcount++;}
	   if(board[(a/c+1)%r    ][a%c          ].flagged) {markcount++;}
	   if(board[(a/c+1)%r    ][(a%c+1)%c    ].flagged) {markcount++;}
   }
   else
   {
	   if(0<=a/c-1 && 0<=a%c-1) if(board[a/c-1][a%c-1].flagged) {markcount++;}
	   if(0<=a/c-1            ) if(board[a/c-1][a%c  ].flagged) {markcount++;}
	   if(0<=a/c-1 && a%c+1< c) if(board[a/c-1][a%c+1].flagged) {markcount++;}
	   if(            0<=a%c-1) if(board[a/c  ][a%c-1].flagged) {markcount++;}
	   if(            a%c+1< c) if(board[a/c  ][a%c+1].flagged) {markcount++;}
	   if(a/c+1< r && 0<=a%c-1) if(board[a/c+1][a%c-1].flagged) {markcount++;}
	   if(a/c+1< r            ) if(board[a/c+1][a%c  ].flagged) {markcount++;}
	   if(a/c+1< r && a%c+1< c) if(board[a/c+1][a%c+1].flagged) {markcount++;}
   }
   return markcount;
}

int countunmarked(apmatrix <_tile> &board, int i, int j)
//Use: counts unmarked tiles in nearby area
//Args: board, location around which to check
//Returns: number of non-cleared, non-flagged tiles in vicinity
{
	int markcount=0; //returned value
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   if(!BORDER)
	{
	   if(!board[((a/c-1)+r)%r][((a%c-1)+c)%c].cleared && !board[((a/c-1)+r)%r][((a%c-1)+c)%c].flagged) {markcount++;}
	   if(!board[((a/c-1)+r)%r][a%c          ].cleared && !board[((a/c-1)+r)%r][a%c          ].flagged) {markcount++;}
	   if(!board[((a/c-1)+r)%r][(a%c+1)%c    ].cleared && !board[((a/c-1)+r)%r][(a%c+1)%c    ].flagged) {markcount++;}
	   if(!board[a/c          ][((a%c-1)+c)%c].cleared && !board[a/c          ][((a%c-1)+c)%c].flagged) {markcount++;}
	   if(!board[a/c          ][(a%c+1)%c    ].cleared && !board[a/c          ][(a%c+1)%c    ].flagged) {markcount++;}
	   if(!board[(a/c+1)%r    ][((a%c-1)+c)%c].cleared && !board[(a/c+1)%r    ][((a%c-1)+c)%c].flagged) {markcount++;}
	   if(!board[(a/c+1)%r    ][a%c          ].cleared && !board[(a/c+1)%r    ][a%c          ].flagged) {markcount++;}
	   if(!board[(a/c+1)%r    ][(a%c+1)%c    ].cleared && !board[(a/c+1)%r    ][(a%c+1)%c    ].flagged) {markcount++;}
   }
   else
   {
	   if(0<=a/c-1 && 0<=a%c-1) if(!board[a/c-1][a%c-1].cleared && !board[a/c-1][a%c-1].flagged) {markcount++;}
	   if(0<=a/c-1            ) if(!board[a/c-1][a%c  ].cleared && !board[a/c-1][a%c  ].flagged) {markcount++;}
	   if(0<=a/c-1 && a%c+1< c) if(!board[a/c-1][a%c+1].cleared && !board[a/c-1][a%c+1].flagged) {markcount++;}
	   if(            0<=a%c-1) if(!board[a/c  ][a%c-1].cleared && !board[a/c  ][a%c-1].flagged) {markcount++;}
	   if(            a%c+1< c) if(!board[a/c  ][a%c+1].cleared && !board[a/c  ][a%c+1].flagged) {markcount++;}
	   if(a/c+1< r && 0<=a%c-1) if(!board[a/c+1][a%c-1].cleared && !board[a/c+1][a%c-1].flagged) {markcount++;}
	   if(a/c+1< r            ) if(!board[a/c+1][a%c  ].cleared && !board[a/c+1][a%c  ].flagged) {markcount++;}
	   if(a/c+1< r && a%c+1< c) if(!board[a/c+1][a%c+1].cleared && !board[a/c+1][a%c+1].flagged) {markcount++;}
   }
   return markcount;
}

double gettime()
//Use: Returns the number of seconds that have passed since midnight, 1st
//     January 1970 GMT (or 6pm, 31st December 1969 CST).
//Args: None
//Returns: current time
//Note: Is a very large number **EDITED: now uses clock() which returns ms.
{
   time_t t=clock();
 	double t1=t;
 	return t1/1000;
}

bool r4(apmatrix <_tile> &board)
//Use: tries to determine any mined/clear tiles using systems of equations
//Args: Entire board, by reference.
//Returns: TRUE if any tiles can be determined, FALSE if none can.
//Note: Does not check for Rules 3 and 4, which suggest two solutions exist.
//Procedure: automatically looks at all tiles with at least one not-clear-not-flagged,
// non-flagged neighbor and adds them to list, total = status - flagcount
{
	//make matrix, with enough space to assign values to all tiles, plus one
   //for the total
	apmatrix <int> matrix(1,board.numrows()*board.numcols()+1);
   matrix[0][matrix.numcols()-1]=0;
   for(int i=0; i<board.numrows(); i++)
   for(int j=0; j<board.numcols(); j++)
   {	//tally for all unaccounted tiles: mark 1 if hidden, and not flagged.
   	matrix[0][i*board.numcols()+j]=(1-board[i][j].cleared)*(1-board[i][j].flagged);
      //increment unaccounted mine total by 1 if hidden, not flagged, and a bomb.
      matrix[0][matrix.numcols()-1]+=(1-board[i][j].cleared)*board[i][j].bomb*(1-board[i][j].flagged);
   }
   int r=board.numrows(), c=board.numcols(); //placeholder temps

   //set up matrix
   cout<<endl;
   for(int i=0; i<board.numrows(); i++)
   for(int j=0; j<board.numcols(); j++)
   {
		if(countunmarked(board,i,j)>board[i][j].status)
      {  //add a line, initialize
      	matrix.resize(matrix.numrows()+1,matrix.numcols());
         for(int k=0; k<matrix.numcols(); k++)
         	matrix[matrix.numrows()-1][k]=0;

         if(SHOW_R4)
         	cout<<"M#"<<matrix.numrows()-1<<" ("<<i<<","<<j<<")"<<endl;

         //assign status-flagcount to final element
         matrix[matrix.numrows()-1][matrix.numcols()-1]=board[i][j].status-countflags(board,i,j);

         //assign 1 to neighboring tiles that are unclear and unflagged
         if(!BORDER)
         {
	         if(board[((i-1)+r)%r][((j-1)+c)%c].cleared==0 && board[((i-1)+r)%r][((j-1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i-1)+r)%r*c+((j-1)+c)%c]=1;
	         if(board[((i-1)+r)%r][((j-0)+c)%c].cleared==0 && board[((i-1)+r)%r][((j-0)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i-1)+r)%r*c+((j-0)+c)%c]=1;
	         if(board[((i-1)+r)%r][((j+1)+c)%c].cleared==0 && board[((i-1)+r)%r][((j+1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i-1)+r)%r*c+((j+1)+c)%c]=1;
	         if(board[((i-0)+r)%r][((j-1)+c)%c].cleared==0 && board[((i-0)+r)%r][((j-1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i-0)+r)%r*c+((j-1)+c)%c]=1;
	         if(board[((i-0)+r)%r][((j+1)+c)%c].cleared==0 && board[((i-0)+r)%r][((j+1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i-0)+r)%r*c+((j+1)+c)%c]=1;
	         if(board[((i+1)+r)%r][((j-1)+c)%c].cleared==0 && board[((i+1)+r)%r][((j-1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i+1)+r)%r*c+((j-1)+c)%c]=1;
	         if(board[((i+1)+r)%r][((j-0)+c)%c].cleared==0 && board[((i+1)+r)%r][((j-0)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i+1)+r)%r*c+((j-0)+c)%c]=1;
	         if(board[((i+1)+r)%r][((j+1)+c)%c].cleared==0 && board[((i+1)+r)%r][((j+1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i+1)+r)%r*c+((j+1)+c)%c]=1;
         }
      	else
         {
         	if(0<i && 0<j)
  	         if(board[((i-1)+r)%r][((j-1)+c)%c].cleared==0 && board[((i-1)+r)%r][((j-1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i-1)+r)%r*c+((j-1)+c)%c]=1;
            if(0<i)
	         if(board[((i-1)+r)%r][((j-0)+c)%c].cleared==0 && board[((i-1)+r)%r][((j-0)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i-1)+r)%r*c+((j-0)+c)%c]=1;
            if(0<i && j<c)
	         if(board[((i-1)+r)%r][((j+1)+c)%c].cleared==0 && board[((i-1)+r)%r][((j+1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i-1)+r)%r*c+((j+1)+c)%c]=1;
            if(0<j)
	         if(board[((i-0)+r)%r][((j-1)+c)%c].cleared==0 && board[((i-0)+r)%r][((j-1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i-0)+r)%r*c+((j-1)+c)%c]=1;
            if(0<c)
	         if(board[((i-0)+r)%r][((j+1)+c)%c].cleared==0 && board[((i-0)+r)%r][((j+1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i-0)+r)%r*c+((j+1)+c)%c]=1;
            if(i<r && 0<j)
	         if(board[((i+1)+r)%r][((j-1)+c)%c].cleared==0 && board[((i+1)+r)%r][((j-1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i+1)+r)%r*c+((j-1)+c)%c]=1;
            if(i<r)
	         if(board[((i+1)+r)%r][((j-0)+c)%c].cleared==0 && board[((i+1)+r)%r][((j-0)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i+1)+r)%r*c+((j-0)+c)%c]=1;
            if(i<r && j<c)
	         if(board[((i+1)+r)%r][((j+1)+c)%c].cleared==0 && board[((i+1)+r)%r][((j+1)+c)%c].flagged==0)
	         	matrix[matrix.numrows()-1][((i+1)+r)%r*c+((j+1)+c)%c]=1;
         }
      }
   }

   apvector <int> temp(matrix.numcols());
   //begin checking for useful data, storing temporary values in temp[]
   for(int i=0; i<matrix.numrows(); i++)
   for(int j=0; j<matrix.numrows(); j++)
   {
   	if(i!=j) //two different rows
      {
	   	for(int k=0; k<matrix.numcols(); k++)
	      	temp[k]=matrix[i][k]-matrix[j][k];

         if(SHOW_R4)
         {
         	cout<<"("<<i<<"-"<<j<<")";
		   	for(int k=0; k<matrix.numcols()-1; k++)
            	if(temp[k]>=0)
			      	cout<<setw(2)<<temp[k];
               else
               	cout<<temp[k];
            cout<<"| "<<temp[temp.length()-1]<<endl;
            getch();
         }

	   	//Rule 1a: if number of +1's = total, then all +1's are mined
	      if(r4_count(temp,1)==temp[temp.length()-1] && r4_sum(temp,1)!=0)
         {
	         if(1)
	         {
            	cout<<endl;
	         	cout<<"("<<i<<"-"<<j<<")";
			   	for(int k=0; k<matrix.numcols()-1; k++)
	            	if(temp[k]>=0)
				      	cout<<setw(2)<<temp[k];
	               else
	               	cout<<temp[k];
	            cout<<"| "<<temp[temp.length()-1]<<endl;
         	}
         	for(int k=0; k<temp.length()-1; k++)
            	if(temp[k]==1)
               	board[k/c][k%c].flagged=1;
            if(SHOW_R4)
            	cout<<"[OK]";
            return true;
         }
         //Rule 1b: if number of -1's = -total, then all -1's are mined
	      if(r4_count(temp,-1)==abs(temp[temp.length()-1]) && r4_sum(temp,1)!=0)
         {
         	for(int k=0; k<temp.length()-1; k++)
            	if(temp[k]==-1)
               	board[k/c][k%c].flagged=1;
            if(SHOW_R4)
            	cout<<"[OK]";
            return true;
         }


         //Rule 2: all remaining unknowns are either 1 or -1, and total is 0.
         if(r4_sum(temp,1)==abs(r4_sum(temp,0)) && temp[temp.length()-1]==0)
         {
         	for(int k=0; k<temp.length()-1; k++)
            	if(k!=0)
               	board[k/c][k%c].cleared=1;
            if(SHOW_R4)
            	cout<<"[OK]";
            return true;
         }
      }
   }
   return false;
}

int r4_sum(apvector <int> &equation, bool absolute)
//Use: adds up values in "equation", if abs=true, adds up abs. values.
//Args: matrix, row to check, absolute-value-sum toggle
//Returns: sum of row, or sum of absolute values of row
//Notes: for use with R4 logic
{
	int ret=0;
	for(int i=0; i<equation.length()-1; i++) //don't add up final box!
   	if(absolute)
      	ret+=abs(equation[i]);
      else
      	ret+=equation[i];
   return ret;
}
int r4_count(apvector <int> &equation, int target)
{
	int ret=0;
   for(int i=0; i<equation.length()-1; i++)
   	if(equation[i]==target)
      	ret++;
   return ret;
}


int minesleft(apmatrix <_tile> &board)
{
	int ret=0;
	for(int i=0; i<board.numrows(); i++)
   for(int j=0; j<board.numcols(); j++)
   	if(board[i][j].bomb && !board[i][j].flagged)
      	ret++;
   return ret;
}