Kitonum

14034 Reputation

24 Badges

11 years, 195 days

MaplePrimes Activity


These are Posts that have been published by Kitonum

knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. This problem mentioned in  page of tasks still without  Maple implementation. 

The post presents the implementation of this task in Maple. Required parameter of the procedure (named  KnightTour)  is  address  - the address of the initial square in the algebraic notation. The second parameter  opt  is optional parameter:

1) if  opt is sequence  (by default) then  the procedure returns the sequence of moves of the knight in the usual algebraic notation,

2)  if  opt is diagram   then  the procedure returns the plot of moves of the knight and  sequentially numbers all the visited squares,

3) if  opt is animation  then  the procedure returns an animation of moves of the knight.

In the procedure is used a solution with maximum symmetry by George Jelliss, http://www.mayhematics.com/t/8f.htm

 

Code of the procedure:

KnightTour := proc(address::symbol, opt::symbol := sequence)

local L, n, L1, k, i, j, squares, border, chessboard, letters, digits, L2, L3, Tour, T, F;

uses ListTools, plottools, plots;

L := [a1, b3, d2, c4, a5, b7, d8, e6, d4, b5, c7, a8, b6, c8, a7, c6, b8, a6, b4, d5, e3, d1, b2, a4, c5, d7, f8, h7, f6, g8, h6, f7, h8, g6, e7, f5, h4, g2, e1, d3, e5, g4, f2, h1, g3, f1, h2, f3, g1, h3, g5, e4, d6, e8, g7, h5, f4, e2, c1, a2, c3, b1, a3, c2];

n := Search(address, L);

L1 := [L[n .. 64][], L[1 .. n-1][]];

if opt = sequence then return L1[] fi;

k := 0;

for i to 8 do

for j from `if`(type(i, odd), 1, 2) by 2 to 8 do

k := k+1;

squares[k] := polygon([[i-1/2, j-1/2], [i-1/2, j+1/2], [i+1/2, j+1/2], [i+1/2, j-1/2]], color = grey);

od;  od;

squares := convert(squares, list);

border := curve([[1/2, 1/2], [1/2, 17/2], [17/2, 17/2], [17/2, 1/2], [1/2, 1/2]], color = black, thickness = 4);

chessboard := display(squares, border);

letters := [a, b, c, d, e, f, g, h];

digits := [$ 1 .. 8];

L2 := convert~(L1, string);

L3 := subs(letters=~digits, map(t->[parse(t[1]), parse(t[2])], L2));

Tour := curve(L3, color = red, thickness = 3);

T := textplot([seq([op(L3[i]), i], i = 1 .. 64)], align = above, font = [times, bold, 16]);

if opt = diagram then return display(chessboard, Tour, T, axes = none) fi;

F := seq(display(chessboard, curve(L3[1 .. s], color = red, thickness = 3), textplot([seq([op(L3[i]), i], i = 1 .. s)], align = above, font = [times, bold, 16])), s = 1 .. 64);

display(seq(F[i]$5, i = 1 .. 64), insequence = true, axes = none);

end proc:

 

 Examples of use:

KnightTour(f3);

KnightTour(f3, diagram);

 

 

KnightTour(f3, animation);

                                 

 

 

 KnightTour.mw

@Markiyan Hirnyk   I try not to use this package, as I think the results are not reliable enough. Here is the example, where instead of the three real roots it finds only one, despite the hint to look for the three roots:

restart;

DirectSearch:-SolveEquations(100^x=x^100, AllSolutions, solutions=3);

 

There are many other examples, particularly in discrete optimization in which it returns false results. Here is one example (well-known to you).

This post is related to the this thread

The recursive procedure  PosIntSolve  finds the number of non-negative or positive solutions of any linear Diophantine equation

a1*x1+a2*x2+ ... +aN*xN = n  with positive coefficients a1, a2, ... aN .  

Formal parameters: L is the list of coefficients of the left part, n  is the right part,  s (optional) is nonneg (by default) for nonnegint solutions and  pos  for positive solutions.

The basic ideas:

