Category: 8-Puzzle and 15-Puzzle
Blog Entry © Sunday, November 23, 2025, by James Pate Williams, Jr. Modification of My A* Informed Search Solver for the 8-Tile Puzzle
Blog Entry © Friday, November 21, 2025, by James Pate Williams, Jr., Win32 C/C++ Desktop GUI Solution of the 15-Tile Puzzle Using Iterative Deepening A* Informed Seach Algorithm
Solution of the 8-Puzzle Using Java by James Pate Williams, Jr.
/*
Author: James Pate Williams, Jr.
Solution of 8-puzzle using A* search
*/
import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
class Puzzle8Panel extends JPanel {
char[] s;
int deltaX, deltaY;
int x0, x1, y0, y1;
public Puzzle8Panel(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 Puzzle8Frame extends JFrame implements Runnable {
boolean next;
int iHeight, iWidth;
JButton jButton1 = new JButton();
JPanel jPanel = new JPanel();
BorderLayout borderLayout = new BorderLayout();
Puzzle8Panel puzzle8Panel;
// 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 Puzzle8Frame(char[] solution) {
String title = "Puzzle8 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);
puzzle8Panel = new Puzzle8Panel(iWidth, iHeight, solution);
contentPane.add(puzzle8Panel, 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) {
puzzle8Panel.setSolution(solution);
puzzle8Panel.paintComponent(getGraphics());
}
}
class Puzzle {
int g, nodesExpanded;
int[][] board;
Date date;
Random random;
public static final int MaxMoves = 100;
public Puzzle() {
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 = 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);
}
boolean move() {
int b, count, i, j, k, min;
int[] f = new int[4], index = new int[4];
int[][][] tempSquare = new int[4][3][3];
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)
return true;
b = expand(board, tempSquare);
for (i = 0; i < b; i++) {
f[i] = g + heuristic(tempSquare[i]);
for (j = 0; j < 3; j++)
for (k = 0; k < 3; k++)
board[j][k] = tempSquare[i][j][k];
}
// find the node of minimum f
min = f[0];
for (i = 1; i < b; i++)
if (f[i] < min)
min = f[i];
for (count = i = 0; i < b; i++)
if (f[i] == min)
index[count++] = i;
i = index[random.nextInt(count)];
// increment the cost of the path thus far
g++;
nodesExpanded += b;
for (j = 0; j < 3; j++)
for (k = 0; k < 3; k++)
board[j][k] = tempSquare[i][j][k];
return false;
}
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;
}
int solve(char[][] solution) {
boolean found;
int i, j, k, m = 0;
do {
for (i = k = 0; i < 3; i++)
for (j = 0; j < 3; j++)
solution[m][k++] = (char) (board[i][j] + '0');
found = move();
m++;
} while (!found && m < MaxMoves);
for (i = k = 0; i < 3; i++)
for (j = 0; j < 3; j++)
solution[m][k++] = (char) (board[i][j] + '0');
return m;
}
}
class Puzzle8 implements Runnable {
char[][] solution = null;
int moves;
public Puzzle8 () {
solution = new char[Puzzle.MaxMoves + 1][9];
do {
Puzzle puzzle = new Puzzle();
moves = puzzle.solve(solution);
} while (moves == Puzzle.MaxMoves);
}
public void run() {
Puzzle8Frame puzzle8Frame = new Puzzle8Frame(solution[0]);
System.out.println("moves = " + moves);
for (int i = 0; i < moves; i++) {
while (!puzzle8Frame.getNext())
Thread.yield();
puzzle8Frame.setNext(false);
puzzle8Frame.draw(solution[i]);
}
puzzle8Frame.draw(solution[moves]);
}
static void main(String[] arg) {
(new Puzzle8()).run();
}
}
Iterative Deepening A* Search to Solve the 8-Puzzle and 15-Puzzle by James Pate Williams, Jr.
The 8-puzzle is a child’s tiled toy. The toy consists of 8 numbered tiles and a blank space. The object of the game is to get the tiles in the order 1 to 8 going from the top left hand corner for the number 1 tile around the perimeter clockwise and finish with the space in the center of the 3 x 3 board.
A* search is a complete and optimal informed or heuristic search algorithm. A good source for information on uniformed and informed search procedures is the tome “Artificial Intelligence A Modern Approach First and/or Second Edition” by Stuart Russell and Peter Norvig. The second edition has more info on the 8-puzzle and the 15-puzzle. Iterative deepening A* search is also a complete and optimal search algorithm. Below is an instance of the 8-puzzle that requires 10 steps to reach the goal state. I use a different goal state than Russell and Norvig in the second edition of their textbook.
I developed an application in 2015 that uses 5 search algorithms to solve instances of the 15-puzzle.
Numerical Explorations 