- 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);
- }
- }