>
|
nQueens := module()
local completeBoardAndCheck,
search,
continuation,
subInit;
export checkBoard,
ModuleApply;
checkBoard := proc( n, board::Array )
local i, j, index;
for i from 1 to n-1
do
index := board[i]+1;
for j from i+1 to n while index <= n
do
if ( index = board[j] ) then
return false;
end;
index := index + 1;
end do;
index := board[i] - 1;
for j from i+1 to n while index >= 0
do
if ( index = board[j] ) then
return false;
end;
index := index - 1;
end do;
end do;
return true;
end proc;
completeBoardAndCheck := proc( n, board, i, unused )
local j;
if ( i < n ) then
return andmap( proc( j )
board[i] := j;
completeBoardAndCheck( n, board, i+1,
unused minus {j} )
end proc, unused );
else
board[n] := unused[1];
if ( checkBoard( n, board ) ) then
Threads:-Task:-Return( convert( board, 'list' ) );
return false
end;
end if;
return true;
end proc;
search := proc( i::posint, n::posint, m::nonnegint, board::Array )
local j, k, boards, a, used, unused;
if ( i <= m ) then
if ( i > 1 ) then
used := convert( board[1..i-1], set );
boards := [ seq( Array( board ), k=1..n-i+1 ) ];
k := 1;
for j from 1 to n
do
if ( not j in used ) then
boards[k][i] := j;
k := k+1;
end if;
end do;
else
boards := [ seq( Array( board ), k=1..n ) ];
for j from 1 to n
do
boards[j][i] := j;
end do;
end if;
Threads:-Task:-Continue( passed,
Tasks = [ search, seq( [i+1, n, m, j], j in boards ) ] );
else
unused := { seq( j, j=1..n ) } minus convert( board[1..i-1], set );
return completeBoardAndCheck( n, board, i, unused );
end if;
return NULL;
end proc;
ModuleApply := proc( n::posint, m::nonnegint )
local board;
board := Array( 1..n, datatype=integer[8] );
Threads:-Task:-Start( search, 1, n, m, board );
end proc;
end:
|