| Astaraki |
۰۵-۲۰-۱۳۸۹ ۱۰:۱۰ قبل از ظهر |
به زبان جاوا
Solution of the 8-puzzle using iterative deepening A* (IDA*) search
كد:
/*
Author: James Pate Williams, Jr.
Solution of 8-puzzle using IDA* search
*/
import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
class Puzzle8IPanel extends JPanel {
char[] s;
int deltaX, deltaY;
int x0, x1, y0, y1;
public Puzzle8IPanel(int iWidth, int iHeight, char[] solution) {
x0 = iWidth / 8;
x1 = 7 * x0;
y0 = iHeight / 8;
y1 = 7 * y0;
deltaX = (x1 - x0) / 3;
deltaY = (y1 - y0) / 3;
s = new char[9];
s = solution;
}
public void sevenSegmentDisplay(Graphics g, char digit,
int x, int y, int xUnit, int yUnit) {
int xInc = xUnit / 10;
int yInc = yUnit / 10;
int xPoint1 = x + xInc;
int yPoint1 = y + yInc;
int xPoint2 = x + xUnit - xInc;
int yPoint2 = yPoint1;
int xPoint3 = xPoint1;
int yPoint3 = y + yUnit / 2;
int xPoint4 = xPoint2;
int yPoint4 = yPoint3;
int xPoint5 = xPoint3;
int yPoint5 = y + yUnit - yInc;
int xPoint6 = xPoint4;
int yPoint6 = yPoint5;
g.setColor(Color.white);
switch (digit) {
case '0':
g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
g.drawLine(xPoint5, yPoint5, xPoint1, yPoint1);
break;
case '1':
g.drawLine(xPoint1, yPoint1, xPoint5, yPoint5);
break;
case '2':
g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
g.drawLine(xPoint2, yPoint2, xPoint4, yPoint4);
g.drawLine(xPoint4, yPoint4, xPoint3, yPoint3);
g.drawLine(xPoint3, yPoint3, xPoint5, yPoint5);
g.drawLine(xPoint5, yPoint5, xPoint6, yPoint6);
break;
case '3':
g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
g.drawLine(xPoint2, yPoint2, xPoint4, yPoint4);
g.drawLine(xPoint4, yPoint4, xPoint3, yPoint3);
g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
break;
case '4':
g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
g.drawLine(xPoint4, yPoint4, xPoint2, yPoint2);
g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
break;
case '5':
g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
break;
case '6':
g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
g.drawLine(xPoint5, yPoint5, xPoint3, yPoint3);
break;
case '7':
g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
break;
case '8':
g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
g.drawLine(xPoint5, yPoint5, xPoint1, yPoint1);
g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
break;
case '9':
g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
break;
}
}
public void paintComponent(Graphics g) {
int i, j, x, y;
int xUnit = deltaY / 9;
int yUnit = deltaY / 15;
super.paintComponent(g);
y = y0;
for (i = 0; i < 3; i++) {
x = x0;
for (j = 0; j < 3; j++) {
g.setColor(Color.white);
g.drawRect(x, y, deltaX, deltaY);
g.setColor(Color.black);
g.fillRect(x, y, deltaX, deltaY);
sevenSegmentDisplay(g, s[3 * i + j], x, y, deltaX, deltaY);
x += deltaX;
}
y += deltaY;
}
}
public void setSolution(char[] solution) {
s = new char[9];
s = solution;
}
}
class Puzzle8IFrame extends JFrame implements Runnable {
boolean next;
int iHeight, iWidth;
JButton jButton1 = new JButton();
JPanel jPanel = new JPanel();
BorderLayout borderLayout = new BorderLayout();
Puzzle8IPanel puzzle8IPanel;
// step 3 - percentage size the window
void setDesktopSize(JFrame frame, int wPerc, int hPerc) {
Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
iWidth = screen.width * wPerc / 100;
iHeight = screen.height * hPerc / 100;
frame.setSize(iWidth, iHeight);
}
// step 4 - center the window
void centerOnScreen(JFrame frame) {
Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
Dimension window = frame.getSize();
int iCenterX = screen.width / 2;
int iCenterY = screen.height / 2;
frame.setLocation(iCenterX - window.width / 2, iCenterY - window.height / 2);
}
public Puzzle8IFrame(char[] solution) {
String title = "Puzzle8I by James Pate Williams, Jr. (c) 2001";
next = false;
jButton1.setToolTipText("Perform one iteration of algorithm");
jButton1.setText("Next");
jButton1.setVerticalAlignment(SwingConstants.BOTTOM);
jButton1.addActionListener(new java.awt.event.ActionListener() {
public void actionPerformed(ActionEvent e) {
jButton1_actionPerformed(e);
}
});
this.getContentPane().setLayout(borderLayout);
setTitle(title);
addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent event) {
System.exit(0);
}
});
setDesktopSize(this, 100, 100);
centerOnScreen(this);
Container contentPane = getContentPane();
contentPane.add(jPanel, BorderLayout.SOUTH);
jPanel.add(jButton1, BorderLayout.CENTER);
puzzle8IPanel = new Puzzle8IPanel(iWidth, iHeight, solution);
contentPane.add(puzzle8IPanel, BorderLayout.CENTER);
this.show();
(new Thread(this)).run();
}
public boolean getNext() {
return next;
}
public void setNext(boolean n) {
next = n;
}
void jButton1_actionPerformed(ActionEvent e) {
next = true;
}
public void run() {
Thread.yield();
}
public void draw(char[] solution) {
puzzle8IPanel.setSolution(solution);
puzzle8IPanel.paintComponent(getGraphics());
}
}
class PuzzleI {
int flag, g, moves, nodesExpanded;
int[][] board;
Date date;
Random random;
public static final int Infinity = 2000000000;
public static final int MaxMoves = 100;
public PuzzleI() {
boolean found;
int digit, i, j, k;
int[] placed = new int[9];
date = new Date();
random = new Random(date.getTime());
for (i = 0; i < 9; i++)
placed[i] = 0;
board = new int[3][3];
g = moves = nodesExpanded = 0;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
board[i][j] = 0;
for (i = 0; i < 9; i++) {
found = false;
do {
digit = random.nextInt(9);
found = placed[digit] == 0;
if (found)
placed[digit] = 1;
} while (!found);
do {
j = random.nextInt(3);
k = random.nextInt(3);
found = board[j][k] == 0;
if (found)
board[j][k] = digit;
} while (!found);
}
}
int getNodesExpanded() {
return nodesExpanded;
}
int expand(int[][] square, int[][][] tempSquare) {
int b = - 1, col = - 1, i, j, k, row = - 1;
for (i = 0; i < 4; i++)
for (j = 0; j < 3; j++)
for (k = 0; k < 3; k++)
tempSquare[i][j][k] = square[j][k];
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
if (square[i][j] == 0) {
row = i;
col = j;
break;
}
}
}
if (row == 0 && col == 0) {
tempSquare[0][0][0] = tempSquare[0][0][1];
tempSquare[0][0][1] = 0;
tempSquare[1][0][0] = tempSquare[1][1][0];
tempSquare[1][1][0] = 0;
b = 2;
}
else if (row == 0 && col == 1) {
tempSquare[0][0][1] = tempSquare[0][0][0];
tempSquare[0][0][0] = 0;
tempSquare[1][0][1] = tempSquare[1][1][1];
tempSquare[1][1][1] = 0;
tempSquare[2][0][1] = tempSquare[2][0][2];
tempSquare[2][0][2] = 0;
b = 3;
}
else if (row == 0 && col == 2) {
tempSquare[0][0][2] = tempSquare[0][0][1];
tempSquare[0][0][1] = 0;
tempSquare[1][0][2] = tempSquare[1][1][2];
tempSquare[1][1][2] = 0;
b = 2;
}
else if (row == 1 && col == 0) {
tempSquare[0][1][0] = tempSquare[0][0][0];
tempSquare[0][0][0] = 0;
tempSquare[1][1][0] = tempSquare[1][1][1];
tempSquare[1][1][1] = 0;
tempSquare[2][1][0] = tempSquare[2][2][0];
tempSquare[2][2][0] = 0;
b = 3;
}
else if (row == 1 && col == 1) {
tempSquare[0][1][1] = tempSquare[0][1][0];
tempSquare[0][1][0] = 0;
tempSquare[1][1][1] = tempSquare[1][0][1];
tempSquare[1][0][1] = 0;
tempSquare[2][1][1] = tempSquare[2][1][2];
tempSquare[2][1][2] = 0;
tempSquare[3][1][1] = tempSquare[3][2][1];
tempSquare[3][2][1] = 0;
b = 4;
}
else if (row == 1 && col == 2) {
tempSquare[0][1][2] = tempSquare[0][0][2];
tempSquare[0][0][2] = 0;
tempSquare[1][1][2] = tempSquare[1][1][1];
tempSquare[1][1][1] = 0;
tempSquare[2][1][2] = tempSquare[2][2][2];
tempSquare[2][2][2] = 0;
b = 3;
}
else if (row == 2 && col == 0) {
tempSquare[0][2][0] = tempSquare[0][1][0];
tempSquare[0][1][0] = 0;
tempSquare[1][2][0] = tempSquare[1][2][1];
tempSquare[1][2][1] = 0;
b = 2;
}
else if (row == 2 && col == 1) {
tempSquare[0][2][1] = tempSquare[0][2][0];
tempSquare[0][2][0] = 0;
tempSquare[1][2][1] = tempSquare[1][1][1];
tempSquare[1][1][1] = 0;
tempSquare[2][2][1] = tempSquare[2][2][2];
tempSquare[2][2][2] = 0;
b = 3;
}
else if (row == 2 && col == 2) {
tempSquare[0][2][2] = tempSquare[0][2][1];
tempSquare[0][2][1] = 0;
tempSquare[1][2][2] = tempSquare[1][1][2];
tempSquare[1][1][2] = 0;
b = 2;
}
return b;
}
int heuristic(int[][] square) {
return ManhattenDistance(square);
}
int DFSContour(char[][] solution, int fLimit, int m, int[][] board) {
boolean equal, skip;
char[] tempSolution = new char[9];
int b, count, fCost, i, j, k, l, n, newF, nextF = Infinity;
int[][][] tempSquare = new int[4][3][3];
fCost = g + heuristic(board);
for (i = k = 0; i < 3; i++)
for (j = 0; j < 3; j++)
solution[m][k++] = (char) (board[i][j] + '0');
m++;
if (m == MaxMoves)
return Infinity;
if (fCost > fLimit) {
flag = 0;
return fCost;
}
if (board[0][0] == 1 && board[0][1] == 2 && board[0][2] == 3 &&
board[1][0] == 8 && board[1][1] == 0 && board[1][2] == 4 &&
board[2][0] == 7 && board[2][1] == 6 && board[2][2] == 5) {
flag = 1;
moves = m;
return fCost;
}
b = expand(board, tempSquare);
nodesExpanded += b;
for (i = 0; i < b; i++) {
skip = false;
for (j = m - 1; !skip && j < m; j++) {
for (k = l = 0; k < 3; k++)
for (n = 0; n < 3; n++)
tempSolution[l++] = (char) (tempSquare[i][k][n] + '0');
equal = tempSolution[0] == solution[j][0];
for (k = 1; equal && k < 9; k++)
equal = tempSolution[k] == solution[j][k];
if (equal)
skip = true;
}
if (!skip) {
newF = DFSContour(solution, fCost, m, tempSquare[i]);
if (flag == 1)
return newF;
nextF = newF < nextF ? newF : nextF;
}
}
g++;
return nextF;
}
int outOfPlace(int[][] square) {
int i, j, oop = 0;
int[][] goal = new int[3][3];
goal[0][0] = 1;
goal[0][1] = 2;
goal[0][2] = 3;
goal[1][0] = 8;
goal[1][1] = 0;
goal[1][2] = 4;
goal[2][0] = 7;
goal[2][1] = 6;
goal[2][2] = 5;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
if (square[i][j] != goal[i][j])
oop++;
return oop;
}
int ManhattenDistance(int[][] square) {
// city block or Manhatten distance heuristic
int md = 0;
if (square[0][0] == 1)
md += 0;
else if (square[0][0] == 2)
md += 1;
else if (square[0][0] == 3)
md += 2;
else if (square[0][0] == 4)
md += 3;
else if (square[0][0] == 5)
md += 4;
else if (square[0][0] == 6)
md += 3;
else if (square[0][0] == 7)
md += 2;
else if (square[0][0] == 8)
md += 1;
if (square[0][1] == 1)
md += 1;
else if (square[0][1] == 2)
md += 0;
else if (square[0][1] == 3)
md += 1;
else if (square[0][1] == 4)
md += 2;
else if (square[0][1] == 5)
md += 3;
else if (square[0][1] == 6)
md += 2;
else if (square[0][1] == 7)
md += 3;
else if (square[0][1] == 8)
md += 2;
if (square[0][2] == 1)
md += 2;
else if (square[0][2] == 2)
md += 1;
else if (square[0][2] == 3)
md += 0;
else if (square[0][2] == 4)
md += 1;
else if (square[0][2] == 5)
md += 2;
else if (square[0][2] == 6)
md += 3;
else if (square[0][2] == 7)
md += 4;
else if (square[0][2] == 8)
md += 3;
if (square[1][0] == 1)
md += 1;
else if (square[1][0] == 2)
md += 2;
else if (square[1][0] == 3)
md += 3;
else if (square[1][0] == 4)
md += 2;
else if (square[1][0] == 5)
md += 3;
else if (square[1][0] == 6)
md += 2;
else if (square[1][0] == 7)
md += 1;
else if (square[1][0] == 8)
md += 0;
if (square[1][1] == 1)
md += 2;
else if (square[1][1] == 2)
md += 1;
else if (square[1][1] == 3)
md += 2;
else if (square[1][1] == 4)
md += 1;
else if (square[1][1] == 5)
md += 2;
else if (square[1][1] == 6)
md += 1;
else if (square[1][1] == 7)
md += 2;
else if (square[1][1] == 8)
md += 1;
if (square[1][2] == 1)
md += 3;
else if (square[1][2] == 2)
md += 2;
else if (square[1][2] == 3)
md += 1;
else if (square[1][2] == 4)
md += 0;
else if (square[1][2] == 5)
md += 1;
else if (square[1][2] == 6)
md += 2;
else if (square[1][2] == 7)
md += 3;
else if (square[1][2] == 8)
md += 2;
if (square[2][0] == 1)
md += 2;
else if (square[2][0] == 2)
md += 3;
else if (square[2][0] == 3)
md += 4;
else if (square[2][0] == 4)
md += 3;
else if (square[2][0] == 5)
md += 2;
else if (square[2][0] == 6)
md += 1;
else if (square[2][0] == 7)
md += 0;
else if (square[2][0] == 8)
md += 1;
if (square[2][1] == 1)
md += 3;
else if (square[2][1] == 2)
md += 2;
else if (square[2][1] == 3)
md += 3;
else if (square[2][1] == 4)
md += 2;
else if (square[2][1] == 5)
md += 1;
else if (square[2][1] == 6)
md += 0;
else if (square[2][1] == 7)
md += 1;
else if (square[2][1] == 8)
md += 2;
if (square[2][2] == 1)
md += 4;
else if (square[2][2] == 2)
md += 3;
else if (square[2][2] == 3)
md += 2;
else if (square[2][2] == 4)
md += 1;
else if (square[2][2] == 5)
md += 0;
else if (square[2][2] == 6)
md += 1;
else if (square[2][2] == 7)
md += 2;
else if (square[2][2] == 8)
md += 3;
return md;
}
boolean solve(char[][] solution) {
boolean found;
int fCost, i, j, k, m = 0;
fCost = DFSContour(solution, Infinity, 0, board);
if (flag == 1)
return true;
else if (fCost == Infinity)
return false;
return false;
}
int getMoves() {
return moves;
}
}
class Puzzle8I implements Runnable {
char[][] solution = null;
int moves;
PuzzleI puzzleI = null;
public Puzzle8I () {
solution = new char[PuzzleI.MaxMoves][9];
do
puzzleI = new PuzzleI();
while (!puzzleI.solve(solution));
}
public void run() {
Puzzle8IFrame puzzle8IFrame = new Puzzle8IFrame(solution[0]);
moves = puzzleI.getMoves() - 1;
System.out.println("moves = " + moves);
for (int i = 1; i < moves + 1; i++) {
while (!puzzle8IFrame.getNext())
Thread.yield();
puzzle8IFrame.setNext(false);
puzzle8IFrame.draw(solution[i]);
}
}
static void main(String[] arg) {
(new Puzzle8I()).run();
}
}
|
