N-queen puzzle - Revision history

Thomas Linder Puls: N-queen problem moved to N-queen puzzle

2008-11-09T11:28:36Z

← Older revision	Revision as of 13:28, 9 November 2008
(No difference)

Thomas Linder Puls: wikipedia link

2008-11-09T11:28:22Z

wikipedia link

← Older revision		Revision as of 13:28, 9 November 2008
Line 90:		Line 90:
	end implement main</vip>		end implement main</vip>

			=== See also ===

			[[wikipedia:Eight queens puzzle]]

	[[Category:Examples]]		[[Category:Examples]]

Thomas Linder Puls: wrong word tower

2008-11-09T11:16:00Z

wrong word tower

← Older revision		Revision as of 13:16, 9 November 2008
Line 10:		Line 10:
	* So to place N queens on an N x N board there must be exactly one queen in each row.		* So to place N queens on an N x N board there must be exactly one queen in each row.

	So in each row there is exactly one ~~tower~~ which is placed in some column. So we can represent ways to place queens in rows by listing which column that carries a queen for each row.		So in each row there is exactly one queen which is placed in some column. So we can represent ways to place queens in rows by listing which column that carries a queen for each row.

	{{Example\| <vp>[3,3,2]</vp> represents a board where:		{{Example\| <vp>[3,3,2]</vp> represents a board where:
Line 18:		Line 18:
	}}		}}

	* Since a ~~tower~~ can hit vertically, there can at most be one ~~tower~~ in each column.		* Since a queen can hit vertically, there can at most be one queen in each column.
	* So to place N ~~towers~~ on an N x N board there must be exactly one ~~tower~~ in each column.		* So to place N queens on an N x N board there must be exactly one queen in each column.

	So the list representing the position must contain the numbers from 1 to N, each occurring exactly once.		So the list representing the position must contain the numbers from 1 to N, each occurring exactly once.

Thomas Linder Puls: wiki formatting

2008-11-09T11:14:39Z

wiki formatting

← Older revision		Revision as of 13:14, 9 November 2008
Line 7:		Line 7:
	'''Pre-analysis'''		'''Pre-analysis'''

	[*]Since a queen can hit horizontally there can at most be one queen in each row.		* Since a queen can hit horizontally there can at most be one queen in each row.
	[*]So to place N queens on an N x N board there must be exactly one queen in each row.		* So to place N queens on an N x N board there must be exactly one queen in each row.

	So in each row there is exactly one tower which is placed in some column. So we can represent ways to place queens in rows by listing which column that carries a queen for each row.		So in each row there is exactly one tower which is placed in some column. So we can represent ways to place queens in rows by listing which column that carries a queen for each row.
Line 18:		Line 18:
	}}		}}

	[*]Since a tower can hit vertically, there can at most be one tower in each column.		* Since a tower can hit vertically, there can at most be one tower in each column.
	[*]So to place N towers on an N x N board there must be exactly one tower in each column.		* So to place N towers on an N x N board there must be exactly one tower in each column.

	So the list representing the position must contain the numbers from 1 to N, each occurring exactly once.		So the list representing the position must contain the numbers from 1 to N, each occurring exactly once.

Thomas Linder Puls: Category

2008-11-09T11:13:50Z

Thomas Linder Puls: Initial

2008-11-06T17:08:38Z

Initial

New page

The N-queen problem: Place N chess queens on an N x N chess board, such that none of the queens can hit each other.

The N-queen problem is a classical Prolog problem, often used to illustrate a generate and test solution strategy.

The solution here is equally classical: It relies on some pre-analysis of the problem and handy representation.

'''Pre-analysis'''

[*]Since a queen can hit horizontally there can at most be one queen in each row.
[*]So to place N queens on an N x N board there must be exactly one queen in each row.

So in each row there is exactly one tower which is placed in some column. So we can represent ways to place queens in rows by listing which column that carries a queen for each row.

{{Example| <vp>[3,3,2]</vp> represents a board where:
* the first row has a queen in column 3
* the second row has a queen in column 3
* the third row has a queen in column 2
}}

[*]Since a tower can hit vertically, there can at most be one tower in each column.
[*]So to place N towers on an N x N board there must be exactly one tower in each column.

So the list representing the position must contain the numbers from 1 to N, each occurring exactly once.

Hence the possible solutions are permutations of the list <vp>[1,2,...,N]</vp>.

'''Generate and Test'''

The generate and test method will generate all permutations of the list <vp>[1,2,...,N]</vp> and test which ones that are solutions.

We use a list comprehension to build the list <vp>[1,2,...,N]</vp>.

We create all permutations of a list by inserting the fist element at all places in all permutations of the rest of the list.

Given the pre-analysis above we have dealth with the horizontal and vertical hitting, so to test whether something is a solution we only need to consider diagonal hits. Queens can hit diagonally if the vertical distance is the same as the horizontal distance. First we test whether the first queen can hit any other the other queens, then we test whether some of the remaining queens can hit each other (using same starategy).

<vip>implement main
clauses
run() :-
console::init(),
nqueen(7).

class facts
count : integer := 0.

class predicates
nqueen : (integer N).
clauses
nqueen(N) :-
count := 0,
InitBoard = [ I || I = std::fromTo(1, N) ],
foreach B = permute_nd(InitBoard) do
if isSolution(B) then
stdio::writef("Solution: %\n", B),
count := count+1
end if
end foreach,
stdio::writef("Found % solutions to the %-queen problem", count, N).

class predicates
permute_nd : (A*) -> A* nondeterm.
clauses
permute_nd([]) = [].
permute_nd([H|T]) = insert_nd(H, permute_nd(T)).

class predicates
insert_nd : (A, A*) -> A* multi.
clauses
insert_nd(X, L) = [X|L].
insert_nd(X, [Y|L]) = [Y|insert_nd(X,L)].

class predicates
isSolution : (integer* Board) determ.
clauses
isSolution([]).
isSolution([Q|QL]) :-
cannotHit(Q, 1, QL),
isSolution(QL).

class predicates
cannotHit : (integer Q, integer DistX, integer* QL) determ.
clauses
cannotHit(_Q, _Dist, []).
cannotHit(Q, DistX, [QDistX|QL]) :-
DistY = math::abs(Q-QDistX),
DistX <> DistY,
cannotHit(Q, DistX+1, QL).

end implement main</vip>

← Older revision		Revision as of 13:13, 9 November 2008
Line 89:		Line 89:

	end implement main</vip>		end implement main</vip>


			[[Category:Examples]]