/*..

======================================
Some Solutions to the N Queens Problem
======================================

:Source: http://pure-lang.googlecode.com/svn/trunk/pure/examples/libor/queens.pure
:Author: Libor Spacek (C) <libors@gmail.com\>
:License: GPL V3
:Date: Version 3: August 2009


Example usage:
______________

	#pure -i queens.pure

	>fullboard (thequeen 30); */

/*..

Utilities:
__________
*/
//>>>
nonfix nosolution notimplemented passed failed;
//<<<
/*..

**(diagsafe j l)**

	is square j in the current row safe from the diagonal attacks by 
	all queens in previous rows placed on other columns recorded in list l ? */

// >>>
diagsafe j::int l = rsafe 1 j l
	with
		rsafe _ _ [] = 1;
		rsafe id::int j::int (j2::int:l) = if ((id==j-j2)||(id==j2-j)) then 0 
			else rsafe (succ id) j l
	end;

/* remove one element from an ordered list */
rem _ [] = [];
rem h1::int (h2::int:t) = if h1 == h2 then t else h2:(rem h1 t);

// <<<
/*..

**(fullboard s)**

	full coordinates representation [(row,column),...] is redundant
	because the first coordinate of any solution will always be 1..n. 
	However, it can be reconstructed with, e.g. (fullboard (thequeens n));
	All solutions here are encoded as the columns permutations only, 
	[column, ...], leaving out (the index formed by) the ordered rows.
	In all cases rows and columns are interchangeable, 
	i.e. reading the same numbers as [row, ....] for ordered
	columns is also a valid solution. */
