#
# file:    queens.gap
# purpose: find all solutuons of "N-queens problem" with a brute force method
# 


#N := 4;

nqueen := function (N)
	local p, list, lmp, i, j, is_solution, solutions;
	solutions := [];
	for p in SymmetricGroup(N) do
		list := ListPerm (p);
		lmp := LargestMovedPoint (p);
		# complete list beyond the LargestMovedPoint of a permutation
		for i in [lmp+1 .. N] do
			list[i] := i;
		od;
	
		is_solution := true;  # whether given permutation is a solution or not
		# for every permutation in S(N), check whether it provides a solution for N-queens
		for i in [1..N] do
			if not is_solution then
				break;
			fi;
			for j in [1..i-1] do
				if AbsInt(list[i] - list[j]) = i - j then
					is_solution := false;
					break;
				fi;
			od;
		od;

		if is_solution then
			#Print (p, "\n");
			Add (solutions, p);
		fi;
	od;
	return (solutions);
end;


# prints all permutations group elements as permutation matrices
print_group := function (G, N)
	local e;
	for e in G do
		PrintArray (PermutationMat (e, N));
		Print ("\n");
	od;
end;


# print matrix representations of a group generated by solutions of n-queens,
# not coinciding with solutions themselves
pup := function (N)
	local list, n, in_list;
	list := nqueen (N);
	n := Size(list);
	for e in Group(list) do
		in_list := false;
		for i in [1..n] do
			if e = list[i] then
				in_list := true;	
				break;
			fi;
		od;
		if not in_list then
			PrintArray (PermutationMat (e, N));
			Print ("\n");
		fi;
	od;
end;


# end of queens.gap