/**
 * labynombre - Test.java
 * Author : Jonathan Schnyder
 * Created : 18 déc. 2017
 */

package labynombre;

import java.util.ArrayList;

public class Test
{
    public static int[][] matrix = new int[20][20] ;

    public static int[][] mouvements = {
            //mouv. ligne[0],   mouv. col[1],   nombre à ajouter[2]
            {+0,                +1,             +2},                //droige [0]
            {+0,                -1,             -4},                //gauche [1]
            {-1,                +0,             -5},                //haut   [2]
            {+1,                +0,             +3},                //bas    [3]
    };

    //initialisation
    public static int ligneActuelle = 0;
    public static int colonneActuelle = 6;
    public static int valeurActuelle = 4;

    public static int nbSolutions = 0 ;

    //liste des mouvements effectués
    public static ArrayList listeMouvement = new ArrayList() ;

    //méthode de backtracking
    public static void resoudreLabynombre()
    {
        //clause de finitude
        if((ligneActuelle==13&&colonneActuelle==0)||(ligneActuelle==13&&colonneActuelle==19)||(ligneActuelle==19&&colonneActuelle==9))
        {
            nbSolutions++ ;
            System.out.println("Solution "+nbSolutions);
            affiche() ;
            return ;
        }

        //pas récursif
        //pour chaque mouvement à partir de la case actuelle
        for (int i = 0; i < mouvements.length; i++)
        {
            if(mouvementPossible(i))
            {
                effectuerMouvement(i, 1) ;
                resoudreLabynombre() ;
                effectuerMouvement(i, -1) ;
            }
        }
    }

    //methode pour effectuer et enregistrer le mouvement
    //opérateur = 1 si on effectue le mouvement, -1 si on l'annule
    public static void effectuerMouvement(int mouvement, int operateur)
    {
        //définit les mouvements
        int mouvementLigne = mouvements[mouvement][0] * operateur ;
        int mouvementColonne = mouvements[mouvement][1] * operateur ;
        int mouvementValeur = mouvements[mouvement][2] * operateur ;

        //si on annule le mouvement, on le retire de la liste
        if(operateur==-1)
        {
            listeMouvement.remove(listeMouvement.size()-1) ;
        }
        //sinon on l'ajoute
        else
        {
            String direction = null;
            switch(mouvement)
            {

            case 0 :
                direction = ">" ;
                break;
            case 1 :
                direction = "<" ;
                break;
            case 2 :
                direction = "^" ;
                break ;
            case 3 :
                direction = "v" ;
                break ;
            }
            listeMouvement.add(direction) ;
        }

        //on effectue le mouvement
        valeurActuelle += mouvementValeur ;
        ligneActuelle += mouvementLigne ;
        colonneActuelle += mouvementColonne ;
    }

    //methode qui teste si le mouvement est possible
    public static boolean mouvementPossible(int mouvement)
    {
        //définit les valeurs obtenues par le mouvement
        int ligneSuivante = ligneActuelle+mouvements[mouvement][0] ;
        int colonneSuivante = colonneActuelle+mouvements[mouvement][1] ;
        int valeurSuivante = valeurActuelle+mouvements[mouvement][2] ;

        //si on sort du tableau (lignes)
        if(ligneSuivante==-1||ligneSuivante==20) return false ;

        //si on sort du tableau (colonnes)
        if(colonneSuivante==-1||colonneSuivante==20) return false ;

        //si on tombe sur une case en dehors des valeurs
        if(matrix[ligneSuivante][colonneSuivante]==-1) return false ;

        //si l'addition de la valeur du mouvement ne correspond pas à la valeur de la case
        if(matrix[ligneSuivante][colonneSuivante]!=valeurSuivante) return false ;

        return true ;
    }

    //duh
    public static void affiche()
    {
        for (int i = 0; i < listeMouvement.size(); i++)
        {
            System.out.print(listeMouvement.get(i)+" ");
        }
        System.out.println();
    }

    //re-duh
    public static void main(String[] args)
    {

        fillMatrix();
        resoudreLabynombre();
    }

