Всем дня,
Я попробовал решение для восьми задач головоломки, опубликованных здесь
Джоэл Нили и поиграл с ним и изменил его, чтобы можно было использовать его для решения для более высоких сеток
логика соответственно. Однако модифицированный код может решить сетки 3х3, но быстро исчерпает пространство кучи для сетки 4х4. Я думаю, что это ограничение, вызванное используемым алгоритмом, который я думаю, что некоторые
вариация ветви и границы, а не вариация Java. Если мои предположения верны, может кто-нибудь предложить какие-нибудь другие хорошие алгоритмы для решения этой проблемы? Если нет, пожалуйста, подскажите, что можно сделать, чтобы сделать эту программу
работа для сеток более высокого порядка.
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
class EightPuzzle {
//Queue<Integer[][]> agenda = new LinkedList<Integer[][]>(); // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
//Map<Integer[][],Integer> stateDepth = new HashMap<Integer[][], Integer>(); // HashMap is used to ignore repeated nodes
//Map<Integer[][],Integer[][]> stateHistory = new HashMap<Integer[][],Integer[][]>(); // relates each position to its predecessor
Map<String,String> stateHistory = new HashMap<String,String>(); // relates each position to its predecessor
Map<String,Integer> stateDepth = new HashMap<String,Integer>();
Queue<Integer[][]> agenda=new LinkedList<Integer[][]>();
final int GRIDSIZE=4;
int row=0,col=0;
public static void main(String args[]){
// Integer[][] str="087465132"; // Input the Board State as a Integer[][] with 0 as the Blank Space
Integer init[][]={{1,3,12,4},{2,9,10,7},{0,14,8,15},{5,6,13,11}};
//Integer init[][]={{0,8,7},{4,6,5},{1,3,2}};
EightPuzzle e = new EightPuzzle(); // New Instance of the EightPuzzle
e.add(init,null); // Add the Initial State
while(!e.agenda.isEmpty()){
Integer[][] currentState = e.agenda.remove();
e.up(currentState); // Move the blank space up and add new state to queue
e.down(currentState); // Move the blank space down
e.left(currentState); // Move left
e.right(currentState); // Move right and remove the current node from Queue
}
System.out.println("Solution doesn't exist");
}
//Add method to add the new Integer[][] to the Map and Queue
void add(Integer newState[][], Integer oldState[][]){
if(!stateDepth.containsKey(convertToString(newState))){
int newValue = oldState == null ? 0 : stateDepth.get(convertToString(oldState)) + 1;
stateDepth.put(convertToString(newState), newValue);
agenda.add(newState);
stateHistory.put(convertToString(newState), convertToString(oldState));
}
}
/* Each of the Methods below Takes the Current State of Board as Integer[][]. Then the operation to move the blank space is done if possible.
After that the new Integer[][] is added to the map and queue.If it is the Goal State then the Program Terminates.
*/
void up(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(row!=0){
nextState[row-1][col]=currentState[row][col];
nextState[row][col]=currentState[row-1][col];
checkCompletion(currentState, nextState);
}
}
/**
* @param currentState
*/
/**
* @param currentState
*/
void down(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(row!=GRIDSIZE-1){
nextState[row+1][col]=currentState[row][col];
nextState[row][col]=currentState[row+1][col];
checkCompletion(currentState, nextState);
}
}
void left(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(col!=0){
nextState[row][col-1]=currentState[row][col];
nextState[row][col]=currentState[row][col-1];
checkCompletion(currentState, nextState);
}
}
void right(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(col!=GRIDSIZE-1){
nextState[row][col+1]=currentState[row][col];
nextState[row][col]=currentState[row][col+1];
checkCompletion(currentState, nextState);
}
}
private void checkCompletion(Integer[][] oldState, Integer[][] newState) {
add(newState, oldState);
Integer[][] completeState={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};
//Integer[][] completeState={{1,2,3},{4,5,6},{7,8,0}};
boolean equality=true;
outer:for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
if(newState[i][j]!=completeState[i][j]){
equality=false;
break outer;
}
}
}
if(equality){
System.out.println("Solution Exists at Level "+stateDepth.get(convertToString(newState))+" of the tree");
String traceState = convertToString(newState);
while (traceState != null) {
System.out.println(traceState + " at " + stateDepth.get(traceState));
traceState = stateHistory.get(traceState);
}
System.exit(0);
}
}
String convertToString(Integer[][] a){
String str="";
if(a!=null){
for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
str+=a[i][j];
}
}
}
else{
str=null;
}
return str;
}
void getIndicesOfZero(Integer[][] currentState,Integer[][] nextState){
for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
nextState[i][j]=currentState[i][j];
}
}
outer:for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
if(currentState[i][j]==0){
row=i;
col=j;
break outer;
}
}
}
}
}
Спасибо заранее,
Пол.