#include <iostream>
#include <iomanip>
using namespace std;
 
#define SIZE 8
 
int board[SIZE][SIZE];                     //board, DX, DY, PRIORITY
const int DX[SIZE] = {-2,-1, 1,2, 2,  1,-1,-2};  //are all global variables
const int DY[SIZE] = { 1, 2, 2,1,-1, -2,-2,-1};
const int PRIORITY[SIZE][SIZE] = { 
				{1,2,2,2,2,2,2,1},
				{2,3,4,4,4,4,3,2},
				{2,4,5,6,6,5,4,2},
				{2,4,6,7,7,6,4,2},
				{2,4,6,7,7,6,4,2},
				{2,4,5,6,6,5,4,2},
				{2,3,4,4,4,4,3,2},
				{1,2,2,2,2,2,2,1},
			};
struct CELL {  //a cell on the board
  int row, col;
};
void display_board() {  //display the board, 0=empty; >0 means occupied
  int i, j;
  for  (i = 0; i < SIZE; i++) 
  {
    for (j = 0; j < SIZE; j++) 
    {
      cout << setw(4) << board[i][j];
    }
    cout << endl;
  }
}
void init() { //board[i][j]==0 means cell (i, j) is empty
  int i, j;
  for  (i = 0; i < SIZE; i++) 
  {
    for (j = 0; j < SIZE; j++) 
    {
      board[i][j] = 0;
    }
  }	
}
bool valid_cell(int row, int col) {  //(row, col) is "valid" if it is inside the board and is empty
     //to be valid row and col should be >=0 and < SIZE
     //also: board[row][col]should be ==0
     //write this code
 
     if ( row < 0 || row >= SIZE )   //checks for row inside the board
     {
        return false;
     }
 
     if ( col < 0 || col >= SIZE )   //checks for column inside the board
     {
        return false;
     }
 
     if ( board[row][col] != 0 )     //checks if cell is empty
     {
        return false; 
     }
 
     else
     {
        return true;             //returns true for valid cells
     } 
}
int next_valid_cells (CELL c, CELL nc[]) { //store the next valid cells in nc array and return the count 
    //go thru all cells: (c.row+DX[i], c.col+DY[i]) i=0 to SIZE-1
    //if it is valid cell put it in nc array
    //and keep trackof how many are there: cnt and return this value
 
    int count = 0;
 
    for ( int i = 0; i < SIZE; i++ )     //loop cycles through the 8 possible moves
       //write the code
    {    
        if ( valid_cell( c.row+DX[i], c.col+DY[i] ) )   //if cell is valid
        {
             nc[count].row = c.row+DX[i];           //assigns valid cell row to nc array
             nc[count].col = c.col+DY[i];           //assigns valid cell column to nc array
             count++;                                //counts number of valid moves
        }
    }
 
    return count;      // returns valid move count
}
 
int bestmove(CELL nc[], int cnt) { //return the index of the best move
	//you know nc[0], nc[1],  nc[cnt-1] hold the valid cells
	//find the cell which has the least priority number
	//and return this index
 
    //complete this code
 
    int best_index, smallest;
 
    if ( cnt == 0 )   //if count is zero, there were no valid moves found
    {
         best_index = -1;
    }
 
    else
    {
        smallest = PRIORITY[nc[0].row][nc[0].col];
 
        for ( int i = 1; i < cnt; i++ )
        {
            if ( PRIORITY[nc[i].row][nc[i].col] < smallest )
            {
                 smallest = PRIORITY[nc[i].row][nc[i].col];
                 best_index = i;
            }
        }
    }
 
    return best_index;
}
 
 
 
int main() {
  int i, j, num, cnt, bestndx;
  CELL cc, nc[SIZE];       //cc=current cell; nc=next cell array
  for ( i = 0; i < SIZE; i++) 
  {
	for (j = 0; j < SIZE; j++) 
    {  //go thru all start positions (i, j)
	  init();  //make board all 0. (all empty)
	  cc.row = i; 
      cc.col = j; 
      num = 1; 
      board[cc.row][cc.col] = num; //put 1 on the start cell
      num++; //increment and keep ready to put the next number
 
 
      while (1) 
      { //keep going as long as you can go or this starting point (i, j)
	    //find next possible moves; 
	      cnt = next_valid_cells(cc, nc);
 
	      cout << "TEST" << endl;
 
	    //find the best move out of all these valid moves
	      bestndx = bestmove(nc, cnt);
 
	      if ( bestndx == -1 )
          {
             break;
          }  //no valid moves; break out of while loop
	    //else put the number on the board and reset current cell to be this new cell and loop back	  
          else 
          {
             board[nc[bestndx].row][nc[bestndx].col] = num; 
             num++;
             cc.row = nc[bestndx].row; cc.col = nc[bestndx].col;
          }
 
	  } //completed for one start position (i, j)
      display_board();
	  if (num < 65) { 
		cout << i <<" " << j << " failed. max entry= " << num - 1 << endl; 
	  }
	  else cout << "SUCCESS!! made all 64 moves from " << i << " " << j << endl;
	}
  }
 
 
  system("pause");
  return 0;
}

    smallest = PRIORITY[nc[0].row][nc[0].col];
 
    for ( int i = 1; i < cnt; i++ )