Kwadrat magiczny 3x3

Definicja

Kwadrat magiczny n×n to tablica w którą wpisano liczby całkowite z przedziału [1, 2, .., n²] w taki sposób, że suma liczb w każdym wierszu, kolumnie i przekątnej jest taka sama. Taka suma liczb nazywana jest sumą magiczną. Suma magiczna M wynosi n(n² + 1)/2. Dowodzi się, że kwadratów magicznych jest nieskończenie wiele.

Ciekawostką jest fakt, że nie istniej kwadrat magiczny 2×2. Istnieją jeszcze kwadraty półmagiczne, które nie spełniają warunku tej samej sumy na przekątnych co w wierszach i kolumnach.

Przykład

Oto przykładowy kwadrat magiczny:

Suma liczb w każdym wierszu, kolumnie i przekątnej wynosi dokładnie 15 co można sprawdzić.

Implementacja

Spostrzeżenia

Szukanie kwadratów magicznych jest dla komputera bardzo proste, ale bardzo czasochłonne. W przypadku sprawdzania każdego możliwego ustawienia liczb kwadratu magicznego n×n należałoby sprawdzić n²! możliwości. W przypadku najprostszego przypadku 3×3 oznaczałoby sprawdzenie 362,880 możliwości, a dla 4×4 ponad 2·10¹³.

Istnieją metody, które pozwalają wyznaczyć kwadrat magiczny bez problemu (patrz Zadanie 1), ale nie jest możliwe ich zastosowanie do kwadratów magicznych innych wielkości.

Ograniczenia sprawdzania

Najprostszą metodą na ograniczenie sprawdzanych możliwych kwadratów jest wyznaczenie wszystkich ciągów n liczbowych, których suma wynosi tyle co suma magiczna M = n(n² + 1)/2. Następnie wszystkie wyznaczone n-tki można wykorzystać do utworzenia kwadratu magicznego. Ogranicza to tworzenie do dopasowania n-tek z wszystkich znalezionych.

Dla wspomnianego kwadratu magicznego 3×3 jest 48 takich trójek. Są to wszystkie permutacje poniższych trójek:

1. 6 5 4
2. 7 5 3
3. 7 6 2
4. 8 4 3
5. 8 5 2
6. 8 6 1
7. 9 4 2
8. 9 5 1

Oznacza to, że sprawdzonych zostanie 48·47·46 = 103776 kombinacji. Wynik ten można poprawić poprzez optymalizację wyboru kolejnych trójek tworzących kwadrat magiczny. Warto zauważyć, że jeśli w pierwszej trójce występuje to już nie może zostać wybrana trójka zawierająca 9. Tego typu optymalizacja pozwala ograniczyć sprawdzanie do 15,840. Jest to poprawa wydajności blisko 23 razy. Tego typu metodę spokojnie można przenieść na kwadraty magiczne wyższych rzędów.

Wyznaczanie kwadratu magicznego

Przedstawiony dalej kod znajduje wszystkie możliwe kwadraty magiczne dla danej wielkości n. Pomimo zastosowanych prób optymalizacji należy mieć na uwadze, że istnieje bardzo dużo możliwości dla kwadratów większych od 3×3.

1. void szukajKwadratowMagicznych(int n) {
2.   int M = n*(n*n + 1) / 2;
3.   int** table = new int*[n];
4.   for (int i = 0; i < n; i++)
5.     table[i] = new int[n];
6.   bool* wyl = new bool[n*n];
7.   for (int i = 0; i < n*n; i++)
8.     wyl[i] = false;
9.   szukaj(table, wyl, n, M, M);
10.   for (int i = 0; i < n; i++)
11.     delete table[i];
12.   delete table, wyl;
13. }

Implementacja poszukiwania kwadratu magicznego zaczyna się od (2.) wyliczenia sumy magicznej, a następnie zadeklarowaniu (3. - 5.) tablicy przechowującej aktualny kwadrat magiczny. Dalej potrzebna jest tablica, która szybko pozwoli stwierdzić czy dana liczba jest już wykorzystana w kwadracie magicznym. Jest to (6.) tablica typu bool i (7. - 8.) początkowo wszystkie wartości są ustawione na fałsz. (9.) Zadeklarowane tablice wykorzystuje funkcja szukaj(), która wypisuje wszystkie znalezione kwadraty magiczne. Na koniec (10. - 12.) należy zdealokować wszystkie zbędne tablice pomocnicze.

