Companion

object Companion

Companion object containing constants and methods related to solving an 8-puzzle.

Properties

childPositions

private val childPositions: ArrayList<ArrayList<Int>>

Stores the positions adjacent to each position in the puzzle grid.

FRONTIER_INITIAL_CAPACITY

private const val FRONTIER_INITIAL_CAPACITY: Int = 11

Initial capacity of the priority queue storing the frontier nodes.

MAX_NUM_CHILDREN

private const val MAX_NUM_CHILDREN: Int = 4

Maximum number of children of a node, that is, the maximum number of states than can be reached from a given state after exactly a single move.

Functions

backtrackPath

private fun backtrackPath(node: Node): Stack<StatePair>

Traces the path from the specified node back to the start node.

getChildNodes

private fun getChildNodes(node: Node, blankTilePos: Int, numColumns: Int, blankTileMarker: Int): ArrayList<Node>

Gets the child nodes of the given node.

getChildPositions

private fun getChildPositions(): ArrayList<ArrayList<Int>>

Gets the positions adjacent to each position in the puzzle grid.

isSolved

fun isSolved(puzzleState: ArrayList<Int>, goalPuzzleState: ArrayList<Int>): Boolean

Checks if the current puzzle state is equal to the goal state.

solve

fun solve(puzzleStatePair: StatePair, goalPuzzleState: ArrayList<Int>, numColumns: Int, blankTileMarker: Int): Stack<StatePair>?

Returns the sequence of states from the current puzzle state to the goal state, as determined using the A* search algorithm with Manhattan distance as the heuristic.