package Taci_Algorithm;
/*
* Mục đích: Quản lý nghiệp vụ về đỉnh của bài toán Taci
* Người viết:
* Ngày viết:
* Version:
*/
import [Link].*;
public class Vertex {
private int[][] state, goal;
private int cost;
private int heuristic;
private Vertex parent;
private int row, col;
public Vertex(int[][] state, int goal[][], int cost) {
[Link] = state;
[Link] = goal;
[Link] = cost;
[Link] = calculateHeuristic();
public void setRowCol(int row, int col) {
[Link] = col;
[Link] = row;
}
// public Vertex(int[][] state, int cost) {
// [Link] = state;
// [Link] = cost;
// }
public int[][] getState() {
return state;
public void setGoal(int goal[][]) {
[Link] = goal;
public int getCost() {
return cost;
public int getHeuristic() {
return heuristic;
public Vertex getParent() {
return parent;
public List<Vertex> getNeighbors() {
List<Vertex> neighbors = new ArrayList<>();
// danh sach cac node ke
for (int[] move : getValidMoves()) {
int[][] newState = [Link](state).map(int[]::clone).toArray(int[][]::new);
swap(newState, row, col, move[0], move[1]);
Vertex neighbor = new Vertex(newState, goal, cost + 1);
[Link] = this;
[Link] = move[0];
[Link] = move[1];
[Link](neighbor);
return neighbors;
private List<int[]> getValidMoves() {
List<int[]> moves = new ArrayList<>();
for (int[] move : new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }) {
int newRow = row + move[0];
int newCol = col + move[1];
if (newRow >= 0 && newRow < 3 && newCol >= 0 && newCol < 3) {
[Link](new int[] { newRow, newCol });
return moves;
public int calculateHeuristic() {
int distance = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (i != 1 || j != 1)
if (state[i][j] != goal[i][j])
distance++;
return distance ;
private void swap(int[][] state, int i, int j, int x, int y) {
int temp = state[i][j];
state[i][j] = state[x][y];
state[x][y] = temp;
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (o == null || getClass() != [Link]())
return false;
Vertex node = (Vertex) o;
return [Link](state, [Link]);
@Override
public int hashCode() {
return [Link](state);
}
package Taci_Algorithm;
import [Link].*;
public class Taci {
private PriorityQueue<Vertex> queue;
private Set<Vertex> visited;
private int[][] goal;
public Taci(int[][] start, int[][] goal, int row, int col) {
[Link] = new HashSet<>();
[Link] = goal;
Vertex startNode = new Vertex(start, goal, 0);
[Link] = new
PriorityQueue<>([Link](Vertex::getHeuristic));
[Link](row, col);
[Link](startNode);
}
public List<Vertex> solve() {
int i = 0;
while (![Link]()) {
[Link]("Loop " + (i++));
// In thông tin về đỉnh đang xét
Vertex current = [Link]();
int[][] currentState = [Link]();
[Link]("Đỉnh đang xét: ");
for (int[] row : currentState) {
[Link]([Link](row) + " ");
}
[Link]("\ng: " + [Link]() + "\th: "
+ [Link]() + "\tf: "
+ ([Link]() + [Link]()));
// In thông tin về đỉnh kề
[Link]("Đỉnh kề với v: ");
for (Vertex neighbor : [Link]()) {
int[][] neighborState = [Link]();
for (int[] row : neighborState) {
[Link]([Link](row) + " ");
}
[Link]("\ng: " + [Link]() +
"\th: " + [Link]() + "\tf: "
+ ([Link]() +
[Link]()) + " ");
}
[Link]();
// In thông tin về hàng đợi Open
[Link]("Open:");
for (Vertex node : queue) {
int[][] state = [Link]();
[Link]([Link](state) + " ");
[Link]("g: " + [Link]() + " h: "
+ [Link]() + " f: "
+ ([Link]() + [Link]()));
}
// In thông tin về tập Closed
[Link]("\nClosed:");
for (Vertex v : visited) {
int[][] state = [Link]();
[Link]([Link](state) + " ");
[Link]("g: " + [Link]() + " h: " +
[Link]() + " f: "
+ ([Link]() + [Link]()));
}
[Link]("---------------------\n\n");
[Link](current);
if ([Link]([Link](), goal)) {
[Link]("Goal reached!");
return getPath(current);
}
for (Vertex neighbor : [Link]())
if ()
[Link](neighbor);
}
[Link]("No solution found!");
return null;
}
private List<Vertex> getPath(Vertex end) {
List<Vertex> path = new ArrayList<>();
Vertex current = end;
while (current != null) {
[Link](current);
current = [Link]();
}
[Link](path);
return path;
}
public static void main(String[] args) {
int[][] start = { { 2, 8, 3 }, { 1, 6, 4 }, { 7, 0, 5 } };
int[][] goal = { { 1, 2, 3 }, { 8, 0, 4 }, { 7, 6, 5 } };
int r = 2, c = 1;
Taci solver = new Taci(start, goal, r, c);
List<Vertex> solution = [Link]();
if (solution == null) {
[Link]("No Result!");
} else {
[Link]("Result: ");
for (Vertex node : solution) {
int[][] state = [Link]();
[Link]("----------");
for (int[] row : state) {
[Link]([Link](row));
}
}
[Link]("----------");
}
}
}