ВСЕ решения для Магического квадрата без массива

+-+-+-+
|2|7|6|
+-+-+-+
|9|5|1|
+-+-+-+
|4|3|8|
+-+-+-+

+-+-+-+
|2|9|4|
+-+-+-+
|7|5|3|
+-+-+-+
|6|1|8|
+-+-+-+

// generate possible solution (x)
int a, b, c, d, e, f, g, h, i, x;
x = rand() % 987654322 + 864197532;

// set the for loop to list possible values of x.
// This part needs revison
for (x = 123456788; ((x < 987654322) && (sol == true)); ++x)
{
// split into integers to evaluate
a = x / 100000000;
b = x % 100000000 / 10000000;
c = x % 10000000 / 1000000;
d = x % 1000000 / 100000;
e = x % 100000 / 10000;
f = x % 10000 / 1000;
g = x % 1000 / 100;
h = x % 100 / 10;
i = x % 10;

// Could this be condensed somehow?
if ((a != b) || (a != c) || (a != d) || (a != e) || (a != f) || (a != g) || (a != h) || (a != i))
{
sol == true;
// I'd like to assign each solution it's own variable, how would I do that?
std::cout << x;
}
}
How would I output in ascending order?

Этот вопрос привлек мое внимание, когда я ответил на SO: магический квадрат неправильное размещение некоторых чисел недавно.

// I'd like to assign each solution it's own variable, how would I do that?

Я бы не стал это учитывать. Каждое найденное решение может быть распечатано немедленно (вместо этого сохранено) Цикл с восходящим счетом гарантирует, что вывод с целью.

Я просто не знаю, как создать полный список из девятизначных чисел, которые являются решениями, использующими цикл for.

Ответ перестановка.

В случае OP это набор из 9 различных элементов, для которых желательны все последовательности с различным порядком всех этих элементов.

Количество возможных решений для 9 цифр рассчитывается по факториал:

9! = 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 362880

Буквально, если будут проверены все возможные порядки из 9 цифр, цикл должен выполнить 362880 итераций.

Погуглив на готовый алгоритм (или хотя бы на вдохновение) я обнаружил (к моему удивлению), что C ++ std Библиотека алгоритмов на самом деле хорошо подготовлен к этому:

std::next_permutation()

Преобразует ассортимент [first, last) в следующую перестановку из множества всех перестановок, которые лексикографически упорядочены относительно operator< или же comp, Возвращает true если такая перестановка существует, в противном случае преобразует диапазон в первую перестановку (как если бы std::sort(first, last)) и возвращает false,

Что делает вещи более хитрыми, так это ограничение, касающееся запрета массивов. Предполагая, что запреты массива запрещают std::vector а также std::string также я исследовал идею использования OP вместо одного целого числа.

32 бит int охватывает диапазон [-2147483648, 2147483647], достаточный для хранения даже самой большой перестановки цифр 1 … 9: 987654321. (Может быть, std::int32_t будет лучшим выбором.)

Извлечение отдельных цифр с делением и делением по модулю на 10 немного утомительно. Хранение набора вместо числа с основанием 16 значительно упрощает процесс. Изоляция отдельных элементов (или цифр) теперь становится комбинацией побитовых операций (&, |, ~, <<, а также >>). Обратной ничьей является то, что 32 бита больше не достаточно для девяти цифр — я использовал std::uint64_t,

Я помещал вещи в капсулы class Set16, Я решил предоставить ссылочный тип и двунаправленные итераторы. Немного поигравшись, я пришел к выводу, что это не так просто (если не невозможно). Чтобы повторно реализовать std::next_permutation() в соответствии с приведенным примером кода на cppreference.com был мой более легкий выбор.

362880 строк вывода для демонстрации. Следовательно, мой образец делает это для меньшего набора из 3 цифр, который имеет 3! (= 6) решения:

#include <iostream>
#include <cassert>
#include <cstdint>

// convenience types
typedef unsigned uint;
typedef std::uint64_t uint64;

// number of elements 2 <= N < 16
enum { N = 3 };

// class to store a set of digits in one uint64
class Set16 {
public:
enum { size = N };

private:
uint64 _store; // storage

public:
// initializes the set in ascending order.
// (This is a premise to start permutation at first result.)
Set16(): _store()
{
for (uint i = 0; i < N; ++i) elem(i, i + 1);
}

// get element with a certain index.
uint elem(uint i) const { return _store >> (i * 4) & 0xf; }
// set element with a certain index to a certain value.
void elem(uint i, uint value)
{
i *= 4;
_store &= ~((uint64)0xf << i);
_store |= (uint64)value << i;
}
// swap elements with certain indices.
void swap(uint i1, uint i2)
{
uint temp = elem(i1);
elem(i1, elem(i2));
elem(i2, temp);
}
// reverse order of elements in range [i1, i2)
void reverse(uint i1, uint i2)
{
while (i1 < i2) swap(i1++, --i2);
}
};

// re-orders set to provide next permutation of set.
// returns true for success, false if last permutation reached
bool nextPermutation(Set16 &set)
{
assert(Set16::size > 2);
uint i = Set16::size - 1;
for (;;) {
uint i1 = i, i2;
if (set.elem(--i) < set.elem(i1)) {
i2 = Set16::size;
while (set.elem(i) >= set.elem(--i2));
set.swap(i, i2);
set.reverse(i1, Set16::size);
return true;
}
if (!i) {
set.reverse(0, Set16::size);
return false;
}
}
}

// pretty-printing of Set16
std::ostream& operator<<(std::ostream &out, const Set16 &set)
{
const char *sep = "";
for (uint i = 0; i < Set16::size; ++i, sep = ", ") out << sep << set.elem(i);
return out;
}

// main
int main()
{
Set16 set;
// output all permutations of sample
unsigned n = 0; // permutation counter
do {
#if 1 // for demo:
std::cout << set << std::endl;
#else // the OP wants instead:
/* @todo check whether sample builds a magic square
* something like this:
* if (
*   // first row
*   set.elem(0) + set.elem(1) + set.elem(2) == 15
* etc.
*/
#endif // 1
++n;
} while(nextPermutation(set));
std::cout << n << " permutations found." << std::endl;
// done
return 0;
}

Выход:

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
6 permutations found.

Демоверсия жизни на ideone

Итак, я здесь: перестановки без массивов.

---

Наконец, еще одна идея пришла мне в голову. Возможно, целью задания было скорее научить «взгляду извне» … Возможно, стоит изучить описание Магические квадраты снова:

Эквивалентные магические квадраты

Любой магический квадрат можно вращать и отражать, чтобы получить 8 тривиально различных квадратов. В теории магических квадратов все они обычно считаются эквивалентными, и говорят, что восемь таких квадратов составляют один класс эквивалентности.

Количество магических квадратов данного порядка

За исключением вращений и отражений, существует ровно один магический квадрат 3 × 3 …

Однако я не знаю, как это можно сочетать с требованием сортировки решений в порядке возрастания.