Well-known problem is the problem of placing eight shess queens on an 8×8 chessboard so that no two queens attack each other. In this post, we consider the same problem of placing  m  shess queens on an  n×n  chessboard. The problem has a solution if  n>3  and  m<=n .

Work consists of two procedures. The first procedure  Queens  returns the total number of solutions and saves a complete list of all solutions (global variable  S ). The second procedure  QueensPic  shows the user-defined solutions from the list  S  on the board. Formal argument  t  is the number of solutions in each row of the display. The second procedure should be used in the standard interface, rather than in the classic one, since in the latter it may not work properly.

Queens := proc (m::posint, n::posint)

local It, K, l, L, M, P;

global S, p, q;

It := proc (L)

local P, k, i, j;

M := []; k := nops(L[1]);

for i in L do

for j to n do

if convert([seq(j <> i[s, 2], s = 1 .. k)], `and`) and convert([seq(l[k+1]-i[s, 1] <> i[s, 2]-j, s = 1 .. k)], `and`) and convert([seq(l[k+1]-i[s, 1] <> j-i[s, 2], s = 1 .. k)], `and`) then M := [op(M), [op(i), [l[k+1], j]]]

fi;

od; od;

M;

end proc;

K := combinat:-choose([`$`(1 .. n)], m);

S := [];

for l in K do P := [];

L := [seq([[l[1], i]], i = 1 .. n)];

P := [op(P), op((It@@(m-1))(L))];

S := [op(S), op(P)]

od;

p := args[1]; q := args[2];

nops(S);

end proc:

 

QueensPic := proc (M, t::posint)

local m, n, HL, VL, T, A, N;

uses plottools, plots;

m := p; n := q; N := nops(args[1]);

HL := seq(line([.5, .5+k], [.5+n, .5+k], color = black, thickness = 2), k = 0 .. n);

VL := seq(line([.5+k, .5], [.5+k, .5+n], color = black, thickness = 2), k = 0 .. n);

T := [seq(textplot([seq([op(M[i, j]), Q], j = 1 .. m)], color = red, font = [TIMES, ROMAN, 24]), i = 1 .. N)];

if m <= n and 3 < n then

A := seq(display(HL, VL, T[k], axes = none, scaling = constrained), k = 1 .. N), seq(display(plot([[0, 0]]), axes = none, scaling = constrained), k = 1 .. t*ceil(N/t)-N);

Matrix(ceil(N/t), t, [A]);

display(%);

fi;

end proc:

 

Examples of work:

Queens(5, 6);  

S[70], S[140], S[210];

QueensPic([%], 3); 

                                                                            248

[[1, 5], [2, 3], [3, 6], [4, 4], [6, 1]], [[1, 3], [2, 5], [4, 1], [5, 4], [6, 2]], [[2, 1], [3, 4], [4, 2], [5, 5], [6, 3]]

 

Two solutions of classic problem:

Queens(8, 8); 

S[64..65];

QueensPic(%, 2);

                                                                                      92

[[[1, 5], [2, 8], [3, 4], [4, 1], [5, 7], [6, 2], [7, 6], [8, 3]], [[1, 6], [2, 1], [3, 5], [4, 2], [5, 8], [6, 3], [7, 7], [8, 4]]]

 

 

Queens_problem.mw


Please Wait...