1) If you make shifts of the all unknowns by the formulas  x1'=x1-1,  x2'=x2-1, ... , xN'=xN-1  then  the number of positive solutions of the first equation equals the number of non-negative solutions of the second equation.

2) The recurrence formula (penultimate line of the procedure) can easily be proved by induction.

 

The code of the procedure:

restart;

PosIntSolve:=proc(L::list(posint), n::nonnegint, s::symbol:=nonneg)

local N, n0;

option remember;

if s=pos then n0:=n-`+`(op(L)) else n0:=n fi;

N:=nops(L);

if N=1 then if irem(n0,L[1])=0 then return 1 else return 0 fi; fi;

add(PosIntSolve(subsop(1=NULL,L),n0-k*L[1]), k=0..floor(n0/L[1]));

end proc:

 

Examples of use.

 

Finding of the all positive solutions of equation 30*a+75*b+110*c+85*d+255*e+160*f+15*g+12*h+120*i=8000:

st:=time():

PosIntSolve([30,75,110,85,255,160,15,12,120], 8000, pos);

time()-st;

                                       13971409380

                                             2.125

 

To test the procedure, solve (separately for non-negative and positive solutions) the simple equation  2*x1+7*x2+3*x3=2000  in two ways (by the  procedure and brute force method):

ts:=time():

PosIntSolve([2,7,3], 2000);

PosIntSolve([2,7,3], 2000, pos);

time()-ts;

                47905

                47334

                 0.281

 

ts:=time():

k:=0:

for x from 0 to 2000/2 do

for y from 0 to floor((2000-2*x)/7) do

for z from 0 to floor((2000-2*x-7*y)/3) do

if 2*x+7*y+3*z=2000 then k:=k+1 fi;

od: od: od:

k; 

k:=0:

for x from 1 to 2000/2 do

for y from 1 to floor((2000-2*x)/7) do

for z from 1 to floor((2000-2*x-7*y)/3) do

if 2*x+7*y+3*z=2000 then k:=k+1 fi;

od: od: od:

k;

time()-ts; 

                   47905

                   47334

                   50.063

 

Another example - the solution of the famous problem: how many ways can be exchanged $ 1 using the coins of smaller denomination.

PosIntSolve([1,5,10,25,50],100);

                        292

 

 Number-of-solutions.mw

 

 Edit.  The code has been slightly edited 

This post is related to the question. There were  proposed two ways of finding the volume of the cutted part of a sphere in the form of a wedge.  Here the procedure is presented that shows the rest of the sphere. Parameters procedure: R - radius of the sphere, H1 - the distance the first cutting plane to the plane  xOy,  H2 -  the distance the second cutting plane to the plane  zOy. Necessary conditions:  R>0,  H1>=0,  H2>=0,  H1^2+H2^2<R^2 . For clarity, different surfaces are painted in different colors.

restart;

Pic := proc (R::positive, H1::nonnegative, H2::nonnegative)

local A, B, C, E, F;

if R^2 <= H1^2+H2^2 then error "Should be H1^(2)+H2^(2)<R^(2)" end if;

A := plot3d([R*sin(theta)*cos(phi), R*sin(theta)*sin(phi), R*cos(theta)], phi = arctan(sqrt(-H1^2-H2^2+R^2), H2) .. 2*Pi-arctan(sqrt(-H1^2-H2^2+R^2), H2), theta = 0 .. Pi, color = green);

B := plot3d([R*sin(theta)*cos(phi), R*sin(theta)*sin(phi), R*cos(theta)], phi = -arctan(sqrt(-H1^2-H2^2+R^2), H2) .. arctan(sqrt(-H1^2-H2^2+R^2), H2), theta = 0 .. arccos(sqrt(R^2-H2^2-H2^2*tan(phi)^2)/R), color = green);

C := plot3d([R*sin(theta)*cos(phi), R*sin(theta)*sin(phi), R*cos(theta)], phi = -arctan(sqrt(-H1^2-H2^2+R^2), H2) .. arctan(sqrt(-H1^2-H2^2+R^2), H2), theta = arccos(H1/R) .. Pi, color = green);

