/usr/share/yacas/scripts/examples/queens.ys is in yacas 1.3.6-2+b1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | /* Example: queens problem. */
/* Queens(n) : main entry function. This function returns a list of
* results to the n-queens problem. The results will be lists of numbers,
* for instance {2,3,1,4} which is to be interpreted as queens standing
* on (1,2), (2,4), (3,1) and (4,3).
*
* No typechecking is done on the arguments of the internal functions,
* only on Queens(n), since that is the only function that should be
* used by the outside world.
*/
Queens(n_IsPositiveInteger) <--
[
Local(result);
Set(result,{});
Queens(n,{},1 .. n,result); /* build result */
result; /* return result */
];
/* IsOnDiagonal determines if two queens are on a diagonal */
10 # IsOnDiagonal({_x1,_y1},{_x2,_y2})_(MathSubtract(x1,x2) = MathSubtract(y1,y2)) <-- True;
20 # IsOnDiagonal({_x1,_y1},{_x2,_y2})_(MathSubtract(x1,x2) = MathSubtract(y2,y1)) <-- True;
30 # IsOnDiagonal(_n,_m) <-- False;
/* QueenCollides determines if a new queen to be positioned on n collides
* with the queens on positions held in the list
*/
10 # QueenCollides(_n,_list) <--
[
Local(result);
Set(result, False);
While(And(Not(result), Not(Equals(list, {}))))
[
Set(result, IsOnDiagonal(n,Head(list)));
Set(list, Tail(list));
];
result;
];
/* If new queen does not collide with other queens, add to try list,
* and solve the n-1 queens problem
*/
TryAddQueen(_n,_element,_try,_use,_result)_
Not(QueenCollides(element,try)) <--
[
Queens(MathSubtract(n,1),element:try,use,result);
];
/* Recursive solve n-queens problem.*/
/* All queens checked, so add the result. */
10 # Queens( 0,_try,_touse,_result) <-- DestructiveInsert(result,1,try);
20 # Queens(_n,_try,_touse,_result) <--
[
Local(tailuse,i);
Local(nextuse);
Set(tailuse, touse);
Set(i, 1);
While(Not(Equals(tailuse, {})))
[
Set(nextuse,FlatCopy(touse));
DestructiveDelete(nextuse,i);
TryAddQueen(n, {n,Head(tailuse)}, try, nextuse, result );
Set(tailuse,Tail(tailuse));
Set(i, MathAdd(i,1));
];
];
|