Magic squares of singly even order: Difference between revisions
Content added Content deleted
(Added Elixir) |
m (no longer draft) |
||
| Line 1: | Line 1: | ||
{{ |
{{task}} |
||
A [[wp:Magic_square|magic square]] of singly even order has a size that is a multiple of 4, plus 2 (e.g. 6, 10, 14). This means that the subsquares have an odd size, which plays a role in the construction. |
A [[wp:Magic_square|magic square]] of singly even order has a size that is a multiple of 4, plus 2 (e.g. 6, 10, 14). This means that the subsquares have an odd size, which plays a role in the construction. |
||
Revision as of 19:47, 29 May 2016
You are encouraged to solve this task according to the task description, using any language you may know.
A magic square of singly even order has a size that is a multiple of 4, plus 2 (e.g. 6, 10, 14). This means that the subsquares have an odd size, which plays a role in the construction.
The task: create a magic square of 6 x 6.
- Cf.
- See also
C++
<lang cpp>
- include <iostream>
- include <sstream>
- include <iomanip>
using namespace std;
class magicSqr { public:
magicSqr() { sqr = 0; }
~magicSqr() { if( sqr ) delete [] sqr; }
void create( int d ) {
if( sqr ) delete [] sqr;
if( d & 1 ) d++;
while( d % 4 == 0 ) { d += 2; }
sz = d;
sqr = new int[sz * sz];
memset( sqr, 0, sz * sz * sizeof( int ) );
fillSqr();
}
void display() {
cout << "Singly Even Magic Square: " << sz << " x " << sz << "\n";
cout << "It's Magic Sum is: " << magicNumber() << "\n\n";
ostringstream cvr; cvr << sz * sz;
int l = cvr.str().size();
for( int y = 0; y < sz; y++ ) {
int yy = y * sz;
for( int x = 0; x < sz; x++ ) {
cout << setw( l + 2 ) << sqr[yy + x];
}
cout << "\n";
}
cout << "\n\n";
}
private:
void siamese( int from, int to ) {
int oneSide = to - from, curCol = oneSide / 2, curRow = 0, count = oneSide * oneSide, s = 1;
while( count > 0 ) {
bool done = false;
while ( false == done ) {
if( curCol >= oneSide ) curCol = 0;
if( curRow < 0 ) curRow = oneSide - 1;
done = true;
if( sqr[curCol + sz * curRow] != 0 ) {
curCol -= 1; curRow += 2;
if( curCol < 0 ) curCol = oneSide - 1;
if( curRow >= oneSide ) curRow -= oneSide;
done = false;
}
}
sqr[curCol + sz * curRow] = s;
s++; count--; curCol++; curRow--;
}
}
void fillSqr() {
int n = sz / 2, ns = n * sz, size = sz * sz, add1 = size / 2, add3 = size / 4, add2 = 3 * add3;
siamese( 0, n );
for( int r = 0; r < n; r++ ) {
int row = r * sz;
for( int c = n; c < sz; c++ ) {
int m = sqr[c - n + row];
sqr[c + row] = m + add1;
sqr[c + row + ns] = m + add3;
sqr[c - n + row + ns] = m + add2;
}
}
int lc = ( sz - 2 ) / 4, co = sz - ( lc - 1 );
for( int r = 0; r < n; r++ ) {
int row = r * sz;
for( int c = co; c < sz; c++ ) {
sqr[c + row] -= add3;
sqr[c + row + ns] += add3;
}
}
for( int r = 0; r < n; r++ ) {
int row = r * sz;
for( int c = 0; c < lc; c++ ) {
int cc = c;
if( r == lc ) cc++;
sqr[cc + row] += add2;
sqr[cc + row + ns] -= add2;
}
}
}
int magicNumber() { return sz * ( ( sz * sz ) + 1 ) / 2; }
void inc( int& a ) { if( ++a == sz ) a = 0; }
void dec( int& a ) { if( --a < 0 ) a = sz - 1; }
bool checkPos( int x, int y ) { return( isInside( x ) && isInside( y ) && !sqr[sz * y + x] ); }
bool isInside( int s ) { return ( s < sz && s > -1 ); }
int* sqr;
int sz;
}; int main( int argc, char* argv[] ) {
magicSqr s; s.create( 6 ); s.display(); return 0;
} </lang>
- Output:
Singly Even Magic Square: 6 x 6 It's Magic Sum is: 111 35 1 6 26 19 24 3 32 7 21 23 25 31 9 2 22 27 20 8 28 33 17 10 15 30 5 34 12 14 16 4 36 29 13 18 11
Elixir
wp:Conway's LUX method for magic squares: <lang elixir>defmodule Magic_square do
@lux %{ L: [4, 1, 2, 3], U: [1, 4, 2, 3], X: [1, 4, 3, 2] }
def singly_even(n) when rem(n-2,4)!=0, do: raise ArgumentError, "must be even, but not divisible by 4."
def singly_even(2), do: raise ArgumentError, "2x2 magic square not possible."
def singly_even(n) do
n2 = div(n, 2)
oms = odd_magic_square(n2)
mat = make_lux_matrix(n2)
square = synthesis(n2, oms, mat)
IO.puts to_string(n, square)
square
end
defp odd_magic_square(m) do # zero beginning, it is 4 multiples.
for i <- 0..m-1, j <- 0..m-1, into: %{},
do: {{i,j}, (m*(rem(i+j+1+div(m,2),m)) + rem(i+2*j-5+2*m, m)) * 4}
end
defp make_lux_matrix(m) do
center = div(m, 2)
lux = List.duplicate(:L, center+1) ++ [:U] ++ List.duplicate(:X, m-center-2)
(for {x,i} <- Enum.with_index(lux), j <- 0..m-1, into: %{}, do: {{i,j}, x})
|> Map.put({center, center}, :U)
|> Map.put({center+1, center}, :L)
end
defp synthesis(m, oms, mat) do
range = 0..m-1
Enum.reduce(range, [], fn i,acc ->
{row0, row1} = Enum.reduce(range, {[],[]}, fn j,{r0,r1} ->
x = oms[{i,j}]
[lux0, lux1, lux2, lux3] = @lux[mat[{i,j}]]
{[x+lux0, x+lux1 | r0], [x+lux2, x+lux3 | r1]}
end)
[row0, row1 | acc]
end)
end
defp to_string(n, square) do
format = String.duplicate("~#{length(to_char_list(n*n))}w ", n) <> "\n"
Enum.map_join(square, fn row ->
:io_lib.format(format, row)
end)
end
end
Magic_square.singly_even(6)</lang>
- Output:
5 8 36 33 13 16 6 7 34 35 14 15 28 25 17 20 12 9 26 27 18 19 10 11 24 21 4 1 32 29 22 23 2 3 30 31
FreeBASIC
<lang freebasic>' version 18-03-2016 ' compile with: fbc -s console ' singly even magic square 6, 10, 14, 18...
Sub Err_msg(msg As String)
Print msg Beep : Sleep 5000, 1 : Exit Sub
End Sub
Sub se_magicsq(n As UInteger, filename As String = "")
' filename <> "" then save square in a file ' filename can contain directory name ' if filename exist it will be overwriten, no error checking
If n < 6 Then
Err_msg( "Error: n is to small")
Exit Sub
End If
If ((n -2) Mod 4) <> 0 Then
Err_msg "Error: not possible to make singly" + _
" even magic square size " + Str(n)
Exit Sub
End If
Dim As UInteger sq(1 To n, 1 To n) Dim As UInteger magic_sum = n * (n ^ 2 +1) \ 2 Dim As UInteger sq_d_2 = n \ 2, q2 = sq_d_2 ^ 2 Dim As UInteger l = (n -2) \ 4 Dim As UInteger x = sq_d_2 \ 2 + 1, y = 1, nr = 1 Dim As String frmt = String(Len(Str(n * n)) +1, "#")
' fill pattern A C
' D B
' main loop for creating magic square in section A
' the value for B,C and D is derived from A
' uses the FreeBASIC odd order magic square routine
Do
If sq(x, y) = 0 Then
sq(x , y ) = nr ' A
sq(x + sq_d_2, y + sq_d_2) = nr + q2 ' B
sq(x + sq_d_2, y ) = nr + q2 * 2 ' C
sq(x , y + sq_d_2) = nr + q2 * 3 ' D
If nr Mod sq_d_2 = 0 Then
y += 1
Else
x += 1 : y -= 1
End If
nr += 1
End If
If x > sq_d_2 Then
x = 1
Do While sq(x,y) <> 0
x += 1
Loop
End If
If y < 1 Then
y = sq_d_2
Do While sq(x,y) <> 0
y -= 1
Loop
End If
Loop Until nr > q2
' swap left side
For y = 1 To sq_d_2
For x = 1 To l
Swap sq(x, y), sq(x,y + sq_d_2)
Next
Next
' make indent
y = (sq_d_2 \ 2) +1
Swap sq(1, y), sq(1, y + sq_d_2) ' was swapped, restore to orignal value
Swap sq(l +1, y), sq(l +1, y + sq_d_2)
' swap right side
For y = 1 To sq_d_2
For x = n - l +2 To n
Swap sq(x, y), sq(x,y + sq_d_2)
Next
Next
' check columms and rows
For y = 1 To n
nr = 0 : l = 0
For x = 1 To n
nr += sq(x,y)
l += sq(y,x)
Next
If nr <> magic_sum Or l <> magic_sum Then
Err_msg "Error: value <> magic_sum"
Exit Sub
End If
Next
' check diagonals
nr = 0 : l = 0
For x = 1 To n
nr += sq(x, x)
l += sq(n - x +1, n - x +1)
Next
If nr <> magic_sum Or l <> magic_sum Then
Err_msg "Error: value <> magic_sum"
Exit Sub
End If
' printing square's on screen bigger when
' n > 19 results in a wrapping of the line
Print "Single even magic square size: "; n; "*"; n
Print "The magic sum = "; magic_sum
Print
For y = 1 To n
For x = 1 To n
Print Using frmt; sq(x, y);
Next
Print
Next
' output magic square to a file with the name provided
If filename <> "" Then
nr = FreeFile
Open filename For Output As #nr
Print #nr, "Single even magic square size: "; n; "*"; n
Print #nr, "The magic sum = "; magic_sum
Print #nr,
For y = 1 To n
For x = 1 To n
Print #nr, Using frmt; sq(x,y);
Next
Print #nr,
Next
Close #nr
End If
End Sub
' ------=< MAIN >=------
se_magicsq(6, "magicse6.txt") : Print
' empty keyboard buffer While Inkey <> "" : Var _key_ = Inkey : Wend Print : Print "hit any key to end program" Sleep End</lang>
- Output:
Single even magic square size: 6*6 The magic sum = 111 35 1 6 26 19 24 3 32 7 21 23 25 31 9 2 22 27 20 8 28 33 17 10 15 30 5 34 12 14 16 4 36 29 13 18 11
Java
<lang java>public class MagicSquareSinglyEven {
public static void main(String[] args) {
int n = 6;
for (int[] row : magicSquareSinglyEven(n)) {
for (int x : row)
System.out.printf("%2s ", x);
System.out.println();
}
System.out.printf("\nMagic constant: %d ", (n * n + 1) * n / 2);
}
public static int[][] magicSquareOdd(final int n) {
if (n < 3 || n % 2 == 0)
throw new IllegalArgumentException("base must be odd and > 2");
int value = 0;
int gridSize = n * n;
int c = n / 2, r = 0;
int[][] result = new int[n][n];
while (++value <= gridSize) {
result[r][c] = value;
if (r == 0) {
if (c == n - 1) {
r++;
} else {
r = n - 1;
c++;
}
} else if (c == n - 1) {
r--;
c = 0;
} else if (result[r - 1][c + 1] == 0) {
r--;
c++;
} else {
r++;
}
}
return result;
}
static int[][] magicSquareSinglyEven(final int n) {
if (n < 6 || (n - 2) % 4 != 0)
throw new IllegalArgumentException("base must be a positive "
+ "multiple of 4 plus 2");
int size = n * n;
int halfN = n / 2;
int subSquareSize = size / 4;
int[][] subSquare = magicSquareOdd(halfN);
int[] quadrantFactors = {0, 2, 3, 1};
int[][] result = new int[n][n];
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
int quadrant = (r / halfN) * 2 + (c / halfN);
result[r][c] = subSquare[r % halfN][c % halfN];
result[r][c] += quadrantFactors[quadrant] * subSquareSize;
}
}
int nColsLeft = halfN / 2;
int nColsRight = nColsLeft - 1;
for (int r = 0; r < halfN; r++)
for (int c = 0; c < n; c++) {
if (c < nColsLeft || c >= n - nColsRight
|| (c == nColsLeft && r == nColsLeft)) {
if (c == 0 && r == nColsLeft)
continue;
int tmp = result[r][c];
result[r][c] = result[r + halfN][c];
result[r + halfN][c] = tmp;
}
}
return result; }
}</lang>
35 1 6 26 19 24 3 32 7 21 23 25 31 9 2 22 27 20 8 28 33 17 10 15 30 5 34 12 14 16 4 36 29 13 18 11 Magic constant: 111
Perl 6
See Magic squares/Perl 6 for a general magic square generator.
- Output:
With a parameter of 6:
35 1 6 26 19 24 3 32 7 21 23 25 31 9 2 22 27 20 8 28 33 17 10 15 30 5 34 12 14 16 4 36 29 13 18 11 The magic number is 111
With a parameter of 10:
92 99 1 8 15 67 74 51 58 40 98 80 7 14 16 73 55 57 64 41 4 81 88 20 22 54 56 63 70 47 85 87 19 21 3 60 62 69 71 28 86 93 25 2 9 61 68 75 52 34 17 24 76 83 90 42 49 26 33 65 23 5 82 89 91 48 30 32 39 66 79 6 13 95 97 29 31 38 45 72 10 12 94 96 78 35 37 44 46 53 11 18 100 77 84 36 43 50 27 59 The magic number is 505
Ruby
<lang ruby>def odd_magic_square(n)
n.times.map{|i| n.times.map{|j| n*((i+j+1+n/2)%n) + ((i+2*j-5)%n) + 1} }
end
def single_even_magic_square(n)
raise ArgumentError, "must be even, but not divisible by 4." unless (n-2) % 4 == 0 raise ArgumentError, "2x2 magic square not possible." if n == 2
order = (n-2)/4
odd_square = odd_magic_square(n/2)
to_add = (0..3).map{|f| f*n*n/4}
quarts = to_add.map{|f| odd_square.dup.map{|row|row.map{|el| el+f}} }
sq = []
quarts[0].zip(quarts[2]){|d1,d2| sq << [d1,d2].flatten}
quarts[3].zip(quarts[1]){|d1,d2| sq << [d1,d2].flatten}
sq = sq.transpose
order.times{|i| sq[i].rotate!(n/2)}
swap(sq[0][order], sq[0][-order-1])
swap(sq[order][order], sq[order][-order-1])
(order-1).times{|i| sq[-(i+1)].rotate!(n/2)}
randomize(sq)
end
def swap(a,b)
a,b = b,a
end
def randomize(square)
square.shuffle.transpose.shuffle
end
def to_string(square)
n = square.size
fmt = "%#{(n*n).to_s.size + 1}d" * n
square.inject(""){|str,row| str << fmt % row << "\n"}
end
puts to_string(single_even_magic_square(6))</lang>
- Output:
23 7 5 21 30 25 18 29 36 13 4 11 14 34 32 12 3 16 19 6 1 26 35 24 27 2 9 22 31 20 10 33 28 17 8 15
zkl
<lang zkl>class MagicSquareSinglyEven{
fcn init(n){ var result=magicSquareSinglyEven(n) }
fcn toString{
sink,n:=Sink(String),result.len(); // num collumns
fmt:="%2s ";
foreach row in (result)
{ sink.write(row.apply('wrap(n){ fmt.fmt(n) }).concat(),"\n") }
sink.write("\nMagic constant: %d".fmt((n*n + 1)*n/2));
sink.close();
}
fcn magicSquareOdd(n){
if (n<3 or n%2==0) throw(Exception.ValueError("base must be odd and > 2"));
value,gridSize,c,r:=0, n*n, n/2, 0;
result:=n.pump(List(),n.pump(List(),0).copy); // array[n,n] of zero
while((value+=1)<=gridSize){
result[r][c]=value; if(r==0){ if(c==n-1) r+=1;
else{ r=n-1; c+=1; }
} else if(c==n-1){ r-=1; c=0; } else if(result[r-1][c+1]==0){ r-=1; c+=1; } else r+=1;
}
result;
}
fcn magicSquareSinglyEven(n){
if (n<6 or (n-2)%4!=0)
throw(Exception.ValueError("base must be a positive multiple of 4 +2"));
size,halfN,subSquareSize:=n*n, n/2, size/4;
subSquare:=magicSquareOdd(halfN);
quadrantFactors:=T(0, 2, 3, 1);
result:=n.pump(List(),n.pump(List(),0).copy); // array[n,n] of zero
foreach r,c in (n,n){
quadrant:=(r/halfN)*2 + (c/halfN);
result[r][c]=subSquare[r%halfN][c%halfN]; result[r][c]+=quadrantFactors[quadrant]*subSquareSize;
}
nColsLeft,nColsRight:=halfN/2, nColsLeft-1;
foreach r,c in (halfN,n){
if ( c<nColsLeft or c>=(n-nColsRight) or
(c==nColsLeft and r==nColsLeft) ){
if(c==0 and r==nColsLeft) continue; tmp:=result[r][c]; result[r][c]=result[r+halfN][c]; result[r+halfN][c]=tmp; }
}
result
}
}</lang> <lang zkl>MagicSquareSinglyEven(6).println();</lang>
- Output:
35 1 6 26 19 24 3 32 7 21 23 25 31 9 2 22 27 20 8 28 33 17 10 15 30 5 34 12 14 16 4 36 29 13 18 11 Magic constant: 111