E := plot3d([r*cos(phi), r*sin(phi), H1], phi = -arccos(H2/sqrt(R^2-H1^2)) .. arccos(H2/sqrt(R^2-H1^2)), r = H2/cos(phi) .. sqrt(R^2-H1^2), color = blue);

F := plot3d([H2, r*cos(phi), r*sin(phi)], phi = arccos(sqrt(-H1^2-H2^2+R^2)/sqrt(R^2-H2^2)) .. Pi-arccos(sqrt(-H1^2-H2^2+R^2)/sqrt(R^2-H2^2)), r = H1/sin(phi) .. sqrt(R^2-H2^2), color = gold);

plots[display](A, B, C, E, F, axes = none, view = [-1.5 .. 1.5, -1.5 .. 1.5, -1.5 .. 1.5], scaling = constrained, lightmodel = light4, orientation = [60, 80]);

end proc:

 

Example of use:

Pic(1,  0.5,  0.3);

                             

 

 

The work contains two procedures called  SetPartition  and  NumbPart .

The first procedure  SetPartition  generates all the partitions of a set  S  into disjoint subsets of specific sizes defined by a list  Q. The third optional parameter is the symbol  `ordered`  or  `nonordered`  (by default) . It determines whether the order of subsets in a partition is significant.

The second procedure  NumbPart  returns the number of all partitions of the sizes indicated by  Q .

 

Codes of these procedures:

SetPartition:=proc(S::set, Q::list(posint), K::symbol:=nonordered)  # Procedure finds all partitions of the set  S  into subsets of the specific size given Q.

local L, P, T, S1, S2, n, i, j, m, k, M;

uses ListTools,combinat;

if `+`(op(Q))<>nops(S) then error "Should be `+`(op(Q))=nops(S)" fi;

L:=convert(Q,set);

T:=[seq([L[i],Occurrences(L[i],Q)], i=1..nops(L))];

P:=`if`(K=ordered,convert(T,list),convert(T,set));

S1:=S;  S2:={`if`(K=ordered,[],{})}; n:=nops(P);

for i to n do

m:=P[i,1]; k:=P[i,2];

for j to k do

S2:={seq(seq(`if`(K=ordered,[op(s),t],{op(s),t}), t=choose(S1 minus `union`(op(s)),m)), s=S2)};

od; od;

if K=ordered then {map(op@permute,S2)[]} else S2 fi;

end proc:

 

NumbPart:=proc(Q::list(posint), K::symbol:=nonordered)  # Procedure finds the number of all partitions of a set into subsets of the specific size given  Q

local L, T, P, n, S, N;

uses ListTools;

L:=convert(Q,set);

T:=[seq([L[i],Occurrences(L[i],Q)], i=1..nops(L))];

P:=`if`(K=ordered,convert(T,list),convert(T,set));

n:=nops(P);  N:=add(P[i,2], i=1..n);

S:=add(P[i,1]*P[i,2],i=1..n)!/mul(P[i,1]!^P[i,2],i=1..n)/mul(P[i,2]!,i=1..n);

if K=nonordered then return S else  S*N! fi;

end proc:

 

Examples of use:

SetPartition({a,b,c,d,e}, [1,1,3]);  nops(%);  # Nonordered partitions and their number

SetPartition({a,b,c,d,e}, [1,1,3], ordered);  nops(%);  # Ordered partitions and their number

 

 

Here's a more interesting example. 5 fruits  {apple, pear, orange, mango, peach}  must be put on three plates so that  on each of two plates there are 2  fruits, and there is one fruit  on one plate. Two variants to solve: 1) plates are indistinguishable and 2) different plates. In how many ways can this be done?

SetPartition({apple,pear,orange,mango,peach}, [1,2,2]);  nops(%);  # plates are indistinguishable

 

NumbPart([1,2,2], ordered);  # Number of ways for  different plates

                                                              90

 

Another example - how many ways can be divided  100 objects into 10 equal parts?

NumbPart([10$10]);

    64954656894649578274066349293466217242333450230560675312538868633528911487364888307200

 

 SetPartition.mws

3 4 5 6 7 8 9 Page 5 of 10