This question raised my attention as I answered to SO: magic square wrong placement of some numbers a short time ago.
// I'd like to assign each solution it's own variable, how would I do that?
I wouldn't consider this. Each found solution can be printed immediately (instead stored). The upwards-counting loop grants that the output is in order.
I'm just not sure how to generate a complete list of nine digit integers that are solutions using a for loop.
The answer is Permutation.
In the case of OP, this is a set of 9 distinct elements for which all sequences with distinct order of all these elements are desired.
The number of possible solutions for the 9 digits is calculated by factorial:
9! = 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 362880
Literally, if all possible orders of the 9 digits shall be checked the loop has to do 362880 iterations.
Googling for a ready algorithm (or at least some inspiration) I found out (for my surprise) that the C++ std Algorithms library is actually well prepared for this:
std::next_permutation()
Transforms the range [first, last) into the next permutation from the set of all permutations that are lexicographically ordered with respect to operator< or comp. Returns true if such permutation exists, otherwise transforms the range into the first permutation (as if by std::sort(first, last)) and returns false.
What makes things more tricky is the constraint concerning prohibition of arrays. Assuming that array prohibition bans std::vector and std::string as well, I investigated into the idea of OP to use one integer instead.
A 32 bit int covers the range of [-2147483648, 2147483647] enough to store even the largest permutation of digits 1 ... 9: 987654321. (May be, std::int32_t would be the better choice.)
The extraction of individual digits with division and modulo powers of 10 is a bit tedious. Storing the set instead as a number with base 16 simplifies things much. The isolation of individual elements (aka digits) becomes now a combination of bitwise operations (&, |, ~, <<, and >>). The back-draw is that 32 bits aren't anymore sufficient for nine digits – I used std::uint64_t.
I capsuled things in a class Set16. I considered to provide a reference type and bidirectional iterators. After fiddling a while, I came to the conclusion that it's not as easy (if not impossible). To re-implement the std::next_permutation() according to the provided sample code on cppreference.com was my easier choice.
362880 lines ouf output are a little bit much for a demonstration. Hence, my sample does it for the smaller set of 3 digits which has 3! (= 6) solutions:
#include <iostream>
#include <cassert>
#include <cstdint>
typedef unsigned uint;
typedef std::uint64_t uint64;
enum { N = 3 };
class Set16 {
public:
enum { size = N };
private:
uint64 _store;
public:
Set16(): _store()
{
for (uint i = 0; i < N; ++i) elem(i, i + 1);
}
uint elem(uint i) const { return _store >> (i * 4) & 0xf; }
void elem(uint i, uint value)
{
i *= 4;
_store &= ~((uint64)0xf << i);
_store |= (uint64)value << i;
}
void swap(uint i1, uint i2)
{
uint temp = elem(i1);
elem(i1, elem(i2));
elem(i2, temp);
}
void reverse(uint i1, uint i2)
{
while (i1 < i2) swap(i1++, --i2);
}
};
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;
}
}
}
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;
}
int main()
{
Set16 set;
unsigned n = 0;
do {
#if 1
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;
}
Output:
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
6 permutations found.
Life demo on ideone
So, here I am: permutations without arrays.
Finally, another idea hit me. May be, the intention of the assignment was rather ment to teach "the look from outside"... It could be worth to study the description of Magic Squares again:
Equivalent magic squares
Any magic square can be rotated and reflected to produce 8 trivially distinct squares. In magic square theory, all of these are generally deemed equivalent and the eight such squares are said to make up a single equivalence class.
Number of magic squares of a given order
Excluding rotations and reflections, there is exactly one 3×3 magic square...
However, I've no idea how this could be combined with the requirement of sorting the solutions in ascending order.