Szukanie kwadratu

Funkcja szukaj() przyjmuje kolejno: table - aktualny kwadrat magiczny, wyl - tablica wylosowanych liczb, n - wielkość kwadratu, M - suma magiczna, suma - aktualnie brakująca suma w rzędzie do M, row - aktualnie wyszukiwany wiersz oraz col - aktualnie zapisywana pozycja w wierszu row. Początkowo poszukiwania zaczynają się od pozycji (0, 0).

1. void szukaj(int** table, bool* wyl, int n, int M, int suma, int row = 0, int col = 0) {
2.   if (row != n) {
3.     if (col != n) {
4.       for (int a = n*n - 1; a >= 0; a--) {
5.         if (!wyl[a]) {
6.           wyl[a] = true;
7.           table[row][col] = a + 1;
8.           szukaj(table, wyl, n, M, suma - table[row][col], row, col + 1);
9.           wyl[a] = false;
10.         }
11.       }
12.     } else {
13.       if (suma != 0)
14.         return;
15.       szukaj(table, wyl, n, M, M, row + 1);
16.     }

W przypadku, gdy wciąż (2.) istnieje wiersz do zapisu oraz (3.) pole w aktualnym wierszu to (4.) sprawdź każdą liczbę całkowitą z przedziału [0, n² - 1] (5.) czy została już wykorzystana. Jeśli nie to (6.) odznacz wykorzystanie , (7.) wpisz liczbę do tabeli, (8.) rozpocznij poszukiwania dalszych elementów tabeli, a po zakończeniu poszukiwań z danym układem (9.) odznacz, że dana liczba jest użyta.

W przypadku, gdy (12.) nie ma już pól do zapisu danych w aktualnym wierszu to (13.) sprawdź czy wiersz sumuje się do 15. Jeśli nie to (14.) zakończ poszukiwania, a w przeciwnym wypadku (15.) przejdź do losowania następnego wiersza. Zaletą sprawdzania co wiersz czy sumuje się do 15 jest ograniczenie poszukiwań.

17.   } else {
18.     for (int i = 0; i < n; i++) {
19.       suma = M;
20.       for (int j = 0; j < n; j++)
21.         suma -= table[j][i];
22.       if (suma != 0)
23.         return;
24.     }
25.     suma = M;
26.     for (int j = 0; j < n; j++)
27.       suma -= table[j][j];
28.     if (suma != 0)
29.       return;
30.     suma = M;
31.     for (int j = 0; j < n; j++)
32.       suma -= table[j][n - j - 1];
33.     if (suma != 0)
34.       return;
35.     for (int x = 0; x < n; x++) {
36.       for (int y = 0; y < n; y++) {
37.         cout << table[x][y] << " ";
38.       }
39.       cout << endl;
40.     }
41.     cout << endl << endl;
42.   }
43. }

Poszukiwania się kończą, gdy nie ma już żadnego wiersza do ustalenia. Wtedy (17. - 23.) należy sprawdzić czy kolumny się zgadzają oraz (24. - 28.) jedna i (29. - 33.) druga przekątna. Jeśli tak to (34. - 40.) to pozostaje wypisać znaleziony kwadrat magiczny.

Testowanie funkcji

w celu wypisania wszystkich kwadratów magicznych 3×3 wystarczy poniższa funkcja main(). Warto zauważyć, że napisany kod znajduje wszystkie kwadraty magiczne nie zwracając uwagi na to czy są przekształceniami czy nie.

1. int main() {
2.   szukajKwadratowMagicznych(3);
3.   system("pause");
4.   return 0;
5. }

• Kod źródłowy Implementacja

Zadania

Wzór na kwadrat magiczny 3×3

Kwadrat magiczny 3×3 można wyznaczyć przy pomocy poniższego wzoru-tabeli:

Wyznaczony kwadrat będzie magiczny pod warunkiem, że 0 < a < b < c - a i b ≠ 2a.

Zadanie 1

Napisz program, który wczyta od użytkownika liczby a, b, c i na tej podstawie wyznaczy kwadrat magiczny, albo jeśli to niemożliwe to wypisze odpowiedni komunikat na ekran.

• Kod źródłowy Zadanie 1