# Abstract backtrack problem of states (`S`) and actions (`A`).
#
# This class serves to model search problems using a backtracking approach.
# A state, `S`, is a point in the search problem and fully model a given state of the world.
# An action, `A`, is an available mean of transition between two states.
# While there is a potential large number of distinct states and actions, there should be only
# a small number of possible actions from a specific state (thus, a small, or at least finite, branching factor).
#
# The point this class is that the state is a mutable object, the roles of the actions is to modify
# the state.
#
# This abstract class is generic and made to work with any kind of states and actions.
# Therefore, specific subclasses must be developed to implements the required services:
#
# * `initial_state`
# * `actions`
# * `apply_action`
# * `backtrack`
# * `is_goal`
#
# # Basic search
#
# The method `solve` returns a new solver for a backtrack search.
abstract class BacktrackProblem[S: Object,A]
	# The starting state of the problem.
	# It is this object that will be modified by `apply_action` and `backtrack`.
	fun initial_state: S is abstract

	# The available and applicable actions for a given state
	# Because of `backtracking`, actions must also be reversible (see `backtrack`).
	#
	# If there is no available actions, null (or an empty collection) must be returned.
	#
	# In order to optimise the search time, it is sensible to return `null`
	# (or an empty collection) as early as possible.
	#
	# Node: to help some specific implementations, the current node is also available.
	# See `BacktrackNode` for details.
	fun actions(state: S, node: BacktrackNode[A]): nullable Collection[A] is abstract

	# Modify `state` by applying `action`
	# The `action` comes from an earlier invocation of `actions`.
	fun apply_action(state: S, action: A) is abstract

	# Modify `state` by undoing `action`
	# Because of this method, it is important that any action can be undone
	# knowing only the post-state and the action.
	fun backtrack(state: S, action: A) is abstract

	# Is the state a goal state?
	# Once a goal state is found, the solver is automatically stopped.
	# See `BacktrackSolver.run`.
	fun is_goal(state: S): Bool is abstract

	# Return a new solver
	fun solve: BacktrackSolver[S,A] do
		return new BacktrackSolver[S,A](self, initial_state)
	end
end