魔方陣 – C と Python の例を使用して 3×3 パズルを解く

魔方陣とは何ですか?

魔方陣は、特殊な数字が配置された正方行列です。 これらの数字は、各対角線、行、列の数字の合計が同じになるように配置されます。 マジックスクエアares ゲームは、レクリエーション数学で使用される単純な論理パズルです。

マジックスクエアares 例:

マジックスクエア

上の図は、次数 3 の魔方陣の例です。各対角線、行、列の合計は 15 です。

魔方陣の仕組み

マジックスクエアares は、n^2 の正の整数で構成される n*n 行列です。 正方行列の行または列の数は、行列の次数と呼ばれます。

通常、マジックスクares パズルには奇数の順序があり、1 から n^2 までの整数が含まれます。 各対角線、行、列の合計は同じです。 この数値はマジックサムまたはマジック定数と呼ばれます。 一般に、このマジック サムは行列の次数に依存します。 魔法の広場ares 次数 n の魔法の和を求める公式は、次のとおりです。

魔方陣の作品

整数 3 の魔方陣の例を見てみましょう。つまり、魔方陣の和は次のようになります。

魔方陣の作品

魔方陣の作品

なぜそれらはマジックと呼ばれるのでしょうか?

古代の数学者は、いくつかの興味深い数字の組み合わせの性質に魅了されました。 魔方陣もその一つでした。 マジックスクワの最も初期の証拠ares その起源は紀元前190年の中国にまで遡ります。

いくつかの研究では、マジックスクエアの証拠が示されています。ares 古代日本、インド、アラビアのパズル。 いくつかの伝説に基づいて、それらの特別な数字の構成は魔法の世界に関係していると考えられていました。 したがって、それらの平方ares マジックスクエアと名付けられましたares.

魔方陣の種類

マジックスクにはさまざまなバリエーションがありますares 数学 -

  • 通常の魔方陣: このタイプの魔方陣には、最初の n^2 個の数値が含まれます。
  • 準魔方陣: このタイプでは、行と列の合計がマジック定数となります。
  • シンプルな魔方陣: 前のタイプとは対照的に、行、列、および両方の対角線の合計が魔法定数となります。
  • 最も完璧な魔方陣: これは 2 つの特別なプロパティを持つ通常の魔方陣です。 ここで、行列の 2 × 2 の各サブスクエアの合計は 2(n^1+2) になります。 n/XNUMX squ である数値のペアares n^2+1 へのグリッド和は別として。

特性に基づいて、さらに多くの種類の魔法のスクリューがありますares。 しかし、私たちが単に魔方陣について言及するときは常に、それが奇数次の正規の単純な魔方陣であると想定します。

魔方陣生成アルゴリズム

奇数次のマジック squ を生成するアルゴリズムares 次のとおりです。

  • 最初の数値または 1 は (n/2, n-1) に格納されます。ここで、最初の座標は行位置、XNUMX 番目の座標は列位置です。 後の手順のために、この位置を (x, y) として示します。
  • 次の数値は (x-1, y+1) に保存されます。 ポジションが有効でない場合は、次のことを検討します。wing 条件。
    1. 行位置が -1 の場合、n-1 にワープします。 同様に、計算された列位置が n の場合、0 にワープします。
    2. 計算された位置にすでに数値が含まれている場合、行の位置は 1 ずつ増加し、列の位置は 2 ずつ減少します。
    3. 行の位置が -1 で、対応する列の位置が n の場合、新しい位置は (0, n-2.

注: このアルゴリズムは有効なマジック squ のみを生成します。ares 奇妙な順序です。 また、この魔方陣は最初の n^2 個の数値を持つ通常の魔方陣であると考えられます。 さらに、同じ n 値に対して複数の解が存在する可能性があります。

例を挙げて、それがどのように機能するかを見てみましょう。 次数 3 の魔方陣を見つけたいとします。これは単純で通常の奇数次の魔方陣であるため、1 から 3^2 または 9 までのすべての数値が含まれます。

どういう仕組みで、どうすればいいのですか?

私たちによると アルゴリズム、手順は次のとおりですwing:

ステップ1) 最初の数字または 1 は (3/2, 3-1) または (1, 2) の位置になります。 慣例により、後のステップでは x= 1 および y= 2 を考慮します。

魔方陣生成アルゴリズム

ステップ2) 残りの数値の位置は次のように計算されます。wing やり方―

番号 2 の位置:

次の数値は (x-1, y+1) または (0, 3) になりますが、これは有効な位置ではありません。 条件 (a) を使用すると、対応する有効な位置は (0,0) になります。 したがって、x= 0、y= 0 となります。

魔方陣生成アルゴリズム

番号 3 の位置:

番号 3 は (x-1, y+1) または (-1, 1) にありますが、これは有効な位置ではありません。 条件 (a) を使用すると、有効な行位置は n-1 または 2 になります。したがって、番号 3 は (2, 1) になります。 次の数値は、x= 2、y= 1 です。

魔方陣生成アルゴリズム

番号 4 の位置:

数値 4 は (x-1, y+1) または (1, 2) にある必要があり、これは有効な位置です。 ただし、その位置にはすでに番号が含まれています。 条件 (b) によれば、有効な位置は (1+1, 2-2) または (2,0) になります。 次の数値 x= 2、y= 0 の場合。

