Попытка решить кубик Рубика в Java

Question

До сих пор я разработал класс, который может представлять кубик Рубика с использованием древовидной карты (лучший способ?), Каждый цвет отображается на ключ 0 - 53. ключи всегда остаются неизменными и представляются в виде 2D-представления куба. Я сделал метод rotate90, который возьмет цвет и повернет цвет лица (средние кубики никогда не будут двигаться) на 90 градусов по часовой стрелке. Поэтому мой вопрос заключается в том, как мне реализовать хороший поиск (может быть, A*?), Чтобы заставить этот куб двигаться в правильном направлении к его целевому состоянию (которое я также инициализировал в коде как глобальный, чтобы я мог сравнить его с Текущее состояние). Любая обратная связь или намеки в правильном направлении было бы здорово. Спасибо!

Вот код без метода rotate 90 и метода checkInput, который просто проверяет текст файла в порядке. Входные данные - это просто текстовый файл, который представляет 2D-куб и выглядит следующим образом. Метод решения сейчас - просто я бездельничаю и никуда не денусь.

   GGW
   RRG
   RRG
OWWGGOYYR
OGOYYYRBR
YYYRBGRWW
   BOY
   BOB
   BOB
   OGO
   WWB
   WWB

package rubik;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.NavigableMap;
import java.util.TreeMap;

public class RubikCube {
final static String FILE_NAME = "rubikTest.txt";
public TreeMap<Integer, Character> goalState;


//swaps two colors given a cube
public static void swapColorValue(int color1, int color2, TreeMap<Integer, Character> rubik){
    char tempColor = rubik.get(color1);
    rubik.put(color1,rubik.get(color2));
    rubik.put(color2, tempColor);
}

//initialize the goal map
public void goalInit(TreeMap<Integer, Character> rubik){
    //initialize the goal state map each rubik.get(magicNumber) is the static center cubie
    TreeMap<Integer, Character> goalMap = new TreeMap<Integer,Character>();
    for(int i =0;i<=8;i++){
    goalMap.put(i,rubik.get(4));
    }
    //the left side
    goalMap.put(9, rubik.get(19));
    goalMap.put(10, rubik.get(19));
    goalMap.put(11, rubik.get(19));
    goalMap.put(18, rubik.get(19));
    goalMap.put(19, rubik.get(19));
    goalMap.put(20, rubik.get(19));
    goalMap.put(27, rubik.get(19));
    goalMap.put(28, rubik.get(19));
    goalMap.put(29, rubik.get(19));
    //the middle
    goalMap.put(12, rubik.get(22));
    goalMap.put(13, rubik.get(22));
    goalMap.put(14, rubik.get(22));
    goalMap.put(21, rubik.get(22));
    goalMap.put(22, rubik.get(22));
    goalMap.put(23, rubik.get(22));
    goalMap.put(30, rubik.get(22));
    goalMap.put(31, rubik.get(22));
    goalMap.put(32, rubik.get(22));
    //right side
    goalMap.put(15, rubik.get(25));
    goalMap.put(16, rubik.get(25));
    goalMap.put(17, rubik.get(25));
    goalMap.put(24, rubik.get(25));
    goalMap.put(25, rubik.get(25));
    goalMap.put(26, rubik.get(25));
    goalMap.put(33, rubik.get(25));
    goalMap.put(34, rubik.get(25));
    goalMap.put(35, rubik.get(25));
    //bottom
    for(int i = 36;i<=44;i++){
        goalMap.put(i, rubik.get(40));
    }
    //back
    for(int i = 45;i<=53;i++){
        goalMap.put(i, rubik.get(49));
    }
    //give it to the global variable
    goalState = (TreeMap<Integer, Character>) goalMap.clone();

}

//Maps a Integer key to a color given a file.
public static NavigableMap<Integer, Character> setup(String file) throws IOException{
    TreeMap<Integer, Character> rubik = new TreeMap<Integer, Character>();
    BufferedReader br = new BufferedReader(new FileReader(file));
    try {
        StringBuilder sb = new StringBuilder();
        String line = br.readLine();
        //add each line (without white spaces) to the stringbuilder
        while (line != null) {
            sb.append(line.trim());
            line = br.readLine();
        }
        //convert the stringbuilder(which has all the input from the file) to a char array
        char [] colors = sb.toString().toCharArray();
        //put the key,color into the Treemap.
        for(int i =0; i < colors.length;i++){
            rubik.put(i, colors[i]);
        }
    } finally {
        br.close();
    }
    //type Tree map
    return rubik;

    }

public int solve(TreeMap<Integer, Character> rubik){
    int j = 1;
    int check = 0;
    int redMatches=0;
    char [] colors = {'r','g','y','b','o','w'};

    for(int i = 0; i < 100;i++ ){
        if(j==6) j = 1;
        redMatches = 0;
        rotate90(colors[j],rubik);
        if(rubik.get(check)==goalState.get(check)){
            System.out.print("rubik match at: "+i+" with: "+rubik.get(i)+"match at goalState: "+i+" with: "+goalState.get(i));
            redMatches++;
        }

        j++;
    }


    return redMatches;
}

public static void main (String[] args){
    try {
        //check if file input is good
        //System.out.print(new RubikCube().checkInput(FILE_NAME));
        //Map the rubik cube(key,Color)
        RubikCube cubeInst = new RubikCube();
        //make sure to set up the mapping before calling rotate and goalInit    
        TreeMap<Integer, Character> cube = (TreeMap<Integer, Character>) (setup(FILE_NAME));
        cubeInst.goalInit(cube);
        //System.out.print(cubeInst.goalState);
        //rotate90('y',cube);
        //rotate90('y',cube);
        //System.out.print(cube);
        System.out.print(cubeInst.solve(cube));
    } catch (IOException e) {
        e.printStackTrace();
    }
}

}

Answer 1

Я никогда не писал код для решения кубика Рубика, но если вы используете алгоритм обхода эвристического графа, такой как A*, я могу подумать о нескольких хороших эвристиках, чтобы сказать, как далеко вы от цели:

1. Количество неуместных хижин.

2. Суммирование того, как далеко каждый кубби находится от целевого состояния, возможно, используя расстояние до Манхэттена, чтобы сказать, как далеко он находится.

Проблема в том, что я не думаю, что вы можете просто использовать цвет для каждого состояния кубби. Возможно, вам придется представить куб в качестве позиции структуры данных под произвольным углом. Так, например, "верхний левый угол" - это верхний левый угловой элемент в состоянии цели (который также является угловым кубби с левой и задней сторон...). Тогда вы узнаете, вышел ли ваш кубби из "верхнего левого угла". места.