hello @
my involvement in minimicro is limited at the moment. the following is the problem of the nQueens with description.
// nQueens (adapted from python to ring to ms)
// datum: 20210610
// ms is almost 2x slower than easyLang
// ---------------------------------------------------------------
// returned TRUE ONLY when not in conflict.
ok = function(k,i)
for j in range(0, k-1)
if x[j] == i or // conflict in same row OR
abs(x[j]-i) == abs(j-k) then // conflict diagonal
return 0
end if
end for
return 1
end function
// ---------------------------------------------------------------
showBoard = function()
// yes.. I don't like this either...
for y in range(0, n)
if x[y] == 0 then
print " Q"+" •"*n
else if x[y] == 1 then
print " •"+" Q"+" •"*(n-1)
else if x[y] == 2 then
print " •"*2+" Q"+" •"*(n-2)
else if x[y] == 3 then
print " •"*3+" Q"+" •"*(n-3)
else if x[y] == 4 then
print " •"*4+" Q"+" •"*(n-4)
else if x[y] == 5 then
print " •"*5+" Q"+" •"*(n-5)
else if x[y] == 6 then
print " •"*6+" Q"+" •"*(n-6)
else if x[y] == 7 then
print " •"*7+" Q"+" •"*(n-7)
// don't try more as 7 (is to slowly)
else if x[y] == 8 then
print " •"*8+" Q"+" •"*(n-8)
else if x[y] == 9 then
print " •"*9+" Q"+" •"*(n-9)
else if x[y] == 10 then
print " •"*10+" Q"+" •"*(n-10)
end if
end for
end function
nQueen = function(k, n) // 0, n+1
for i in range(0, n)
if ok(k,i) then // conflict?
x[k] = i
if k == n then
print
print x
print
showBoard()
else
nQueen(k+1, n) // *** recursive call ***
end if
end if
end for
return
end function
// ---------------------------------------------------------------
print "Value as Column of the Row."
print "(Below pseudographics):"
n=3 // from 0 to 3 = 4
if n>7 or n<3 then
print "Value: max 8 (7) min 4 (3) Queens"
end if
x = [0] *(n+1) // board 4 col
nQueen(0, n) // RUN
print
// ---------------------------------------------------------------
// output for: 4x4
// arr-base: 0
// 1 3 0 2
// . x . .
// . . . x
// x . . .
// . . x .
// 2 0 3 1
// . . x .
// x . . .
// . . . x
// . x . .
description:
nQueens:
Step 1: Start
Step 2: Given n queens, read n from user and let us denote the queen number by k. k=1,2,..,n.
Step 3: We start a loop for checking if the k<sup>th</sup> queen can be placed in the respective column of the k<sup>th</sup> row.
Step 4: For checking that whether the queen can be placed or not, we check if the previous queens are not in diagonal or in same row with it.
Step 5: If the queen cannot be placed backtracking is done to the previous queens until a feasible solution is not found.
Step 6: Repeat the steps 3-5 until all the queens are placed.
Step 7: The column numbers of the queens are stored in an array and printed as a n-tuple solution
Explanation:
For the n queen problem we take input of n, lets say n=4 so, k=1,2,3,4.
For placing the first queen i.e k=1,we start a loop for n columns i.e n=4 so till the fourth column.
The first queen can be placed at first column only.
Then we move for the second queen and place it seeing that the first queen is not in the same column or in diagonal with the second queen.
Similarly, the third queen and the fourth queen are placed. But if the fourth queen cannot be placed as it lies in same column or is in diagonal with other queens then back-tracking is done to the previous queens in order of 3,2,1 to achieve the unique feasible solution.
For an n problem queen the same way all the n queens are placed and if the nth cannot be placed back-tracking is done and the queens are re-ordered and solution is obtained.
