我正try 在八个拼图游戏中使用广度优先搜索(BFS).代码可以根据BFS规则成功地移动拼图块，并用尽可能性列表.然而，它最终未能找到解决方案.//////////////////////////p>
node 类定义网格以及拼图如何移动，以判断重复和目标.//////////////////////////p>
public class Node
{
public List<Node> children = new List<Node>(); ////////////////////////////////////////////////////// List to store child nodes
public Node parent; ////////////////////////////////////////////////////// Reference to the parent node
public int[] puzzle = new int[9]; ////////////////////////////////////////////////////// one dimensional array to represent the grid.
public int x = 0; ////////////////////////////////////////////////////// Variable to store the index of the empty tile
public int col = 3;
public Node(int[] p)
{
Set_Puzzle(p);
}
public void Set_Puzzle(int[] p)
{
////////////////////////////////////////////////////// Copies the input puzzle array to the current node's puzzle array
for (int i = 0; i < puzzle.Length; i++)
{
this.puzzle[i] = p[i];
}
}
public bool GoalState()
{
////////////////////////////////////////////////////// Checks if the current puzzle state matches the goal state
int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
return arr.SequenceEqual(puzzle);
}
public void Expand_Node()
{
////////////////////////////////////////////////////// Generates child nodes by moving the empty tile in different directions
for (int i = 0; i < puzzle.Length; i++)
{
if (puzzle[i] == 0)
{
x = i;
break;
}
}
Move_To_Right(puzzle, x);
Move_Down(puzzle, x);
Move_To_Left(puzzle, x);
Move_Up(puzzle, x);
}
public void Move_To_Right(int[] p, int i)
{
////////////////////////////////////////////////////// Moves the empty tile to the right, creating a new child node
if (i % col < col - 1)
{
int[] pc = new int[9];
Copy_Puzzle(pc, p);
int temp = pc[i + 1];
pc[i + 1] = pc[i];
pc[i] = temp;
Node child = new Node(pc);
children.Add(child);
child.parent = this;
}
}
public void Move_To_Left(int[] p, int i)
{
if (i % col < 0)
{
int[] pc = new int[9];
Copy_Puzzle(pc, p);
int temp = pc[i - 1];
pc[i - 1] = pc[i];
pc[i] = temp;
Node child = new Node(pc);
children.Add(child);
child.parent = this;
}
}
public void Move_Up(int[] p, int i)
{
if (i - col >= 0)
{
int[] pc = new int[9];
Copy_Puzzle(pc, p);
int temp = pc[i - 3];
pc[i - 3] = pc[i];
pc[i] = temp;
Node child = new Node(pc);
children.Add(child);
child.parent = this;
}
}
public void Move_Down(int[] p, int i)
{
if (i + col <= 8)
{
int[] pc = new int[9];
Copy_Puzzle(pc, p);
int temp = pc[i + 3];
pc[i + 3] = pc[i];
pc[i] = temp;
Node child = new Node(pc);
children.Add(child);
child.parent = this;
}
}
public void Copy_Puzzle(int[] a, int[] b)
{
////////////////////////////////////////////////////// Copies the elements from one array to another
for (int i = 0; i < b.Length; i++)
{
a[i] = b[i];
}
}
public void Print_Console()
{
Console.WriteLine();
int m = 0;
for (int i = 0; i < col; i++)
{
for (int j = 0; j < col; j++)
{
Console.Write(puzzle[m] + " ");
m++;
}
Console.WriteLine();
}
}
public bool SameP(int[] p)
{
return puzzle.SequenceEqual(p);
}
//////////////////////////code>//////////////////////////pre>
BFS算法://////////////////////////p>
public List<Node> BFS(Node root)
{
////////////////////////////////////////////////////// Performs Breadth-First Search starting from the root node
List<Node> path_to_solution = new List<Node>(); ////////////////////////////////////////////////////// List to store the path to the solution
Queue<Node> frontier = new Queue<Node>(); ////////////////////////////////////////////////////// Queue to track nodes to visit
List<Node> visited = new List<Node>(); ////////////////////////////////////////////////////// List to store visited nodes
frontier.Enqueue(root);
bool goal_found = false;
while (frontier.Count > 0 && !goal_found)
{
Node current_node = frontier.Dequeue();
visited.Add(current_node);
if (current_node.GoalState())
{
Console.WriteLine("Goal Found");
goal_found = true;
Path_Tracer(path_to_solution, current_node);
break;
}
////////////////////////////////////////////////////// Expanding the current node by generating its child nodes and add them to the frontier queue
current_node.Expand_Node(); ////////////////////////////////////////////////////// Generate child nodes by moving the empty tile in different possible directions
current_node.Print_Console(); ////////////////////////////////////////////////////// Print the current puzzle grid to the console to check if its working properly
////////////////////////////////////////////////////// Enqueue unvisited child nodes to the frontier
for (int i = 0; i < current_node.children.Count; i++)
{
Node current_child = current_node.children[i];
if (!Contains(frontier.ToList(), current_child) && !Contains(visited, current_child))
{
frontier.Enqueue(current_child);
}
}
}
return path_to_solution;
}
public void Path_Tracer(List<Node> path, Node n)
{
Console.WriteLine("Retracing Path...");
Node current = n; ////////////////////////////////////////////////////// Start from the given node
path.Add(current); ////////////////////////////////////////////////////// Add the current node to the path list
while (current.parent != null)
{
current = current.parent; ////////////////////////////////////////////////////// Move to the parent node
path.Add(current); ////////////////////////////////////////////////////// Add the parent node to the path list
}
path.Reverse();
}
public static bool Contains(List<Node> list, Node c)
{
bool contains = false;
for (int i = 0;i < list.Count;i++)
{
if (list[i].SameP(c.puzzle))
{
contains = true;
}
}
return contains;
}
//////////////////////////code>//////////////////////////pre>
主要://////////////////////////p>
static void Main(string[] args)
{
int[] puzzle =
{
1, 0 ,2,
3, 4, 5,
6, 7 ,8,
};
Node root = new Node(puzzle);
Uninformed_Search ui = new Uninformed_Search();
List<Node> sol = ui.BFS(root);
if(sol.Count > 0)
{
for (int i = 0; i < sol.Count; i++)
{
sol[i].Print_Console();
}
}
else
{
Console.WriteLine("No path found");
}
Console.ReadLine();
}
//////////////////////////code>//////////////////////////pre>
示例输出://////////////////////////p>
沈阳1 0 2//////////////////////////p>
3 4 5//////////////////////////p>
6 7 8....//////////////////////////p>
/////////////////////////////////////////////////////p>
1 2 0//////////////////////////p>
3 4 5//////////////////////////p>
6 7 8....//////////////////////////p>
/////////////////////////////////////////////////////p>
1 4 2//////////////////////////p>
3 0 5//////////////////////////p>
6 7 8....//////////////////////////p>
/////////////////////////////////////////////////////p>
1 2 5//////////////////////////p>
3 4 0//////////////////////////p>
6 7 8....//////////////////////////p>
0 and 1 only need to swap places to reach the goal state but the for some reason its refusing to do so, thus I am suspecting the method to check for repetition(SameP()//////////////////////////code>) might be incorrect. However, I can not think of any solution. Thanks for reading, I hope some one could help me answer this.//////////////////////////p>