Class PuzzleState

java.lang.Object

topics.branchandbound.utils.Node

topics.branchandbound.eightpuzzle.PuzzleState

All Implemented Interfaces:

Comparable<Node>

class PuzzleState
extends Node

Represents a distinct physical configuration of the board within the execution tree. It calculates heuristic bounds and generates topologically valid child states.

*

Complexity

• Time Complexity: O(bd) - Where b is the branching factor (average 3 valid moves) and d is the depth of the optimal solution. The heuristic severely prunes unpromising branches.
• Space Complexity: O(b × d) - Dictated by the nodes residing in the priority queue waiting to be evaluated.

Field Summary

Fields inherited from class Node

depth, heuristicValue, id, parentId

Constructor Summary

Constructors

Constructor	Description
PuzzleState(int[] board, HeuristicType heuristicType, int depth, UUID parentID)	Constructs a child node representing a subsequent move.
PuzzleState(HeuristicType heuristicType, int[] board)	Constructs the root node of the state space tree.

Method Summary

Modifier and Type	Method	Description
void	calculateHeuristicValue()	Computes the lower-bound heuristic value.
ArrayList<Node>	expand()	Generates all mathematically and physically valid child states.
boolean	isSolution()	Determines whether the current node represents a fully resolved configuration satisfying all problem constraints.
String	toString()

Methods inherited from class Node

compareTo, equals, getDepth, getHeuristicValue, getId, getParentId, hashCode, initialValuePruneLimit

Methods inherited from class Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Details

PuzzleState

public PuzzleState(HeuristicType heuristicType,
 int[] board)

Constructs the root node of the state space tree.

Parameters:

heuristicType - The heuristic function applied to evaluate paths.

board - The initial state of the puzzle.

PuzzleState

public PuzzleState(int[] board,
 HeuristicType heuristicType,
 int depth,
 UUID parentID)

Constructs a child node representing a subsequent move.

Parameters:

board - The state of the board after the move.

heuristicType - The heuristic function to evaluate the state.

depth - The current depth level in the execution tree.

parentID - The unique identifier of the preceding state.

Method Details

expand

public ArrayList<Node> expand()

Generates all mathematically and physically valid child states.

Specified by:

expand in class Node

Returns:

A list of valid subsequent board configurations.

calculateHeuristicValue

public void calculateHeuristicValue()

Computes the lower-bound heuristic value. Applies mathematical pruning by evaluating inversion parity to instantly discard unsolvable configurations.

Specified by:

calculateHeuristicValue in class Node

isSolution

public boolean isSolution()

Description copied from class: Node

Determines whether the current node represents a fully resolved configuration satisfying all problem constraints.

Specified by:

isSolution in class Node

Returns:

true if the state is a complete mathematical solution; false otherwise.

toString

public String toString()

Overrides:

toString in class Object