import java.util.Calendar;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
//An modified Traveling Salesperson Problem
// In this example, the salesperson may only visit each city once.
// This is a weighted Hamiltonian Path problem.

//Determine if the graph with numCities nodes and distances defined by the 
//   2D array distances has a Hamiltonian path of weight less than maxPath.
// TODO:
// 1. Write the method verifier.
// 2. Determine how long it takes to fail for different size graphs.
//    Use the createRandomInstance method.
// 3. Copy this file to a class called TSPMin and rewrite its methods
//    so it ignores maxPath and finds the minimum tour.

//example graphs here (you can cut and paste for input
//
/*
 4
 0 1 1 1
 1 0 1 1
 1 1 0 1
 1 1 1 0
 
 4
 0 2 3 1
 4 0 6 2
 1 2 0 5
 4 2 1 0
 
 10
 0 34 45 37 23 83 12 15 99 11
 11 0 22 33 44 55 66 77 88 99
 33 23 0 12 53 23 87 27 54 91
 21 13 81 0 64 81 81 45 53 51
 64 87 54 16 0 87 42 31 46 51
 91 36 65 52 48 0 15 75 32 30
 78 13 16 54 32 76 0 49 35 15
 49 76 45 82 39 47 18 0 19 53
 75 15 95 45 86 45 48 75 0 14
 34 68 49 78 49 68 84 19 37 0
 */

//an instance of the traveling salesman problem
public class TSP {
        int numCities;
        int[][] distances;
        int maxPath;
        
        public static TSP readTSPInstance(java.io.InputStream inStream){
                Scanner in = new Scanner(inStream);
                //read number of cities
                int n = in.nextInt();
                TSP result = new TSP(n);
                
                //read the n x n matrix of distances
                for(int i = 0; i < n; i++){
                        for(int j = 0; j < n; j++){
                                int dist = in.nextInt();
                                result.setDistance(i, j, dist);
                        }
                }
                
                //read the max path value
                int max = in.nextInt();
                result.setMaxPath(max);
                
                return result;
        }
        
        public static TSP createRandomInstance(int n, int max){
                TSP result = new TSP(n);
                Random rand = new Random();
                //read the n x n matrix of distances
                for(int i = 0; i < n; i++){
                        for(int j = 0; j < n; j++){
                                if(i != j)
                                        result.setDistance(i, j, rand.nextInt(100));
                                else
                                        result.setDistance(i,  j, 0);
                        }
                }
                result.setMaxPath(max);
                return result;
                
        }
        
        public TSP(int cities){
                numCities = cities;
                maxPath = numCities; //dummy value
                distances = new int[numCities][numCities];
        }
        
        public int getMaxPath() {
                return maxPath;
        }

        public void setMaxPath(int maxPath) {
                this.maxPath = maxPath;
        }

        //there is no requirement for symmetry
        public void setDistance(int c1, int c2, int dist){
                distances[c1][c2] = dist;
        }
        
        public boolean verifier(List<Integer> certificate){
                //Determine if the certificate represents a TSP path of weight
                //less than or equal to maxPath
                return false;
        }
        
        public boolean hasSolution(){
                List<Integer> cityList = new LinkedList<Integer>();
                for(int i = 0; i < numCities; i++){
                        cityList.add(i);
                }
                
                return permutationHelper(new LinkedList<Integer>(), cityList);
                
        }
        
        private boolean permutationHelper(List<Integer> used, List<Integer> unused){
                if(unused.isEmpty()){
                        if(verifier(used)){
                                printList(used);
                                return true;
                        }
                }
                else {
                        for(int i = 0; i < unused.size(); i++){
                                int item = unused.remove(0);
                                used.add(item);

                                if(permutationHelper(used, unused))
                                        return true;

                                used.remove(used.size()-1);
                                unused.add(item);
                        }
                }
                return false;
        }
        
        public static void main(String[] args){
                //read the problem
                
                System.out.println("Enter the map: ");
                System.out.println("\tn: number of cities");
                System.out.println("\tn*n distances between cities");
                System.out.println("\tm: max tour length");
                
                TSP problem = readTSPInstance(System.in);
                
                
                //TSP problem = createRandomInstance(12, 10);

                long t0 = Calendar.getInstance().getTimeInMillis();
                boolean found = problem.hasSolution();
                long t1 = Calendar.getInstance().getTimeInMillis();
                if(!found)
                        System.out.println("No Solution.");
                System.out.printf("Time: %d\n", (t1-t0));
        }
        
        public static void printList(List<Integer> items){
                for(int i: items){
                        System.out.printf("%d ", i);
                }
                System.out.println();
        }
}