魔方陣生成アルゴリズム

番号 5 の位置:

数値 5 は (x-1, y+1) または (1, 1) にある必要があり、これは有効な位置です。 次の数値の場合、x= 1、y= 1 となります。

魔方陣生成アルゴリズム

番号 6 の位置:

数値 6 は (x-1, y+1) または (0, 2) にある必要があり、これは有効な位置です。 次の数値の場合、x= 0、y= 2 となります。

魔方陣生成アルゴリズム

番号 7 の位置:

番号 7 は (x-1, y+1) または (-1, 3) にある必要がありますが、これは有効な位置ではありません。 条件 (c) によれば、有効な位置は (0, n-2) または (0, 1) になります。 次の数値については、x= 0、y= 1 となります。

魔方陣生成アルゴリズム

番号 8 の位置:

数値 8 は (x-1, y+1) または (-1, 2) にある必要がありますが、これは有効な位置ではありません。 条件 (a) を使用すると、有効な位置は (2, 2) になります。 次の数値の場合、x= 2、y= 2 となります。

魔方陣生成アルゴリズム

番号 9 の位置:

数字 9 は (x-1, y+1) または (1, 3) にある必要がありますが、これは有効な位置ではありません。 条件 (a) を使用すると、有効な位置は (1, 0) になります。

魔方陣生成アルゴリズム

疑似コード

Begin
	Declare an array of size n*n
	Initialize the array to 0
	Set row = n/2
	Set column = n-1
	For all number i: from 1 to n*n
		If the row = -1 and column = n
			row = 0
			column = n-2
		Else
			If row = -1
				row = n-1
			If column = n
				column = 0
		If the position already contains a number
			decrement column by 2
			increment row by 1
			continue until the position is not 0
		Else
			put the number i into the calculated position
			increment i		
		Increment column value
		Decrement row value
End		

C++ コードの魔方陣

入力:

/*
A C/C++ program for generating odd order magic squares
*/
#include <bits/stdc++.h>
using namespace std;

void GenerateMagicSquare(int n)
{
    int magic[n][n];
    //initializing the array
    for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
	        magic[i][j] = 0;
    //setting row and column value
    int i = n / 2;
    int j = n - 1;
    for (int k = 1; k <= n * n;) 
    {
//checking condition (c)
	if (i == -1 && j == n) 
	{
		j = n - 2;
		i = 0;
	}
	else 
	{
		//checking condition (a)
		if (j == n)
			j = 0;
		if (i < 0)
			i = n - 1;
		}
		//checking condition (b)
		if (magic[i][j]) 
		{
			j -= 2;
			i++;
			continue;
		}
		else
		{
		   	//placing the number into the array
		   	magic[i][j] = k; 
			k++;
		}	
		//for the next number setting (i-1, j+1)
		j++;
		i--; 
	}
	//printing the matrix
	for (int i = 0; i < n; i++)
 {
		for (int j = 0; j < n; j++)
			cout << magic[i][j] << "  ";
		cout << endl;
	}	
}
int main()
{
	//This code works for only odd numbers
	int n = 7;
	cout<<"The magic sum is " << n*(n*n+1)/2 <<endl;
	GenerateMagicSquare(n);
	return 0;
}

例の出力:

The magic sum is 175

20  12  4  45  37  29  28
11  3  44  36  35  27  19
2  43  42  34  26  18  10
49  41  33  25  17  9  1
40  32  24  16  8  7  48
31  23  15  14  6  47  39
22  21  13  5  46  38  30

Python コードの魔方陣

def GenerateMagicSquare(n):
#initializing the array
	magic = [[0 for x in range(n)]
				for y in range(n)]
	#setting row and column value
	i = n // 2
	j = n - 1
	k = 1
	while k <= (n * n):
	    #checking condition (c)
		if i == -1 and j == n: 
			j = n - 2
			i = 0
		else:
			#checking condition (a)
			if j == n:
				j = 0
			if i < 0:
				i = n - 1
        #checking conditon (b)
		if magic[i][j]: 
			j = j - 2
			i = i + 1
			continue
		else:
		    #placing the number into the array
			magic[i][j] = k
			k = k + 1
        #for the next number setting (i-1, j+1)
		j = j + 1
		i = i - 1 
	#printing the matrix
	for i in range(0, n):
		for j in range(0, n):
			print('%2d ' % (magic[i][j]),end='')
			if j == n - 1:
				print()
#This code works for only odd numbers
n = 7
print("The magic sum is ",n * (n * n + 1) // 2, "\n")
GenerateMagicSquare(n)

例の出力:

The magic sum is  175

20 12  4 45 37 29 28 
11  3 44 36 35 27 19 
 2 43 42 34 26 18 10 
49 41 33 25 17  9  1 
40 32 24 16  8  7 48 
31 23 15 14  6 47 39 
22 21 13  5 46 38 30

とplex性分析

  • スペースコムplexity: 魔方陣行列を維持するには、*n 配列が必要です。 ということで、スペースコムplex性は O(n^2) になります。
  • タイムコムplexity: Magic Squ の生成に使用したコードares math は XNUMX つのループで構成されます。 外側のループは n 回実行され、内側のループも n 回実行されます。 最終的にはタイムコムplex性は O(n^2) です。