用 Java 創建魔方

一、簡介

在本文中，我們將了解如何創建幻方。我們將了解什麼是幻方、創建它們的算法以及如何在 Java 中實現它。

2.什麼是幻方？

幻方是一個數學難題。我們從一個大小為n*n的正方形開始，需要用數字填充它，使得 1 到n²之間的每個數字只出現一次，並且每行、列和對角線的總和為相同的數字。

例如，大小為 3*3 的幻方可能是：

在這裡我們可以看到每個單元格都有不同的數字，在 1 到 9 之間。我們還可以看到每行、每列和對角線的總和為 15。

正好這裡多了一個檢查。每行、列和對角線的總和也等於只需知道n即可計算出的值。具體來說：

因此，對於 3*3 的正方形，其值為 (3³ + 3)/2 = 15。

事實上，根據正方形的大小，可以使用三種相對簡單的算法來生成這些算法：

• 每邊的單元格數為奇數
• 雙：每側有偶數個單元格。這是當每一邊都是 4 的倍數時。
• 單個：每側有偶數個單元格。這是當每一邊都是 2 的倍數但不是 4 的倍數時。

我們稍後將介紹每種算法以及如何用 Java 生成它們。

3. 驗證幻方

在生成幻方之前，我們首先需要能夠證明給定的方確實滿足要求。也就是說，每行、每列和對角線的總和為相同的值。

在我們這樣做之前，讓我們定義一個類來表示我們的正方形：

public class MagicSquare {
 private int[][] cells;

 public MagicSquare(int n) {
 this.cells = new int[n][];

 for (int i = 0; i < n; ++i) {
 this.cells[i] = new int[n];
 }
 }

 public int getN() {
 return cells.length;
 }

 public int getCell(int x, int y) {
 return cells[x][y];
 }

 public void setCell(int x, int y, int value) {
 cells[x][y] = value;
 }
 }

這只是二維整數數組的包裝。然後，我們確保數組的大小正確，並且我們有一種簡單的方法來訪問數組中的各個單元格。

現在我們已經有了這個，讓我們編寫一個方法來驗證該正方形確實是一個幻方。

首先，我們將計算行、列和對角線的預期值，總和為：

int n = getN();
 int expectedValue = ((n * n * n) + n) / 2;

接下來，我們將開始對值求和並檢查它們是否按預期輸出。我們首先做對角線：

// Diagonals
 if (IntStream.range(0, n).map(i -> getCell(i, i)).sum() != expectedValue) {
 throw new IllegalStateException("Leading diagonal is not the expected value");
 }
 if (IntStream.range(0, n).map(i -> getCell(i, n - i - 1)).sum() != expectedValue) {
 throw new IllegalStateException("Trailing diagonal is not the expected value");
 }

這只是從 0 迭代到n ，抓取相應對角線上該點的每個單元格並對它們求和。

接下來，行和列：

// Rows
 IntStream.range(0, n).forEach(y -> {
 if (IntStream.range(0, n).map(x -> getCell(x, y)).sum() != expectedValue) {
 throw new IllegalStateException("Row is not the expected value");
 }
 });

 // Cols
 IntStream.range(0, n).forEach(x -> {
 if (IntStream.range(0, n).map(y -> getCell(x, y)).sum() != expectedValue) {
 throw new IllegalStateException("Column is not the expected value");
 }
 });

在這裡，我們根據需要迭代每行或每列上的所有單元格，並對所有這些值求和。如果在任何這些情況下，我們得到的值與預期不同，那麼我們將拋出異常，表明出現了問題。

4. 生成幻方

至此，我們可以正確驗證任意給定的方格是否是幻方。所以現在我們需要能夠生成它們。

我們之前看到，根據正方形的大小，這裡可以使用三種不同的算法。我們將依次討論每一個。

4.1.奇數尺寸正方形的算法

我們要研究的第一個算法是針對每邊具有奇數個單元的正方形的算法。

