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.

Property definitions

ai $ BacktrackProblem :: actions
	# 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
lib/ai/backtrack.nit:48,2--58,82

ai $ QueenProblem :: actions
	# What are the available columns for a queen in the first free row?
	# Just look at occupied rows above and cancel the possible columns one by one.
	redef fun actions(rows, node)
	do
		# No more than 8 rows
		if rows.length >= size then return null

		# Available columns. At first, all are available.
		var columns = new Array[Bool].filled_with(true, size)

		# Look at each occupied row and cancel columns
		var i = rows.length # delta for each diagonal
		for r in rows do
			columns[r] = false # no queen under `r`
			var d = r - i
			if d >= 0 then columns[d] = false # no queen on the first diagonal
			d = r + i
			if d < size then columns[d] = false # no queen on the second diagonal
			i -= 1
		end

		# Collect the remaining columns, those that were not cancelled.
		var res = new Array[Int]
		for c in [0..size[ do if columns[c] then res.add(c)

		return res
	end
lib/ai/examples/queens.nit:57,2--83,4