    //methode qui remplit la matrice avec le labyrithe
    public static void fillMatrix() {
        // Remplissage avec une valeur -1
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                matrix[i][j] = -1;
            }
        }

        // Remplissage avec les bonnes valeurs
        matrix[0][6] = 4;
        matrix[1][5] = 1;
        matrix[1][6] = 7;
        matrix[1][7] = 9;
        matrix[2][3] = 3;
        matrix[2][4] = 2;
        matrix[2][5] = 6;
        matrix[2][6] = 10;
        matrix[2][7] = 12;
        matrix[2][8] = 14;
        matrix[2][9] = 16;
        matrix[2][10] = 4;
        matrix[2][11] = 8;
        matrix[2][12] = 10;
        matrix[2][13] = 12;
        // 3
        matrix[3][2] = 4;
        matrix[3][3] = 1;
        matrix[3][4] = 5;
        matrix[3][5] = 9;
        matrix[3][6] = 11;
        matrix[3][7] = 13;
        matrix[3][8] = 15;
        matrix[3][9] = 19;
        matrix[3][10] = 21;
        matrix[3][11] = 13;
        matrix[3][12] = 15;
        matrix[3][13] = 2;
        matrix[3][14] = 5;
        // 4
        matrix[4][2] = 5;
        matrix[4][3] = 4;
        matrix[4][4] = 8;
        matrix[4][5] = 12;
        matrix[4][6] = 12;
        matrix[4][7] = 16;
        matrix[4][8] = 14;
        matrix[4][9] = 16;
        matrix[4][10] = 16;
        matrix[4][11] = 18;
        matrix[4][12] = 4;
        matrix[4][13] = 7;
        matrix[4][14] = 10;
        matrix[4][15] = 12;
        // 5
        matrix[5][2] = 2;
        matrix[5][3] = 7;
        matrix[5][4] = 7;
        matrix[5][5] = 11;
        matrix[5][6] = 15;
        matrix[5][7] = 17;
        matrix[5][8] = 19;
        matrix[5][9] = 19;
        matrix[5][10] = 21;
        matrix[5][11] = 23;
        matrix[5][12] = 9;
        matrix[5][13] = 13;
        matrix[5][14] = 15;
        matrix[5][15] = 2;
        matrix[5][16] = 5;
        // 6
        matrix[6][2] = 6;
        matrix[6][3] = 2;
        matrix[6][4] = 10;
        matrix[6][5] = 12;
        matrix[6][6] = 10;
        matrix[6][7] = 14;
        matrix[6][8] = 18;
        matrix[6][9] = 22;
        matrix[6][10] = 24;
        matrix[6][11] = 26;
        matrix[6][12] = 14;
        matrix[6][13] = 18;
        matrix[6][14] = 18;
        matrix[6][15] = 20;
        matrix[6][16] = 22;
        matrix[6][17] = 24;
        // 7
        matrix[7][2] = 9;
        matrix[7][3] = 8;
        matrix[7][4] = 13;
        matrix[7][5] = 15;
        matrix[7][6] = 13;
        matrix[7][7] = 11;
        matrix[7][8] = 15;
        matrix[7][9] = 17;
        matrix[7][10] = 27;
        matrix[7][11] = 19;
        matrix[7][12] = 21;
        matrix[7][13] = 23;
        matrix[7][14] = 19;
        matrix[7][15] = 23;
        matrix[7][16] = 23;
        matrix[7][17] = 27;
        // 8
        matrix[8][2] = 12;
        matrix[8][3] = 11;
        matrix[8][4] = 11;
        matrix[8][5] = 12;
        matrix[8][6] = 16;
        matrix[8][7] = 18;
        matrix[8][8] = 20;
        matrix[8][9] = 20;
        matrix[8][10] = 22;
        matrix[8][11] = 24;
        matrix[8][12] = 24;
        matrix[8][13] = 26;
        matrix[8][14] = 22;
        matrix[8][15] = 24;
        matrix[8][16] = 26;
        matrix[8][17] = 28;
        // 9
        matrix[9][2] = 15;
        matrix[9][3] = 14;
        matrix[9][4] = 16;
        matrix[9][5] = 15;
        matrix[9][6] = 17;
        matrix[9][7] = 13;
        matrix[9][8] = 17;
        matrix[9][9] = 21;
        matrix[9][10] = 25;
        matrix[9][11] = 21;
        matrix[9][12] = 25;
        matrix[9][13] = 29;
        matrix[9][14] = 25;
        matrix[9][15] = 27;
        matrix[9][16] = 27;
        matrix[9][17] = 31;
        // 10
        matrix[10][2] = 18;
        matrix[10][3] = 22;
        matrix[10][4] = 14;
        matrix[10][5] = 18;
        matrix[10][6] = 12;
        matrix[10][7] = 16;
        matrix[10][8] = 2;
        matrix[10][9] = 6;
        matrix[10][10] = 10;
        matrix[10][11] = 24;
        matrix[10][12] = 20;
        matrix[10][13] = 24;
        matrix[10][14] = 28;
        matrix[10][15] = 30;
        matrix[10][16] = 2;
        matrix[10][17] = 4;
        // 11
        matrix[11][2] = 21;
        matrix[11][3] = 25;
        matrix[11][4] = 25;
        matrix[11][5] = 11;
        matrix[11][6] = 15;
        matrix[11][7] = 0;
        matrix[11][8] = 3;
        matrix[11][9] = 9;
        matrix[11][10] = 15;
        matrix[11][11] = 19;
        matrix[11][12] = 23;
        matrix[11][13] = 25;
        matrix[11][14] = 3;
        matrix[11][15] = 5;
        matrix[11][16] = 7;
        matrix[11][17] = 7;
        // 12
        matrix[12][1] = 20;
        matrix[12][2] = 24;
        matrix[12][3] = 28;
        matrix[12][4] = 30;
        matrix[12][5] = 32;
        matrix[12][6] = 0;
        matrix[12][7] = 4;
        matrix[12][8] = 8;
        matrix[12][9] = 12;
        matrix[12][10] = 14;
        matrix[12][11] = 16;
        matrix[12][12] = 18;
        matrix[12][13] = 4;
        matrix[12][14] = 8;
        matrix[12][15] = 12;
        matrix[12][16] = 10;
        matrix[12][17] = 12;
        matrix[12][18] = 14;
        // 13
        matrix[13][0] = 19;
        matrix[13][1] = 23;
        matrix[13][2] = 25;
        matrix[13][3] = 29;
        matrix[13][4] = 33;
        matrix[13][5] = 0;
        matrix[13][6] = 3;
        matrix[13][7] = 7;
        matrix[13][8] = 11;
        matrix[13][9] = 13;
        matrix[13][10] = 17;
        matrix[13][11] = 11;
        matrix[13][12] = 13;
        matrix[13][13] = 15;
        matrix[13][14] = 13;
        matrix[13][15] = 17;
        matrix[13][16] = 19;
        matrix[13][17] = 21;
        matrix[13][18] = 17;
        matrix[13][19] = 19;
        // 14
        matrix[14][1] = 26;
        matrix[14][2] = 28;
        matrix[14][3] = 30;
        matrix[14][4] = 34;
        matrix[14][5] = 2;
        matrix[14][6] = 6;
        matrix[14][7] = 10;
        matrix[14][8] = 12;
        matrix[14][9] = 16;
        matrix[14][10] = 14;
        matrix[14][11] = 16;
        matrix[14][12] = 18;
        matrix[14][13] = 20;
        matrix[14][14] = 20;
        matrix[14][15] = 22;
        matrix[14][16] = 18;
        matrix[14][17] = 20;
        matrix[14][18] = 22;
        // 15
        matrix[15][2] = 29;
        matrix[15][3] = 33;
        matrix[15][4] = 1;
        matrix[15][5] = 5;
        matrix[15][6] = 7;
        matrix[15][7] = 11;
        matrix[15][8] = 15;
        matrix[15][9] = 17;
        matrix[15][10] = 19;
        matrix[15][11] = 19;
        matrix[15][12] = 19;
        matrix[15][13] = 23;
        matrix[15][14] = 25;
        matrix[15][15] = 25;
        matrix[15][16] = 23;
        matrix[15][17] = 25;
        // 16
        matrix[16][2] = 32;
        matrix[16][3] = 0;
        matrix[16][4] = 4;
        matrix[16][5] = 2;
        matrix[16][6] = 4;
        matrix[16][7] = 6;
        matrix[16][8] = 18;
        matrix[16][9] = 11;
        matrix[16][10] = 13;
        matrix[16][11] = 17;
        matrix[16][12] = 22;
        matrix[16][13] = 22;
        matrix[16][14] = 28;
        matrix[16][15] = 30;
        matrix[16][16] = 28;
        matrix[16][17] = 30;
        // 17
        matrix[17][3] = 3;
        matrix[17][4] = 0;
        matrix[17][5] = 3;
        matrix[17][6] = 7;
        matrix[17][7] = 9;
        matrix[17][8] = 11;
        matrix[17][9] = 13;
        matrix[17][10] = 16;
        matrix[17][11] = 21;
        matrix[17][12] = 25;
        matrix[17][13] = 27;
        matrix[17][14] = 29;
        matrix[17][15] = 33;
        matrix[17][16] = 35;
        // 18 et 19
        matrix[18][8] = 14;
        matrix[18][9] = 16;
        matrix[18][10] = 20;
        matrix[19][9] = 19;
    }
}