HAMMING SIMPLE

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 5

/*
 *
 */
void impMat(int M[N][N],int n){
    int i,j;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            printf("%d", M[i][j]);
        }
        printf("\n");
    }
}

int isSafe(int v, int M[N][N], int A[], int pos)
{
    /* Check if this vertex is an adjacent vertex of the previously
       added vertex. */
    if (M [ A[pos-1] ][ v ] == 0)
        return 0;

    /* Check if the vertex has already been included.
      This step can be optimized by creating an array of size V */
    int i;
    for (i = 0; i < pos; i++)
        if (A[i] == v)
            return 0;

    return 1;
}

int hamCycleUtil(int M[N][N], int A[], int pos)
{
    /* base case: If all vertices are included in Hamiltonian Cycle */
    if (pos == N)
    {
        // And if there is an edge from the last included vertex to the
        // first vertex
        if ( M[ A[pos-1] ][ A[0] ] == 1 )
           return 1;
        else
          return 0;
    }

    // Try different vertices as a next candidate in Hamiltonian Cycle.
    // We don't try for 0 as we included 0 as starting point in in hamCycle()
    int v;
    for (v = 1; v < N; v++)
    {
        /* Check if this vertex can be added to Hamiltonian Cycle */
        if (isSafe(v, M, A, pos))
        {
            A[pos] = v;

            /* recur to construct rest of the path */
            if (hamCycleUtil (M, A, pos+1) == true)
                return 1;

            /* If adding vertex v doesn't lead to a solution,
               then remove it */
            A[pos] = -1;
        }
    }

    /* If no vertex can be added to Hamiltonian Cycle constructed so far,
       then return false */
    return 0;
}


int hamCycle(int M[N][N])
{
    int A[N]; //Arreglo con el ciclo hamiltoniano
    int i;
    for (i = 0; i < N; i++)
        A[i] = -1;

    A[0] = 0; //El ciclo siempre empieza en 0
    if ( hamCycleUtil(M, A, 1) == 0 )
    {
        printf("\nSolution does not exist");
        return 0;
    }

    impSol(A);
    return 1;
}

void impSol(int A[]){
    printf ("Solution Exists:"
            " Following is one Hamiltonian Cycle \n");
    int i;
    for (i = 0; i < N; i++)
        printf(" %d ", A[i]);
}

int main(int argc, char** argv) {
    int n=5;
    int M[N][N]={{0,1,1,0,1},{1,0,1,0,1},{1,1,0,1,1},{0,0,1,0,1},{1,1,1,1,0}};

    /*Lectura archivos
     int i,j;
     for(i=0;i<n;i++)
         for(j=0;j<n;j++)
             scanf("%d", &M[i][j]);
     */
    impMat(M,n);
    hamCycle(M);

    return (EXIT_SUCCESS);
}