//package teneyck.backtrackstuff;
import java.util.*;
public class HamiltonianBacktrack {
  private int [ ][ ] M;       //an adjacency matrix rep of the graph
  private int [ ] path;       //sequence of visited vertices (starting at v0)
  private int N;              //number of vertices
  
  public HamiltonianBacktrack(int [ ][ ] G) {
    M = G;
    path = new int [G.length + 1];   //start vertex visited twice
    N = G.length;
  }
  private void hamiltonian(int index) {
    if (promising(index) ) {
      if (index == N - 1) {
        //add this to the path and print result
        path[index+1] = path[0];   //add start vertex to the path;
        System.out.print("A solution is: ");
        for (int i = 0; i <= index + 1; i++)
          System.out.print(" " + path[i]);
        System.out.println( );
      }
      else 
        for (int j = 1; j < N; j++) {
          path[index+1] = j;           //try all vertices as next one
          hamiltonian(index+1);
        }
    }
  }
  private boolean promising(int index) {
    if (index == 0) return true;
    if (index == N - 1 && M[path[index]][path[0]] == 0)
      return false;
    if (index > 0 && M[path[index-1]][path[index]] == 0)
      return false;
    int j = 0;
    while (j < index && path[j] != path[index])
      j++;
    return (j == index);
  }
  public void hamiltonianPath(int startVertex) {
    path[0] = startVertex;
    hamiltonian(0);
  }
  public static void main(String [ ] args) {
    int [ ][ ] graphMatrix = {{0,1,1,0,0,0,1,1},{1,0,1,0,0,0,1,1},
    {1,1,0,1,0,1,0,0},{0,0,1,0,1,0,0,0},{0,0,0,1,0,1,0,0},{0,0,1,0,1,0,1,0},
    {1,1,0,0,0,1,0,1},{1,1,0,0,0,0,1,0}};
    HamiltonianBacktrack hb = new HamiltonianBacktrack(graphMatrix);
    hb.hamiltonianPath(0);
  }
}