ai :: BacktrackProblem :: defaultinit
# 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
lib/ai/backtrack.nit:20,1--78,3