Как сделать алгоритм более эффективным?

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ Эта задача является частью ЗАВЕРШЕННОГО соревнования и не будет использоваться повторно.

Я надеялся, что кто-нибудь сможет создать и объяснить решение, достаточно эффективное для работы с файлами размером не более 15 x 15 плиток. Ниже проблема:

Плиточный пол (40 очков) Сэм недавно нанял плиточника, чтобы он уложил плитку на кухонном полу. Пол должен был быть очень красочным, без двух соседние плитки одного цвета. К сожалению, установщик не смог убедиться, что соседние плитки имеют разные цвета. Раствор еще влажный, но поднять только одну плитку за раз сложно, поэтому установщик ограничивается перестановкой. соседние плитки. Вопрос в том, как обменять соседние плитки за как можно меньшее количество ходов, чтобы пол совпал критерий того, что никакие две соседние плитки не имеют одинаковый цвет. Пример ввода РГР RPC GRB YPG Представляя плитки на этаже три на четыре, где R — красная плитка, G — зеленая, B — синяя, C — голубая, P — фиолетовая и Y желтый. В общем, ввод будет представлять собой серию строк R, G, B, C, P и Y. Каждая строка будет иметь одинаковую длину. и будет максимум 15 строк по 15 символов в каждой. Выход должен быть целым числом представляющее количество перестановок соседних плиток. Для этой задачи «прилегающий» означает соприкасающийся и в одном и том же месте. строка или столбец; например, только две плитки примыкают к желтой плитке в левом нижнем углу изображения выше. пол: зеленая плитка в начале третьего ряда и фиолетовая плитка в середине четвертого ряда. Выход для верхнего этажа будет 2 поскольку красную плитку в начале строки 2 можно поменять местами с зеленой плиткой в ​​начале строки три, а затем красную плитку в середине строки 3 можно поменять местами с синей плиткой в ​​конце. Это дает расположение РГР ГПХ RBR YPG Возможны и другие исправления, такие как замена первых двух плиток в строке 2 для получения PRC, а затем замена средней плитки в строках 3 и 4. Ваша программа не печатает результирующее расположение полов, а только минимальное количество свопы плитки, которые должны иметь место. Иногда невозможно починить пол: GGYGP CGGRG Это невозможно замостить, потому что есть 6 G, а на полу такого размера может поместиться только 5, причем два из них не будут смежными. В случаях, когда нет решения, выход должен быть невозможно

Я создал решение, но оно работает только примерно для 16 плиток (4 x 4), больше занимает огромное количество времени. Это из-за рекурсивного и наивного характера этой функции, при каждом вызове она вызывает себя как минимум 4 раза.

Ниже приведена моя попытка решения, имейте в виду, что есть дополнительные методы из предыдущих попыток и что MinimumSwaps() является основным рекурсивным методом:

import java.util.*;
import java.io.*;
class Main {
  private static ArrayList<String[][]> solutions = new ArrayList<String[][]>();
  private static ArrayList<Integer> moves = new ArrayList<Integer>();
  private static int min = Integer.MAX_VALUE;
  
  
  public static void main(String[] args) throws Exception {
    File file = new File("Tiles.txt");
    Scanner scan = new Scanner(file);
    Scanner scan1 = new Scanner(file);
    int length = 0;
    while (scan1.hasNextLine()) {
      scan1.nextLine();
      length++;
    } 
    String[][] tiles = new String[length][];
    for (int i = 0; i < length; i++) {
      String line = scan.nextLine();
      tiles[i] = new String[line.length()];
      for (int l = 0; l < tiles[i].length; l++) {
        tiles[i][l] = line.substring(l, l + 1);
      }
    }

    System.out.println("Start");

    minimumSwaps(tiles, 0, new ArrayList<String>());
    

    //System.out.println(Arrays.toString(findCount(tiles)));
    //findSolutions(new String[tiles.length][tiles[0].length], findCount(tiles), 0, 0);
    //System.out.println(solutions.size());
    System.out.println(min);
    //display();

    
  }

  //tilesIDs: more efficient way to check if computer has seen previous situation

  //how to know if there are moves that do not involve problem areas that reduces total number of moves?

