Ищем все магические квадраты 3 на 3 и 4 на 4

Мало о какой математической теме в инете написано столько же, сколько о магических квадратах, из наших авторов сразу вспоминаются Макарова и Ратушный, зарубежным и вовсе несть числа.

Но вот кода, который бы вывел все магические квадраты, я не нашёл нигде.

Под "всеми квадратами" я имею в виду, по сути, только размерности три на три и четыре на четыре, так как квадрат 1 на 1 - вырожденный случай, магических квадратов 2 на 2 не существует, а при размерности больше четырёх количество квадратов явно не поддастся возможностям "персоналки" :)

Ниже показана программа на C++, выводящая в консоль все 8 магических квадратов третьего порядка. На самом деле, квадрат всего один, если считать с точностью до поворотов и отражений. Программа проверена в консоли Visual Studio 2015, работает.

#include <iostream>
using namespace std;

class MagicSquare {
	int **square;
	bool *used;
	int n;
	int magicSum;
	int total;
public:
    MagicSquare(int n) {
		square = new int *[n];
		for (int i=0; i<n; i++) square[i] = new int [n];
		int k = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) square[i][j] = ++k;
		used = new bool[n*n + 1];
		for (int i = 0; i < n*n + 1; i++) used[i] = false;
		this->n = n;
		this->total = 0;
		magicSum = n* (n*n + 1) / 2;
	}
	bool isValid() {
		int sumD1 = 0;
		int sumD2 = 0;
		for (int i = 0; i < n; i++) {
			int sumR = 0;
			int sumC = 0;
			sumD1 += square[i][i];
			sumD2 += square[i][n - i - 1];
			for (int j = 0; j < n; j++) {
				sumR += square[i][j];
				sumC += square[j][i];
			}
			if (sumR != magicSum || sumC != magicSum) { return false; }
		}
		return (sumD1 == magicSum && sumD2 == magicSum);
	}
	bool solve (int step) { //один любой
		if (step == n*n) {
			return isValid();
		}

		for (int val = 1; val <= n*n; val++) {
			if (used[val]) { continue; }

			used[val] = true;
			square[step / n][step%n] = val;
			if (solve(step + 1)) {
				return true;
			}
			square[step / n][step%n] = 0;
			used[val] = false;
		}

		return false;
	}
	void count (int step) { //подсчитать с выводом
		if (step == n*n) {
			if (isValid()) {
				total++;
				outputSolution();
			}
			return;
		}

		for (int val = 1; val <= n*n; val++) {
			if (used[val]) { continue; }

			used[val] = true;
			square[step / n][step%n] = val;
			count(step + 1);
			square[step / n][step%n] = 0;
			used[val] = false;
		}
	}
	bool validUpTo (int step) {
		for (int r = 0; r < n; r++) {
			if (step == (r + 1)*n - 1) {
				int sum = 0;
				for (int c = 0; c < n; c++) { sum += square[r][c]; }
				return (sum == magicSum);
			}
		}
		for (int c = 0; c < n; c++) {
			if (step == n*(n - 1) + c) {
				int sum = 0;
				for (int r = 0; r < n; r++) { sum += square[r][c]; }
				return (sum == magicSum);
			}
		}
		return true;
	}
	void outputSolution() {
		cout << endl << "#" << total;
		for (int r = 0; r < n; r++) {
			cout << endl;
			for (int c = 0; c < n; c++) {
				cout << square[r][c] << " ";
			}
		}
	}
};

int main() {
	MagicSquare *m = new MagicSquare (3);
	m->count(0);
	//Если нужно одно решение - раскомментарить строчку ниже и убрать выше
	//m->solve(0); m->outputSolution();
	cin.sync(); cin.get();  return 0;
}

Изменённая программа, выполненная в той же среде, формирует список квадратов 4 на 4.

У нас выйдет 880 уникальных квадратов или 7040 разных, если не учитывать повороты и отражения.

Все 7040 квадратов выведутся программой, но пытаться скопировать их из консоли не будем, а продублируем решения в файл с именем 4x4.txt, который будет создан в папке с исполняемым файлом .exe.

#include <iostream>
#include <fstream>
using namespace std;

class MagicSquare {
	int **square;
	bool *used;
	int n;
	int magicSum;
	int total;
	ofstream file;
public:
    MagicSquare(int n) {
		square = new int *[n];
		for (int i=0; i<n; i++) square[i] = new int [n];
		int k = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) square[i][j] = ++k;
		used = new bool[n*n + 1];
		for (int i = 0; i < n*n + 1; i++) used[i] = false;
		this->n = n;
		this->total = 0;
		magicSum = n* (n*n + 1) / 2;
		this->file.open("4x4.txt", ios::out);
	}
	~MagicSquare() {
		file.close();
	}
	bool isValid() {
		int sumD1 = 0;
		int sumD2 = 0;
		for (int i = 0; i < n; i++) {
			sumD1 += square[i][i];
			sumD2 += square[i][n - i - 1];
		}
		return (sumD1 == magicSum && sumD2 == magicSum);
	}
	void count(int step) {
		if (step == n*n) {
			if (isValid()) {
				total++;
				outputSolution();
			}
			return;
		}

		for (int val = 1; val <= n*n; val++) {
			if (used[val]) { continue; }

			used[val] = true;
			square[step / n][step%n] = val;
			if (validUpTo(step)) {
				count(step + 1);
			}
			square[step / n][step%n] = 0;
			used[val] = false;
		}
	}
	bool validUpTo(int step) {
		for (int r = 0; r < n; r++) {
			if (step == (r + 1)*n - 1) {
				int sum = 0;
				for (int c = 0; c < n; c++) { sum += square[r][c]; }
				return (sum == magicSum);
			}
		}

		for (int c = 0; c < n; c++) {
			if (step == n*(n - 1) + c) {
				int sum = 0;
				for (int r = 0; r < n; r++) { sum += square[r][c]; }
				return (sum == magicSum);
			}
		}

		return true;
	}
	void outputSolution() {
		cout << endl << "#" << total;
		file << endl << "#" << total;
		for (int r = 0; r < n; r++) {
			cout << endl;
			file << endl;
			for (int c = 0; c < n; c++) {
				cout.width(2);
				cout << square[r][c] << " ";
				file.width(2);
				file << square[r][c] << " ";
			}
		}
	}
};

int main() {
	MagicSquare *m = new MagicSquare (4);
	m->count(0);
	cin.sync(); cin.get();  return 0;
}

Не пытайтесь сделать это для размерности 5, там 275 305 224 уникальных квадрата и в 8 раз больше возможных решений (ссылка).

Для удобства ниже прилагается архив со всеми квадратами, отформатированными построчно и пронумерованными программой.

 Скачать архив .zip с файлами .txt, все магические квадраты 3x3 и 4x4 (73 Кб)

14.10.2017, 21:53 [4682 просмотра]