最終的に単純な 8 パズルを解くことができる深さ優先検索アルゴリズムを作成しています。ファイルと目標状態を読み込み、それに応じてこれらの変数を設定できます。
私が受け取っている主な問題は、評価されている現在のノードの子を取得すると、8 パズルで 2 つの「空の」値が取得され、範囲外のインデックスも取得されるということです。
特定の親の子ノードを取得するには、最初に有効な移動を行い、有効な移動の結果を反映するように子ノードの状態を更新する必要があります。
移動を実行するために、実行可能かどうかを確認します (左に移動しても、パズルの境界内に留まります)。投稿されたコードを参照してください。
期待される結果を正しく出力するため、左と下の最初の 2 つの移動で正しく機能します。
以下は、現在のコード実行の出力です。左と下に正しく移動し、エラーが発生し始めることがわかります。
Start state:
120
345
678
after moving left
102
345
678
Parent: [[C@1b845568
after moving down
125
340
678
Parent: [[C@d032cf5
after moving left
102
340
678
Parent: [[C@d032cf5
after moving down
125
348
670
Parent:
125
340
678
after moving up
125
348
670
Parent: [[C@4b7c8f7f
after moving left
125
304
670
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
at dcs.aber.ac.uk.puzzle.PuzzleBoard.swapValues(PuzzleBoard.java:193)
at dcs.aber.ac.uk.puzzle.PuzzleBoard.moveUp(PuzzleBoard.java:142)
at dcs.aber.ac.uk.puzzle.DFSSolver.addChildren(DFSSolver.java:155)
at dcs.aber.ac.uk.puzzle.DFSSolver.search(DFSSolver.java:85)
at dcs.aber.ac.uk.puzzle.DFSSolver.<init>(DFSSolver.java:27)
at dcs.aber.ac.uk.puzzle.Driver.main(Driver.java:86)
ご覧のとおり、最初の 2 つの後、残りの印刷された状態は正しくありません。複雑な問題が発生した場所を特定できるかどうかを確認するために、ボードのスワッピングと更新をどのように処理するかを示すコードを投稿します。
public class Node {
private Node parent;
private char[][] state = new char[3][3];
private double cost;
private double heurCost;
private double funcCost;
private int depth;
public Node() {
parent = null;
}
public Node(Node parent) {
this.parent = parent;
for(int i = 0; i < 3; i++){
for(int j = 0; j< 3; j++){
state[i][j] = parent.getState()[i][j];
}
}
}
public void setParent(Node parent) {
this.parent = parent;
}
public char[][] getState() {
return state;
}
public char[][] copyState(){
char[][] a = new char[3][3];
for(int i = 0; i < 3; i++){
for(int j = 0; j< 3; j++){
a[i][j] = state[i][j];
}
}
return a;
}
}
public class PuzzleBoard {
private char[][] goalState;
private char[][] currentBoard;
private int emptyRow, emptyCol;
private int outOfPlace;
public PuzzleBoard(char[][] currentState, char[][] goal ){
this.setCurrentState(currentState);
this.setGoalState(goal);
trackEmptySqaure();
}
public void setGoalState(char[][] goalState){
this.goalState = goalState;
}
public void setCurrentState(char[][] currentState){
this.currentBoard = currentState;
}
public char[][] getCurrentBoard() {
return currentBoard;
}
public boolean checkIsGoal(char[][] board){
for(int i = 0; i < 9; i ++){
for(int j = 0; j < 3; j ++){
if(!(goalState[i][j] != (board[i][j]))){
return false;
}
}
}
return true;
}
public void trackEmptySqaure() {
for(int i = 0; i < 3; i ++){
for (int j = 0; j < 3; j ++){
if(currentBoard[i][j] == '0'){
emptyCol = j;
emptyRow = i;
}
}
}
}
public int getemptyRow() {
return emptyRow;
}
public int getemptyCol() {
return emptyCol;
}
public Node moveLeft(Node parent){
currentBoard = parent.copyState();
Node result = new Node(parent);
/* check you can move 'empty' left one space*/
if(getemptyCol() > 0){
swapValues(result.getState(),emptyRow, emptyCol, 1);
return result;
}
return null;
}
public Node moveDown(Node parent){
currentBoard = parent.copyState();
Node result = new Node(parent);
/* check you can move 'empty' down one space*/
if(getemptyRow() < 2){
swapValues(result.getState(),emptyRow, emptyCol,2);
return result;
}
return null;
}
public Node moveUp(Node parent){
currentBoard = parent.getState();
Node result = new Node(parent);
/* check you can move 'empty' up one space*/
if(getemptyRow() > 0){
swapValues(result.getState(),emptyRow, emptyCol,2);
return result;
}
return null;
}
public Node moveRight(Node parent){
currentBoard = parent.getState();
Node result = new Node(parent);
/* check you can move 'empty' right one space*/
if(getemptyCol() < 2){
swapValues(result.getState(),emptyRow, emptyCol,2);
return result;
}
return null;
}
public void swapValues (char[][] c,int x, int y, int method){
char empty = '0';
char swapValue = '0'; // should never be kept as 0
if(method == 1){ // left
swapValue= c[emptyRow][emptyCol -1];
c[emptyRow][emptyCol] = swapValue;
c[emptyRow][emptyCol -1] = empty;
trackEmptySqaure();
}
else if(method == 2){ // down
swapValue = c[emptyRow + 1][emptyCol];
c[emptyRow][emptyCol] = swapValue;
c[emptyRow + 1][emptyCol] = empty;
trackEmptySqaure();
}
else if(method == 3){ // up
swapValue = c[emptyRow -1][emptyCol];
c[emptyRow][emptyCol] = swapValue;
c[emptyRow -1][emptyCol] = empty;
trackEmptySqaure();
}
else if(method == 4){// right
swapValue = c[emptyRow][emptyCol + 1];
c[emptyRow][emptyCol] = swapValue;
c[emptyRow ][emptyCol + 1] = empty;
trackEmptySqaure();
}
}
public class DFSSolver {
private ArrayList<Node> closed = new ArrayList<Node>();
private Stack<Node> open = new Stack<Node>();
private PuzzleBoard pb;
private boolean solved;
private int numberOfSteps;
public DFSSolver(PuzzleBoard puzzle) {
pb = puzzle;
numberOfSteps = 0;
solved = false;
Node root = new Node();
root.setState(pb.getCurrentBoard());
addToOpen(root);
checkIfSolved(root);
search();
}
public boolean inOpenList(Node n){
for(Node node: open){
if(node.equals(n)){
return true;
}
}
return false;
}
public boolean inClosedList(Node n){
for(Node node: closed){
if(node.equals(n)){
return true;
}
}
return false;
}
public void addToOpen(Node n){
open.push(n);
}
public void addToClosed(Node n){
closed.add(n);
}
public Node popOpen(){
return open.pop();
}
public void removeFromClosed(Node n){
closed.remove(n);
}
public void search(){
while(!solved){
Node current = popOpen();
if(current != null){
if(!(inClosedList(current))){ // is it previously explored?
checkIfSolved(current);
addChildren(current);
numberOfSteps++;
}
addToClosed(current);
}
}
System.out.println("No of steps: " + numberOfSteps);
}
public void checkIfSolved(Node curr) {
char[][] goal = pb.getGoal();
char[][] current = curr.getState();
for(int i = 0; i < 3; i ++){
for(int j = 0; j < 3; j ++){
char c = current[i][j];
char x = goal[i][j];
if(c != x){
return;
}
}
}
solved = true;
}
public void addChildren(Node parent){
Node newNode = new Node(parent);
newNode = pb.moveLeft(parent);
if(newNode != null){
System.out.println("Parent: " + parent.getState().toString());
System.out.println("atfer moving left");
System.out.println(newNode.toString());
addToOpen(newNode);
}
newNode = pb.moveDown(parent);
if(newNode != null){
System.out.println("Parent: " + parent.getState().toString());
System.out.println("atfer moving down");
System.out.println(newNode.toString());
addToOpen(newNode);
}
newNode = pb.moveRight(parent);
if(newNode != null){
System.out.println("Parent: " + parent.getState().toString());
System.out.println("atfer moving right");
System.out.println(newNode.toString());
addToOpen(newNode);
}
newNode = pb.moveUp(parent);
if(newNode != null){
System.out.println("Parent:\n " + parent.toString());
System.out.println("atfer moving up");
System.out.println(newNode.toString());
addToOpen(newNode);
}
}