import java.util.Scanner;
import java.io.*;

/*
 * Lab 10
 *
 * Author: Robin Dawes
 *
 * Date: 20091126
 *
 * Comment: some diagnostic output has been included to make it possible to follow the execution of the algorithm
 *
 */

public class Jobs {

    static int instances;
    static int numOfWorkers;
    
    static int[][] costs;
    
    static int globalU;

    public static void main (String[] argv) throws Exception {
        Scanner myScanner = new Scanner(new File("Lab_10_Data.txt"));
        // find out how many instances
        instances = myScanner.nextInt();
        for (int i = 0; i < instances; i++) {
            
            System.out.println("\nInstance " + i + " input: ");
            
            numOfWorkers = myScanner.nextInt();
            System.out.println("# of workers = " + numOfWorkers);
            
            costs = new int[numOfWorkers+1][numOfWorkers];
            
            for (int c = 0; c < numOfWorkers; c++) costs[0][c] = c;     // first row contains the job numbers
            
            for (int r = 1; r <= numOfWorkers; r++) 
                for (int c = 0; c < numOfWorkers; c++) 
                    costs[r][c] = myScanner.nextInt();
                    
            
            for (int r = 0; r <= numOfWorkers; r++) {
                for (int c = 0; c < numOfWorkers; c++)
                    System.out.print(costs[r][c] + "\t");
                System.out.println();
            }
            
            // initialize the global upper bound
            globalU = 0;            
            for (int r = 1; r <= numOfWorkers; r++)
                globalU += costs[r][r-1];
            
            boolean notDone = true;
            
            // initialize the heap S of partial solutions
            
            PartialSolutionHeap S = new PartialSolutionHeap();
            int[] assignments = new int[numOfWorkers];
            
            // initialize the set of partial solutions
            System.out.println("Initializing set of partial solutions");
            int nextWorker = 0;
            int[] newAssigs;
            int[][] newCosts = new int[numOfWorkers][numOfWorkers-1];
        
            for (int j = 0; j < numOfWorkers; j++) { // assign each remaining job to the next worker
                //System.out.println("Assigning job " + j + " to worker 0");
                newAssigs = new int[numOfWorkers];
                newAssigs[0] = costs[0][j]; // this is the id number of the job being assigned to worker 0
                for (int a = 1; a < numOfWorkers; a++) newAssigs[a] = 0;
                /*
                int tc = -1;
                for (int c=0; c < numOfWorkers-1; c++) {
                    if (c == j) tc += 2;
                    else tc += 1;
                    newCosts[0][c] = costs[0][tc];                
                }
            
                for (int r = 1; r < numOfWorkers; r++) {
                    tc = -1;
                    for (int c = 0; c < numOfWorkers-1; c++) {
                        if (c == j) tc += 2;
                        else tc += 1;
                        newCosts[r][c] = costs[r+1][tc];
                    }
                }
            */
                newCosts = reduceMatrix(costs,1,j);
                PartialSolution p = new PartialSolution(numOfWorkers, newCosts, costs[1][j], 0, newAssigs);
                if (p.getLower() <= globalU) S.insert(p);
                else System.out.println("Rejecting new partial solution - cost too high");
                if (p.getUpper() < globalU) globalU = p.getUpper();
            
            }
            
            System.out.println("Partial solution set initialized");
            
            while (notDone && S.notEmpty()) {
                // extract the partial solution P with the lowest lower bound
                // System.out.println("Extracting a partial solution");
                PartialSolution x = S.extractMin();
                // if it is a full solution, output it and set notDone = false
                if (x.isFullSolution()) {
                    System.out.println("Solution found");
                    x.printChoices();
                    S.report();
                    notDone = false;
                }
                else {
                    // else generate all possible expansions of P and add them to S
                    globalU = x.expand(S, globalU);
                }
            } // while
            System.out.println("*******************");    
        } // for
        
    } // main
    
    static int[][] reduceMatrix(int[][] m, int r, int c){
        //returns the matrix with row r and column c removed
        int mrows = m.length;
        int mcols = m[0].length;
        int[][] newM = new int[mrows-1][mcols-1];
        for (int row = 0; row < mrows - 1; row++) {
            int sourcerow;
            if (row < r) sourcerow = row;
            else sourcerow = row+1;
            for (int col = 0; col < mcols - 1; col++) {
                int sourcecol;
                if (col < c) sourcecol = col;
                else sourcecol = col+1;
                // copy the appropriate value into this location of newM
                newM[row][col] = m[sourcerow][sourcecol];
            }
        }
        return newM;
    } //reduceMatrix
    
} // class