import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * Created by Piotruś on 23.04.2017.
 */
public class Algorithms
{
    public static final int N = 3;
    public static final int c = N % 2 == 0 ? 2 * N : 2 * N + 1;
    HashMap<Pair, ArrayList<Integer>> domain;
    public final ArrayList<Integer> colors;
    int[][] matrix;


    {
        HashMap<Pair, ArrayList<Integer>> d = new HashMap<>();
        colors = new ArrayList<>();
        for (int i = 1; i < c + 1; i++)
            colors.add(i);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                d.put(new Pair(i, j), new ArrayList<>(colors));
            }
        domain = d;
    }

    Algorithms()
    {
        matrix = new int[N][N];
    }


    public int backtracking(int[][] matrix, Pair<Integer, Integer> position, int acc, HashSet<HashSet<Integer>> edges)
    {
        for (Integer color : colors)
        {
            int[][] copy = matrix.clone();
            HashSet<HashSet<Integer>> edgesC = new HashSet<>(edges);
            if (constraintsOk(copy, position, color, edgesC))//ograniczenia spełnione
            {
                copy[position.getFirst()][position.getSecond()] = color;
                if (isFinished(copy, position))
                {
                    acc+=1;
                    continue;
                }
                acc = backtracking(copy, getNext(copy, position), acc, edgesC);
            }
        }
        return acc;
    }

    boolean isFinished(int[][] tab, Pair<Integer, Integer> position)
    {
        return position.getFirst() == tab.length - 1 && position.getSecond() == tab[1].length - 1;
    }

    Pair<Integer, Integer> getNext(int[][] matrix, Pair<Integer, Integer> pos)
    {
        if (pos.getSecond() == matrix[0].length - 1)
            return new Pair(pos.getFirst() + 1, 0);
        else
            return new Pair(pos.getFirst(), pos.getSecond() + 1);
    }

    boolean constraintsOk(int[][] matrix, Pair<Integer, Integer> pos, int color ,HashSet<HashSet<Integer>> edges)
    {
        boolean flag = false;
        if (pos.getFirst() == 0 && pos.getSecond() == 0)
        {
            flag = true;
        }
        else if (pos.getFirst() == 0)
        {
            if (matrix[0][pos.getSecond() - 1] != color && !edges.contains(new HashSet<>(Arrays.asList(color, matrix[0][pos.getSecond() - 1]))))
            {
                flag = true;
                edges.add(new HashSet<>(Arrays.asList(color,matrix[0][pos.getSecond() - 1] )));
            }
            else
                flag = false;
        } else if (pos.getSecond() == 0)
        {
            if (matrix[pos.getFirst() - 1][0] != color && !edges.contains(new HashSet<>(Arrays.asList(color, matrix[pos.getFirst() - 1][0]))))
            {
                flag = true;
                edges.add(new HashSet<>(Arrays.asList(color,matrix[pos.getFirst()-1][0])));
            }
            else
                flag = false;
        }
        else if (matrix[pos.getFirst() - 1][pos.getSecond()] != color && matrix[pos.getFirst()][pos.getSecond() - 1] != color && !edges.contains(new HashSet<>(Arrays.asList(color, matrix[pos.getFirst() - 1][pos.getSecond()]))) && !edges.contains(new HashSet<>(Arrays.asList(color, matrix[pos.getFirst()][pos.getSecond() - 1]))))
        {
            flag = true;
            edges.add(new HashSet<>(Arrays.asList(color,matrix[pos.getFirst()][pos.getSecond() - 1])));
            edges.add(new HashSet<>(Arrays.asList(color,matrix[pos.getFirst() - 1][pos.getSecond()])));
        }

        return flag;
    }


    /*public static void main(String args[])
    {
        HashSet<HashSet<Integer>> edges = new HashSet<>();
        Algorithms alg = new Algorithms();
        System.out.println(alg.backtracking(alg.matrix, new Pair(0, 0), 0, edges));
    }*/

   /* public int forwardChecking(int[][] matrix, Pair<Integer, Integer> position, int acc, HashSet<HashSet<Integer>> edge)
    {
        for (Integer color : colors)
        {
            if (constraintsOk(matrix, position, color, edges))//ograniczenia spełnione
            {
                matrix[position.getFirst()][position.getSecond()] = color;
                if (isFinished(matrix, position))
                    return 1;
                acc += backtracking(matrix, getNextSmallestDomain(matrix, position), acc, edges);
            }
        }
        return acc;
    }*/
}