# The (eight-)queens problem, modeled naively as a `BacktrackProblem`.
#
# The state (`S`) is a board, modeled as an array of occupied rows.
# The integer in each row indicates the column occupied by the queen.
# Since there can be only one queen by row, a single `Int` is
# enough for each row, and the whole board `rows` is just an `Array[Int]`.
# Only the occupied rows are stored, thus the length of `rows` indicates
# the number of occupied rows, the remaining virtual rows are considered free.
#
# An action (`A`) is the column where to put a queen in the first free row,
# so modeled as an Int.
# Actions are applied until all rows are occupied by a queen.
class QueenProblem
	super BacktrackProblem[Array[Int], Int]

	# The initial state has no queens; so, no occupied rows.
	redef fun initial_state do return new Array[Int]

	# The board size.
	# Hint: use 8 to be traditional.
	var size: Int

	# 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

	# The first free row become occupied with a queen placed where indicated.
	redef fun apply_action(rows, column)
	do
		rows.add column
	end

	# Just `free` the last occupied row.
	redef fun backtrack(rows, column)
	do
		rows.pop
	end

	# Are all rows are occupied?
	redef fun is_goal(rows) do return rows.length >= size

	# Draw a nice board
	fun print_state(rows: Array[Int])
	do
		printn "+"
		for i in [0..size[ do printn "-"
		print "+"
		for r in rows do
			printn "|"
			for i in [0..r[ do printn "."
			printn "Q"
			for i in [r+1..size[ do printn "."
			print  "|"
		end
		for r in [rows.length..size[ do
			printn "|"
			for i in [0..size[ do printn "."
			print  "|"
		end
		printn "+"
		for i in [0..size[ do printn "-"
		print "+"
	end
end