  public static void minimumSwaps (String[][] tiles, int moves, ArrayList<String> tilesIDs) {
    if (moves < min) {
      String newID = computeID(tiles);
      if (linearSearch(tilesIDs, newID)) return;
      tilesIDs.add(newID);
      if (solved(tiles)) {
        //Main.moves.add(moves);
        if (moves < min) min = moves;
        //solutions.add(cloneTiles(tiles));
      }
      else if (moves < min - 1) {
        for (int i = 0; i < tiles.length; i++) {
          for (int l = 0; l < tiles[i].length; l++) {
            if (adjacentPresent(tiles, tiles[i][l], i, l)) {
              try {
                String[][] newTiles = cloneTiles(tiles);
                String current = newTiles[i][l];
                newTiles[i][l] = newTiles[i][l - 1];
                newTiles[i][l - 1] = current;
                minimumSwaps(newTiles, moves + 1, (ArrayList<String>)(tilesIDs.clone()));
              }  
              catch (Exception e) {}
              try {
                String[][] newTiles = cloneTiles(tiles);
                String current = newTiles[i][l];
                newTiles[i][l] = newTiles[i][l + 1];
                newTiles[i][l + 1] = current;
                minimumSwaps(newTiles, moves + 1, (ArrayList<String>)(tilesIDs.clone()));
              }
              catch (Exception e) {}
              try {
                String[][] newTiles = cloneTiles(tiles);
                String current = newTiles[i][l];
                newTiles[i][l] = newTiles[i - 1][l];
                newTiles[i - 1][l] = current;
                minimumSwaps(newTiles, moves + 1, (ArrayList<String>)(tilesIDs.clone()));
              }
              catch (Exception e) {}
              try {
                String[][] newTiles = cloneTiles(tiles);
                String current = newTiles[i][l];
                newTiles[i][l] = newTiles[i + 1][l];
                newTiles[i + 1][l] = current;
                minimumSwaps(newTiles, moves + 1, (ArrayList<String>)(tilesIDs.clone()));
              }
              catch (Exception e) {}
            }
          }  
        }
      }
    }
  }

  public static boolean linearSearch(ArrayList<String> IDs, String newID) {
    for (String ID : IDs) if (ID.equals(newID)) return true;
    return false;
  }

  public static String computeID(String[][] tiles) {
    String ID = "";
    for (String[] letters : tiles) {
      for (String letter : letters) {
        ID += letter;
      }
    }
    return ID;
  }

  public static String[][] cloneTiles(String[][] tiles) {
    String[][] newTiles = new String[tiles.length][tiles[0].length];
    for (int i = 0; i < tiles.length; i++) {
      newTiles[i] = tiles[i].clone();
    }
    return newTiles;
  }

  public static boolean solved(String[][] tiles) {
    for (int i = 0; i < tiles.length; i++) {
      for (int l = 0; l < tiles[i].length; l++) {
        if (adjacentPresent(tiles, tiles[i][l], i, l)) return false;
      }
    }
    return true;
  }

  public static int minMoves() {
    int min = Integer.MAX_VALUE;
    for (int num : moves) if (num < min) min = num;
    return min;
  }

  public static void findSolutions(String[][] tiles, int[] count, int i, int l) {

    String[] colors = {"R", "G", "B", "C", "P", "Y"};
    for (int z = 0; z < 6; z++) {
      //System.out.println("testing");
      if (!adjacentPresent(tiles, colors[z], i, l) && count[z] > 0) {
        String[][] newTiles = new String[tiles.length][tiles[0].length];
        for (int a = 0; a < newTiles.length; a++) {
          for (int b = 0; b < newTiles[0].length; b++) {
            newTiles[a][b] = tiles[a][b]; // clone does not work properly?
          }
        }
        newTiles[i][l] = colors[z];
        //System.out.println(Arrays.deepToString(newTiles));
        int[] newCount = count.clone();
        newCount[z]--;
        if (l == tiles[0].length - 1 && i != tiles.length - 1) {
          findSolutions(newTiles, newCount, i + 1, 0);
        }
        else if (l < tiles[0].length - 1) {
          findSolutions(newTiles, newCount, i, l + 1);
        }
        else if (l == tiles[0].length - 1 && i == tiles.length - 1) {
          solutions.add(newTiles);
        }
      }
    }
  }

  public static boolean adjacentPresent(String[][] tiles, String color, int i, int l) {
    try {
      if (tiles[i][l + 1].equals(color)) return true;
    }
    catch (Exception e) {}
    try {
      if (tiles[i][l - 1].equals(color)) return true;
    }
    catch (Exception e) {}
    try {
      if (tiles[i + 1][l].equals(color)) return true;
    }
    catch (Exception e) {}
    try {
      if (tiles[i - 1][l].equals(color)) return true;
    }
    catch (Exception e) {}

    return false;
  }

  public static int[] findCount(String[][] tiles) {
    int[] count = new int[6];
    for (String[] line : tiles) {
      for (String letter : line) {
        switch (letter) {
          case "R": count[0]++;
          break;
          case "G": count[1]++;
          break;
          case "B": count[2]++;
          break;
          case "C": count[3]++;
          break;
          case "P": count[4]++;
          break;
          case "Y": count[5]++;
          break;
        }
      }
    }
    return count;
  } 

  public static void display() {
    for (String[][] lines : solutions) {
      for (String[] line : lines) {
        for (String letter : line) {
          System.out.print(letter);
        }
        System.out.println();
      }
      System.out.println("\n\n");
    }
  }
}