Facebook
From Bitty Dolphin, 6 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 285
  1. import java.util.ArrayList;
  2.  
  3. /**
  4.  * Created by Glizda on 10.05.2017.
  5.  */
  6. public class Backtracking
  7. {
  8.     Node[][] square;
  9.     int[] usedColors;
  10.     boolean possible;
  11.     Backtracking(Node[][] square)
  12.     {
  13.         this.square = square;
  14.         usedColors = new int[square[0][0].getDomain().length];
  15.     }
  16.     public class Pair
  17.     {
  18.         Integer c1;
  19.         Integer c2;
  20.         Pair(Integer c1, Integer c2)
  21.         {
  22.             this.c1 = c1;
  23.             this.c2 = c2;
  24.         }
  25.     }
  26.  
  27.     ArrayList<Pair> pairs = new ArrayList<>();
  28.  
  29.     public Node getNode(Coordinates coor)
  30.     {
  31.         System.out.println("Coor x i y " + coor.x + " " + coor.y);
  32.         return square[coor.x][coor.y];
  33.     }
  34.  
  35.     public boolean ifEqual(Pair p1, Pair p2)
  36.     {
  37.         return ((p1.c1 == p2.c1) && (p1.c2 == p2.c2)) || ((p1.c1 == p2.c2) && (p1.c2 == p2.c1));
  38.     }
  39.  
  40.     public void findDomain(Node n)
  41.     {
  42.         ArrayList<Integer> temp = new ArrayList<>();
  43.         for(int i : n.getDomain())
  44.             temp.add(i);
  45.         for(Coordinates c : n.getNeighbourhood())
  46.             temp.remove(getNode(c).getColor());
  47.         int[] domain = new int[temp.size()];
  48.         for(int i : temp)
  49.             domain[i] = temp.get(i);
  50.         n.setDomain(domain);
  51.     }
  52.     public boolean ifConsistent(Node n, Integer myColor)
  53.     {
  54.         boolean consistent = true;
  55.         for(Coordinates c : n.getNeighbourhood())
  56.         {
  57.             if(getNode(c).getColor() != null)
  58.             {
  59.                 if(getNode(c).getColor() == myColor)
  60.                 {
  61.                     consistent = false;
  62.                 }
  63.                 else
  64.                 {
  65.                     for(Pair p : pairs)
  66.                     {
  67.                         if(ifEqual(p, new Pair(getNode(c).getColor(), myColor)))
  68.                             consistent = false;
  69.                     }
  70.                 }
  71.             }
  72.         }
  73.         return consistent;
  74.     }
  75.  
  76.     public void addPairs(Node n)
  77.     {
  78.         for(Coordinates c : n.getNeighbourhood())
  79.         {
  80.             if(getNode(c).getColor() != null)
  81.             {
  82.                 Pair p = new Pair(n.getColor(), getNode(c).getColor());
  83.                 if(pairs.contains(p))
  84.                     System.out.println("Coś poszło nie tak. Ta para już istnieje!");
  85.                 pairs.add(p);
  86.             }
  87.         }
  88.     }
  89.  
  90.     public Node chooseNext(Node[][] square)
  91.     {
  92.         return mostRestricting(mostRestricted(square));
  93.     }
  94.  
  95.     public ArrayList<Coordinates> mostRestricted(Node[][] square)
  96.     {
  97.         ArrayList<Coordinates> mostRestricted = new ArrayList<>();
  98.         int minDom = square[0].length * 2 + 1;
  99.         for(int i = 0; i < square[0].length; i++)
  100.         {
  101.             for (int j = 0; j < square[0].length; j++)
  102.             {
  103.                 findDomain(square[i][j]);
  104.                 if(square[i][j].getDomain().length < minDom)
  105.                 {
  106.                     minDom = square[i][j].getDomain().length;
  107.                     ArrayList<Coordinates> temp = new ArrayList<>();
  108.                     temp.add(square[i][j].myCoor);
  109.                     mostRestricted = temp;
  110.                 }
  111.                 else if(square[i][j].getDomain().length == minDom)
  112.                 {
  113.                     mostRestricted.add(square[i][j].myCoor);
  114.                 }
  115.             }
  116.         }
  117.         return mostRestricted;
  118.     }
  119.  
  120.     public Node mostRestricting(ArrayList<Coordinates> mostRestricted)
  121.     {
  122.         Node max = getNode(mostRestricted.get(0));
  123.         int mostFreeNeighbors = 8;
  124.         for(Coordinates c : mostRestricted)
  125.         {
  126.             int freeNeighbors = 0;
  127.             for(Coordinates f : getNode(c).getNeighbourhood())
  128.             {
  129.                 if(getNode(f).getColor() == null)
  130.                     freeNeighbors++;
  131.             }
  132.             if(freeNeighbors > mostFreeNeighbors)
  133.             {
  134.                 max = getNode(c);
  135.                 mostFreeNeighbors = freeNeighbors;
  136.             }
  137.         }
  138.         return max;
  139.     }
  140.  
  141.     public boolean isDone(Node[][] square)
  142.     {
  143.         boolean done = true;
  144.         for(int i = 0; i < square[0].length - 1; i++)
  145.         {
  146.             for(Node n : square[i])
  147.                 if(n.getColor() == null)
  148.                     done = false;
  149.         }
  150.         return done;
  151.     }
  152.  
  153.     public boolean recursive_backtracking(Coordinates c, Node[][] square)
  154.     {
  155.         Coordinates d = c;
  156.         if(getNode(c).getColor() == null)
  157.         {
  158.             for(int col : usedColors)
  159.             {
  160.                 if(ifConsistent(getNode(c), col))
  161.                 {
  162.                     getNode(c).setColor(col);
  163.                     usedColors[col]++;
  164.                     addPairs(getNode(c));
  165.                     d = new Coordinates(c.x, c.y);
  166.                     if(d.x < square[0].length - 1)
  167.                         d.x++;
  168.                     else
  169.                     {
  170.                         d.x = 0;
  171.                         d.y++;
  172.                     }
  173.                     if(!recursive_backtracking(d, square));
  174.                     {
  175.                         square[d.x][d.y].setColor(null);
  176.                         return false;
  177.                     }
  178.                 }
  179.             }
  180.             if(getNode(d).getColor() == null)
  181.                 return false;
  182.         }
  183.         return isDone(square);
  184.     }
  185. }
  186.