當生成這種大小的幻方時，我們總是首先將第一個數字放入頂行的中間單元格中。然後我們繼續按如下方式放置每個後續數字：

• 首先，我們嘗試將其放置在緊鄰前一個方塊的上方的單元格中。執行此操作時，我們會在邊緣處環繞，因此，例如，在頂行之後，我們將移動到底行。
• 如果所需的單元格已填充，我們會將下一個數字放置在前一個數字正下方的單元格中。同樣，在執行此操作時，我們會在邊緣處進行環繞。

例如，在我們的 3*3 正方形中，我們從頂部中間的單元格開始。然後我們向上和向右移動，環繞找到右下角的單元格：

從這裡開始，我們將向上和向右移動以填充左中單元格。之後，向上和向右移動回到第一個單元格，因此，我們必須向下移動到左下角單元格：

如果我們繼續這樣做，我們最終將用有效的幻方填充每個方格。

4.2.奇數尺寸正方形的實現

那麼我們如何在 Java 中做到這一點呢？

首先，讓我們放置第一個數字。它位於頂行的中心單元格中：

int y = 0;
 int x = (n - 1) / 2;
 setCell(x, y, 1);

完成此操作後，我們將循環所有其他數字，依次放置每個數字：

for (int number = 2; number <= n * n; ++number) {
 int nextX = ...;
 int nextY = ...;

 setCell(nextX, nextY, number);

 x = nextX;
 y = nextY;
 }

現在我們只需要確定nextX和nextY使用什麼值。

首先，我們將嘗試向上和向右移動，並根據需要進行環繞：

int nextX = x + 1;
 if (nextX == n) {
 nextX = 0;
 }

 int nextY = y - 1;
 if (nextY == -1) {
 nextY = n - 1;
 }

但是，我們還需要處理下一個單元格已被佔用的情況：

if (getCell(nextX, nextY) != 0) {
 nextX = x;

 nextY = y + 1;
 if (nextY == n) {
 nextY = 0;
 }
 }

將所有這些放在一起，我們就可以實現生成任何奇數大小的幻方。例如，由此生成的9*9正方形為：

4.3.**雙偶大小正方形**的算法

上述算法適用於奇數大小的正方形，但不適用於偶數大小的正方形。事實上，對於這些，我們需要兩種算法之一，具體取決於確切的大小。

雙偶正方形是邊長為 4 的倍數的正方形，例如 4*4、8*8、12*12 等。為了生成這些正方形，我們需要在正方形中分離出 4 個特殊區域。這些區域是距每條邊n/4而距角大於n/4的單元格：

完成此操作後，我們現在填寫數字。這是分兩次完成的。第一遍從左上角開始，從左到右處理行。每次我們在未突出顯示的單元格上時，我們都會添加序列中的下一個數字：

第二遍完全相同，但從右下角開始，從右向左運行，並且僅向突出顯示的單元格添加數字：

此時，我們已經得到了有效的幻方。

4.4.**雙偶尺寸正方形**的**實現**

為了在 Java 中實現這一點，我們需要使用兩種技術。

首先，我們實際上可以一次將所有數字相加。如果我們在一個未突出顯示的單元格上，那麼我們會像以前一樣執行操作，但如果我們在一個突出顯示的單元格上，那麼我們會從 n² 開始倒數：

int number = 1;

 for (int y = 0; y < n; ++y) {
 for (int x = 0; x < n; ++x) {
 boolean highlighted = ...;

 if (highlighted) {
 setCell(x, y, (n * n) - number + 1);
 } else {
 setCell(x, y, number);
 }

 number += 1;
 }
 }

現在我們只需要計算出我們所認為的突出顯示的方塊。我們可以通過檢查 x 和 y 坐標是否在範圍內來做到這一點：

if ((y < n/4 || y >= 3*n/4) && (x >= n/4 && x < 3*n/4)) {
 highlighted = true;
 } else if ((x < n/4 || x >= 3*n/4) && (y >= n/4 && y < 3*n/4)) {
 highlighted = true;
 }

