import java.util.ArrayList;

/**
 * Created by Glizda on 10.05.2017.
 */
public class Backtracking
{
    Node[][] square;
    int[] usedColors;
    boolean possible;
    Backtracking(Node[][] square)
    {
        this.square = square;
        usedColors = new int[square[0][0].getDomain().length];
    }
    public class Pair
    {
        Integer c1;
        Integer c2;
        Pair(Integer c1, Integer c2)
        {
            this.c1 = c1;
            this.c2 = c2;
        }
    }

    ArrayList<Pair> pairs = new ArrayList<>();

    public Node getNode(Coordinates coor)
    {
        System.out.println("Coor x i y " + coor.x + " " + coor.y);
        return square[coor.x][coor.y];
    }

    public boolean ifEqual(Pair p1, Pair p2)
    {
        return ((p1.c1 == p2.c1) && (p1.c2 == p2.c2)) || ((p1.c1 == p2.c2) && (p1.c2 == p2.c1));
    }

    public void findDomain(Node n)
    {
        ArrayList<Integer> temp = new ArrayList<>();
        for(int i : n.getDomain())
            temp.add(i);
        for(Coordinates c : n.getNeighbourhood())
            temp.remove(getNode(c).getColor());
        int[] domain = new int[temp.size()];
        for(int i : temp)
            domain[i] = temp.get(i);
        n.setDomain(domain);
    }
    public boolean ifConsistent(Node n, Integer myColor)
    {
        boolean consistent = true;
        for(Coordinates c : n.getNeighbourhood())
        {
            if(getNode(c).getColor() != null)
            {
                if(getNode(c).getColor() == myColor)
                {
                    consistent = false;
                }
                else
                {
                    for(Pair p : pairs)
                    {
                        if(ifEqual(p, new Pair(getNode(c).getColor(), myColor)))
                            consistent = false;
                    }
                }
            }
        }
        return consistent;
    }

    public void addPairs(Node n)
    {
        for(Coordinates c : n.getNeighbourhood())
        {
            if(getNode(c).getColor() != null)
            {
                Pair p = new Pair(n.getColor(), getNode(c).getColor());
                if(pairs.contains(p))
                    System.out.println("Coś poszło nie tak. Ta para już istnieje!");
                pairs.add(p);
            }
        }
    }

    public Node chooseNext(Node[][] square)
    {
        return mostRestricting(mostRestricted(square));
    }

    public ArrayList<Coordinates> mostRestricted(Node[][] square)
    {
        ArrayList<Coordinates> mostRestricted = new ArrayList<>();
        int minDom = square[0].length * 2 + 1;
        for(int i = 0; i < square[0].length; i++)
        {
            for (int j = 0; j < square[0].length; j++)
            {
                findDomain(square[i][j]);
                if(square[i][j].getDomain().length < minDom)
                {
                    minDom = square[i][j].getDomain().length;
                    ArrayList<Coordinates> temp = new ArrayList<>();
                    temp.add(square[i][j].myCoor);
                    mostRestricted = temp;
                }
                else if(square[i][j].getDomain().length == minDom)
                {
                    mostRestricted.add(square[i][j].myCoor);
                }
            }
        }
        return mostRestricted;
    }

    public Node mostRestricting(ArrayList<Coordinates> mostRestricted)
    {
        Node max = getNode(mostRestricted.get(0));
        int mostFreeNeighbors = 8;
        for(Coordinates c : mostRestricted)
        {
            int freeNeighbors = 0;
            for(Coordinates f : getNode(c).getNeighbourhood())
            {
                if(getNode(f).getColor() == null)
                    freeNeighbors++;
            }
            if(freeNeighbors > mostFreeNeighbors)
            {
                max = getNode(c);
                mostFreeNeighbors = freeNeighbors;
            }
        }
        return max;
    }

    public boolean isDone(Node[][] square)
    {
        boolean done = true;
        for(int i = 0; i < square[0].length - 1; i++)
        {
            for(Node n : square[i])
                if(n.getColor() == null)
                    done = false;
        }
        return done;
    }

    public boolean recursive_backtracking(Coordinates c, Node[][] square)
    {
        Coordinates d = c;
        if(getNode(c).getColor() == null)
        {
            for(int col : usedColors)
            {
                if(ifConsistent(getNode(c), col))
                {
                    getNode(c).setColor(col);
                    usedColors[col]++;
                    addPairs(getNode(c));
                    d = new Coordinates(c.x, c.y);
                    if(d.x < square[0].length - 1)
                        d.x++;
                    else
                    {
                        d.x = 0;
                        d.y++;
                    }
                    if(!recursive_backtracking(d, square));
                    {
                        square[d.x][d.y].setColor(null);
                        return false;
                    }
                }
            }
            if(getNode(d).getColor() == null)
                return false;
        }
        return isDone(square);
    }
}