#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <fstream.h>

typedef bool bool15[15];        //block out rows and columns
typedef int loc15[15];          //which columns were selected in eahc row?
typedef int table15[15][15];    //hold the distance table

//Procedure to pick 1 game (1 row and 1 column) recursively calls itself
void pick1(table15 t, bool15 b, loc15 loc, int h, int games,int total);
int min;   //hold the grand minimum for each set

int main()
{char fname[25];                      // file name
 ifstream infile;                     // input file
 ofstream outfile;                    // output file
 cout<<"InFile name:";            //get the input file name
 cin>>fname;
 infile.open(fname);
while (infile.fail())              //check the input file
{cout<<fname<<"File error"<<endl;
 cout<<"InFile name:";
 cin>>fname;
 infile.open(fname);
}
 cout<<"Outfilename:";             //open the output file
 cin>>fname;
  outfile.open(fname);

cout<<"Made it past check"<<endl;
 int sets;                         //how many sets in the test file?
 infile>>sets;
cout<<sets<<endl;
 while(sets>0)                     //until we are done with all sets
 {cout<<sets<<endl;
  min=10000;                       //reset the minimum
  int height;                      // hieght and width of the array
  table15 t;                       //hold the distances array
  bool15 b={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};        // mark the taken rows and columns
  loc15 loc={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};        //reset the locations array
  int games=0,total=0;             //game and total distance counters

  infile>>height;              //read in table height & width
  // LOAD TABLE
  for (int x=0;x<height;x++)
   for (int y=0;y<height;y++)
    { infile>>t[x][y];}
 
  pick1(t,b,loc,height,games,total);     //recursively select the empty cells

  outfile<<"Perfect "<<min<<endl;        //print out the shortest total for this set
  sets--;                                // next set
 }
 return 0;
}

void pick1(table15 t,  bool15 b, loc15 loc, int h,  int games,  int total)
//          distances  taken     locations  height  game count  total distance
{
 int x, y;   //generic counters

 if (games<(h/2))                 //not enough games
  {
   for (x=0;x<h;x++)              //check every row
    for (y=0;y<h;y++)             //check every column
     {
     if (b[x]||b[y]) continue;    //if this row or column is taken try again
       if (x==y) continue;        //no main diagonal
 //SELECT THIS ONE
      games++;                    //add 1 to games selected
      loc[x]=y;                   //keep track of locations selected;
      total+=t[x][y];             //add this to the running total
      b[x]=b[y]=true;             //block out these rows and columns
      pick1(t,b,loc,h,games,total);   //recursive call!!!
      games--;                    //unselect game
      loc[x]=-1;                  //erase location
      total-=t[x][y];             //decrease total
      b[x]=b[y]=false;            //unblock row and column
     }
  }
 else if (total<min)
   min=total;

 return;
}