//>>>	
fullboard s = zip (1..(#s)) s;
//<<<
/*..

Solutions:
__________

**(allqueens n)**

	returns all possible solutions by constrained search, e.g.
	(allqueens 8) returns a list of all 92 chessboard solutions. 
	There is no known method to find the number
	of solutions for any n. Experimental solutions exist currently 
	for up to n=26 by using special purpose parallel hardware and 
	running for a long time. Allqueens, which is quite fast,
	is quite breathless for n=15 (number of solutions = 2 279 184). 
	It is unwise to ask for the full list
	to be printed for anything beyond n=10 (724  solutions).
	
	Only half of the first row is considered for the first queen, 
	thus halving the total search effort, 
	followed by adding a reflection of all the solutions found 
	about the middle column. 
	Odd sized boards must have additionally the first midrow starting position
	searched and add its solutions. 
	More reflections and rotations could be done but the solutions 
	would have to be tested for duplicates.
	All rook checking (row and column) is eliminated by using only unused 
	candidates list c, leaving just the bishop check, id==abs(j2-j),  
	(both diagonals).*/
//>>>
allqueens 1 = [[1]];
allqueens n::int = nosolution if n<4;
 = if (n mod 2 == 0) then (hsol+revsol) else hsol+(tryjs rhsn rhsn [hsn])+revsol
	when 
		nl = (1..n); sn::int = succ n; hsn::int = sn div 2; rhsn = rem hsn nl;
		hsol = (tryjs nl (1..(n div 2)) []);
		revsol = map (\y -> map (\z -> sn-z) y) hsol
	end
	with
		tryjs [] _ p = [p]; // solution p
		tryjs _ [] _ = [];  // out of candidate js - no solution here
		tryjs cs (j:ct) p =  res+(tryjs cs ct p)
		when rjs = (rem j cs); res = (tryjs rjs rjs (j:p)) end if (diagsafe j p);
			= (tryjs cs ct p) otherwise;
	end;
//<<<
/*..

**(queen n)**

	this concise depth-first search throws the first found solution */
//>>>
queen 1 = [[1]];
queen n::int = nosolution if n<4;
queen n::int = catch id (srch n n [])
	with srch 0 _ p = throw [p];	// no more rows: solved
		srch _ 0 _ = [];	// out of columns
		srch i::int j::int p = 
			( if (unsafe j p) then void else void (srch (i-1) n (j:p)) )
			$$ void (srch i (j-1) p)
	end;
//<<<
/*..

**(thequeen n)**

	Any two queens placement symmetric under a single reflection around any of 
	the board's four axis of symmetry is not part of a solution by problem 
	definition. It follows that any complete solution cannot be symmetric 
	(invariant) under a single reflection.

	There are so called doubly symmetric solutions, invariant under any 
	combination of 90 degrees rotations, which have an orbit of just two 
	equivalent solutions, produced by a single reflection (e.g. viewing the board
	from top or from underneath). A double symmetric solution has the full square
	symmetry internally but its axis of symmetry do not coincide with those of 
	the board.

	There always exists at least one symmetric solution invariant under 180 
	degrees rotation (or two orthogonal reflections), producing an orbit of four
	equivalent solutions. The symmetric solutions are the ones found by 
	'thequeens' and possibly other regular methods.

	All other solutions are asymmetric and thus can be rotated into four 
	different positions 	and viewed from above or below the board, in each case 
	producing a different (equivalent) solution, the total orbit 
	(of the dihedral group) of eight.

	There are no other solutions.

	'Thequeen' encodes my solution in the following few lines of code. It is to 
	my knowledge the simplest algorithm for the N-Queens problem. It is very fast
	even for large boards, being a regular (linear) solution requiring no search.
	Of course, it does not give all the solutions and thus does not solve the
	hard problem described above for 'allqueens'.

	The correct pattern is simply written down directly without any checking or 
	searching being necessary. It can be easily learnt to do 'by inspection', 
	which is probably a neat party trick to perform. The solutions had been 
	tested exhaustively for board sizes 0 to 5001 and individually for board size
	50000x50000. */
//>>>
thequeen 1 = [[1]];
thequeen n::int = nosolution if n<4;
thequeen n::int
	= [ 1:(map succ (head (thequeen (n-1)))) ] if (n mod 2);// odd sized boards
	= [ map (newsq) (0..(n-1)) ] // the rest is even sized boards solution
	with 
		newsq x::int = (succ ((start+2*x) mod n)) if x < hn;
						 = (succ ((restart+2*(x-hn)) mod n)) end
	when 
		hn::int = (n div 2); // half n
		start::int = if (n mod 3) then (pred hn) else 1; //(n mod 3) special
		restart::int = (1+n-start) end;
//<<<
/*.. 

Testing:
________

**(unsafe j l)**

	is square j in the current row attacked (rook or bishop)
	by any previously placed queen in list l?  */
//>>>
unsafe j::int l = rsafe 1 l
	with
		rsafe _ [] = 0;
		rsafe id::int (j2::int:l) = 
			if ((jd == 0) || ((id-jd) == 0) || ((id+jd) == 0)) then 1 
			else rsafe (succ id) l
			when jd = j2-j end
	end;
//<<<
/*..

**(checkqs l)**

	checks one solution either in 0..n-1 encoding or in 1..n
	encoding. It returns 0 for a correct result and 1 when
	a queen attack exists anywhere within the presented 'solution'. */
//>>>
checkqs [] = 0;
checkqs (s::int:l) = if unsafe s l then 1 else checkqs l;
//<<<
/*..

**(checksols l)**

	checks a list of solutions. It returns 0 iff they are all correct,
	otherwise it returns 1. Correct solutions include 'nosolution' produced
	for sizes 2 and 3;  */
//>>>
checksols [] = 0;
checksols (s:l) = if checkqs s then 1 else checksols l;
checksols nosolution = 0;
//<<<
/*..

**(queenstest method l)**

	conducts exhaustive tests of solutions. Returns either 'passed' or 'failed'.
	Needs name of a method, followed by a list of board sizes. Example usage::
	
	>queenstest allqueens [8];
	>queenstest queen [5,6,7];
	>queenstest thequeen (5000:4999..100); */
//>>>
queenstest _ [] = passed;
queenstest method (h:l) = 
		if (checksols (method h)) then failed else (queenstest method l);
//<<<
