How can I find the time taken to find all magic squares with a brute force algor

Question

How can I find the time taken to find all magic squares with a brute force algorithm? in notation.

here is my code if it helps: (written in matlab)

function mm = magic_square(n)
  
p = zeros(n.^2, 1);
m = (n^3+n)/2;
for i=1:(n^2)
p(i) = i;
end
  
p = p';
  
A = perms(p);

for j=1:length(A)
temp = A(j,:);
fail = 0;
for r=0:(n-1)
%row sum
rowsum = sum(temp((r*n+1):(r+1)*n));
%column sum
colsum = sum(temp((r+1):n:(length(temp))));
%left diagonal sum
ldgsum = sum(temp(1:(n+1):(length(temp))));
%right diagonal sum
rdgsum = sum(temp(n:(n-1):(length(temp)-n+1)));
  
if (rowsum ~= m || colsum ~= m || ldgsum ~= m || rdgsum ~= m)

fail = 1;
  
end
end
if ~fail
  
msquare = zeros(n, n);
for z=1:n
for c =1:n
msquare(z,c) = temp((z-1)*n + c);
end
end
msquare
end
end

also I was wondering if the TSP problem would be similar in time taken to solve. I imagine they would but here is that code as well:

clear
clc

%variable parameters:
N = 9; %N = number of cities

%don't edit below this point%

%generate random number
rng shuffle;

%choose random city names from list:
city_names = {'colorado_springs', 'fort_collins', 'south park', 'denver', 'loveland', 'sterling', 'aurora', 'centennial', 'grand_junction', 'lone tree', 'falcon', 'trinidad', 'monument'};
MAX_N = length(city_names);
if N > MAX_N
N = MAX_N
end

cities = {};
pos = [];

for i=1:N
t_c_n = randi(length(city_names));
cities = [cities; city_names(t_c_n)];
city_names(t_c_n) = []; %remove city from list
  
pos = [pos; randi(500), randi(500)];

end

cities = table(cities,pos,'VariableNames',{'city','pos'})
tic
p = perms(cities.city);

figure
cpos = cities.pos';
for i=1:length(cpos)
plot(cpos(1,i),cpos(2,i), '*b')
hold on
end

%calculate distances

dists = zeros(1,length(p));
%positions = [];
min = -1;

min_route = [];
for i=1:length(p)
sub = p(i,1:end); %get single permutation
sub = [sub sub(1)]; %duplicates first city to include in route.
  
%compares the the length of all the permuations
subpos = [];
for x=1:length(sub)-1
i1 = find(strcmp(cities.city,sub(x) ));
i2 = find(strcmp(cities.city,sub(x+1) ));

%fist city pos
x1 = cities.pos(i1,1);
y1 = cities.pos(i1,2);
  
%second city post
x2 = cities.pos(i2,1);
y2 = cities.pos(i2,2);
  
%distance between
dists(i) = dists(i) + sqrt( (x2 - x1)^2 + (y2 - y1)^2 );
subpos = [subpos; x1, y1];
end
subpos = [subpos; x2, y2]; %get final post
%subpos = [subpos; subpos(1,1) subpos(1,2)]; %duplicate first pos. to loop back
  
%positions = [positions; subpos]
subpos = subpos';

%-1 is first case
if min == -1
min = dists(i);
min_route = subpos;
elseif dists(i) <= min
min = dists(i);
min_route = subpos;
end
  
  
%~~~~~~~~~~~~~% test code~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~%
% tests and plots each of the cities and plots them all at once %
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~%

% positions(i) = subpos;
%plot the route:
% for j=1:length(subpos)-1
%
% x1 = subpos(1,j);
% y1 = subpos(2,j);
% x2 = subpos(1,j+1);
% y2 = subpos(2,j+1);
% plot(x1,y1, '*r')
% plot(x2,y2, '*g')
% plot( [x1, x2], [y1, y2], '-BLACK')
% %line( [x1,x2], [y1,y2)
% end
%plot(subpos')

end

%pause so it doesn't instantly plot, too fast for the human eye
toc
pause(2);
%positions = positions' %flip so that it plots nicely
%plot(positions)

for j=1:length(min_route)-1

x1 = min_route(1,j);
y1 = min_route(2,j);
x2 = min_route(1,j+1);
y2 = min_route(2,j+1);
plot(x1,y1, '*r')
plot(x2,y2, '*g')
plot( [x1, x2], [y1, y2], '-GREEN')
pause(1);
end

Explanation / Answer

THE TIME COMPLEXITY ALGORITHM:

A magic square of order n is an arrangement of numbers 1 to n 2 in a table square so that the sum of each row and each column and the two diagonals principal is the same.

O(n2) Quadratic Time
An algorithm is said to run in quadratic time if its running time is proportional to the square of the input size.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.