nqueens(N, L) :-
	generate(N, L),
	test(N, L).

generate(N, L) :-
	generate(N, 0, L).

generate(N, N, []).
generate(N, I, [A|K]) :-
	I < N,
	J is I + 1,
	gen_number(N, A),
	generate(N, J, K).

test(N, L) :-
	empty_board(N, B),
	check_list(N, B, L).

check_list(N, B, L) :-
	check_list(N, B, 1, L).

check_list(_, _, _, []).
check_list(N, B, I, [L|Ls]) :-
	require_empty_and_fill(B, I, L, B1),
	fill_board(N, B1, I, L, B2),	
	J is I + 1,
	check_list(N, B2, J, Ls).

require_empty_and_fill(B, X, Y, R) :-
	m_get(B, X, Y, e),
	m_set(B, X, Y, q, R).

fill_board(N, B, X, Y, R) :-
	fill_l(N, B, X, Y, B1),
	fill_r(N, B1, X, Y, B2),
	fill_u(N, B2, X, Y, B3),
	fill_d(N, B3, X, Y, B4),
	fill_lu(N, B4, X, Y, B5),
	fill_ru(N, B5, X, Y, B6),
	fill_ld(N, B6, X, Y, B7),
	fill_rd(N, B7, X, Y, R).

fill_l(N, B, X, Y, R) :-
	(
		X > 1 ->
			NX is X - 1,
			m_set(B, NX, Y, q, B1),
			fill_l(N, B1, NX, Y, R)
	;
			B = R
	).
		
fill_r(N, B, X, Y, R) :-
	(
		X < N ->
			NX is X + 1,
			m_set(B, NX, Y, q, B1),
			fill_r(N, B1, NX, Y, R)
	;
			B = R
	).
		
fill_d(N, B, X, Y, R) :-
	(
		Y > 1 ->
			NY is Y - 1,
			m_set(B, X, NY, q, B1),
			fill_d(N, B1, X, NY, R)
	;
			B = R
	).
		
fill_u(N, B, X, Y, R) :-
	(
		Y < N ->
			NY is Y + 1,
			m_set(B, X, NY, q, B1),
			fill_u(N, B1, X, NY, R)
	;
			B = R
	).
		
fill_ld(N, B, X, Y, R) :-
	(
		(X > 1, Y > 1) ->
			NX is X - 1,
			NY is Y - 1,
			m_set(B, NX, NY, q, B1),
			fill_ld(N, B1, NX, NY, R)
	;
			B = R
	).
		
fill_rd(N, B, X, Y, R) :-
	(
		(X < N, Y > 1) ->
			NX is X + 1,
			NY is Y - 1,
			m_set(B, NX, NY, q, B1),
			fill_rd(N, B1, NX, NY, R)
	;
			B = R
	).
		
fill_lu(N, B, X, Y, R) :-
	(
		(X > 1, Y < N) ->
			NX is X - 1,
			NY is Y + 1,
			m_set(B, NX, NY, q, B1),
			fill_lu(N, B1, NX, NY, R)
	;
			B = R
	).
		
fill_ru(N, B, X, Y, R) :-
	(
		(X < N, Y < N) ->
			NX is X + 1,
			NY is Y + 1,
			m_set(B, NX, NY, q, B1),
			fill_ru(N, B1, NX, NY, R)
	;
			B = R
	).
		

gen_number(N, N).
gen_number(N, A) :-
	M is N-1,
	M > 0,
	gen_number(M, A).

empty_board(N, B) :-
	matrix(N, e, B).

matrix(N, V, M) :-
	matrix(N, 0, V, M).

matrix(N, N, _, []).
matrix(N, I, V, [Vec|M]) :-
	I < N,
	J is I + 1,
	vector(N, V, Vec),
	matrix(N, J, V, M).

vector(0, _, []).
vector(N, V, [V|Vec]) :-
	N > 0,
	M is N - 1,
	vector(M, V, Vec).
	
m_get([V|_], 1, Y, R) :-
	v_get(V, Y, R).
m_get([_|Vs], X, Y, R) :-
	X > 1,
	NX is X - 1,
	m_get(Vs, NX, Y, R).

v_get([X|_], 1, X).
v_get([_|Xs], I, R) :-
	I > 1,
	NI is I - 1,
	v_get(Xs, NI, R).

m_set([V|Vs], 1, Y, Val, [R|Vs]) :-
	v_set(V, Y, Val, R).
m_set([V|Vs], X, Y, Val, [V|R]) :-
	X > 1,
	NX is X - 1,
	m_set(Vs, NX, Y, Val, R).

v_set([_|Xs], 1, V, [V|Xs]).
v_set([X|Xs], I, V, [X|R]) :-
	I > 1,
	NI is I - 1,
	v_set(Xs, NI, V,  R).