我們的首要條件是針對正方形頂部和底部的突出顯示區域，而第二個條件是針對正方形左側和右側的突出顯示區域。我們可以看到它們實際上是相同的，只是在檢查中調換了x和y 。在這兩種情況下，我們都位於該邊正方形的 1/4 範圍內以及距相鄰角的 1/4 和 3/4 之間。

將所有這些放在一起，我們就可以實現生成任何雙偶大小的幻方。比如我們這樣生成的8*8的正方形是：

4.5.**單偶尺寸正方形**的算法

我們最終的正方形大小是單偶正方形。也就是說，邊可被 2 整除，但不能被 4 整除。這還要求邊長至少為 6 個單元格 - 2*2 幻方沒有解，因此 6*6 是最小的單偶數我們可以解決的幻方。

我們首先將它們分成四等分——每個四等分都是一個奇數大小的正方形。然後使用與奇數大小的魔方相同的算法來填充它們，只是為每個像限分配不同的數字範圍——從左上角四分之一開始，然後是右下角，右上角，最後是底部 -左邊：

一旦我們使用奇數大小的算法填充了所有的方塊，我們仍然沒有一個有效的幻方。此時我們會注意到，所有列加起來都是正確的數字，但行和對角線卻沒有。但是，我們還會注意到上半部分的行加起來都是相同的數字，後半部分的行加起來也都是相同的數字：

我們可以通過在上半部和下半部之間執行多次交換來解決這個問題，如下所示：

• 位於中心左側的左上象限頂行的每個單元格。
• 位於中心左側的左上象限底行的每個單元格。
• 這些之間的每行上的單元格數量相同，但從其中開始一個單元格。
• 右上象限中每行的單元格比這些單元格少一個，但從右側開始。

看起來如下：

現在這是一個有效的幻方，每行、每列和對角線加起來都是相同的值 - 在本例中為 505。

4.6.**單偶尺寸正方形**的**實現**

其實現將建立在我們對奇數大小的正方形所做的基礎上。首先我們需要計算一些用於生成的值：

int halfN = n/2;
 int swapSize = n/4;

請注意我們如何將swapSize計算為n/4 ，然後將其存儲到 int 中。這實際上是向下舍入，因此對於n=10 ，我們將得到swapSize值為 2。

接下來，我們需要填充網格。我們假設我們已經有一個用於執行奇數平方算法的函數，僅進行適當的偏移：

populateOddArea(0, 0, halfN, 0);
 populateOddArea(halfN, halfN, halfN, halfN * halfN);
 populateOddArea(halfN, 0, halfN, (halfN * halfN) * 2);
 populateOddArea(0, halfN, halfN, (halfN * halfN) * 3);

現在我們只需要執行交換即可。再次，我們假設我們有一個用於交換正方形中的單元格的函數。

交換左象限中的單元格只需從左側迭代swapSize並執行交換即可完成：

for (int x = 0; x < swapSize; ++x) {
 swapCells(x, 0, x, halfN); // Top row
 swapCells(x, halfN - 1, x, n - 1); // Bottom row

 // All in-between rows.
 for (int y = 1; y < halfN - 1; ++y) {
 swapCells(x + 1, y, x + 1, y + halfN);
 }
 }

最後，我們交換右象限的單元格。這是通過從右側迭代swapSize – 1並執行交換來完成的：

for (int x = 0; x < swapSize - 1; ++x) {
 for (int y = 0; y < halfN; ++y) {
 swapCells(n - x - 1, y, n - x - 1, y + halfN);
 }
 }

將所有這些放在一起，我們就可以實現生成任何單偶數大小的幻方。比如我們這樣生成的10*10的正方形如下：

5. 總結

在這裡，我們了解了用於創建幻方的算法，並了解瞭如何在 Java 中實現這些算法。

與往常一樣，我們可以在 GitHub 上找到本文中的所有代碼。