CareerCup

this is a very difficult question, if you never have heard of magic squares. You can generate a square using random method and check if it is a magic square. There are ways to construct them: geeksforgeeks.org/magic-square/ or the linked wikipedia article.

Brute force.

#include <vector>
#include <iostream>

using namespace std;

inline bool Check(vector<vector<int>> const &m)
{
	int size = m.size();
	if (size > 0) {
		int sum = numeric_limits<int>::min();
		for (int i = 0; i < size; ++i) {
			int s1 = 0;
			int s2 = 0;
			for (int j = 0; j < size; ++j) {
				s1 += m[i][j];
				s2 += m[j][i];
			}
			if (sum == numeric_limits<int>::min()) {
				sum = s1;
			}
			if (s1 != sum ||
				s2 != sum)
			{
				return false;
			}
		}

		int s1 = 0;
		int s2 = 0;
		int r = 0;
		int c = 0;
		while (r < size &&
				c < size)
		{
			s1 += m[r][c];
			s2 += m[r++][size - 1 - c++];
		}
		if (s1 != sum ||
			s2 != sum)
		{
			return false;
		}

		return true;
	}

	return false;
}

inline bool Next(vector<vector<int>> &m, int max_val)
{
	int r = 0;
	int c = 0;
	while (++m[r][c] > max_val) {
		m[r][c] = 0;
		if (++c >= m.size()) {
			c = 0;
			if (++r >= m.size()) {
				return false;
			}
		}
	}
	return true;
}

void Print(vector<vector<int>> const &m)
{
	for (auto row : m) {
		for (int v : row) {
			cout << v << ", ";
		}
		cout << "\n";
	}
	cout << "-----\n";
}

void ProduceMagicMatrixes(int size, int max_val)
{
	vector<vector<int>> m;
	for (int i = 0; i < size; ++i) {	
		m.push_back(vector<int>());
		m.back().resize(size, 0);
	}
	do {
		if (Check(m)) {
			Print(m);
		}
	} while (Next(m, max_val));
}

int main()
{
	ProduceMagicMatrixes(3, 10);
	return 0;
}

/*
For a matrix N X N where N is odd
take numbers 1.. N^2
Place 1 in the middle column of top row
Next number will go in one of the following positions
-- move up diagonally 1 place and place it here if this is empty
-- OR move 1 place down
Note: all position calculations are mod N
 */
public class MagicMatrix {
    public static void main(String[] args) {
        print(mm(9));
    }

    static int[][] mm(int N) {
        if (N % 2 != 1)
            throw new IllegalArgumentException("argument should be odd integer");
        int result[][] = new int[N][N];
        for (int p = 1, i = 0, j = N / 2; p < N * N + 1; p++) {
            if (p == 1) {
                //start in the middle column of top row
                result[i][j] = p;
            } else {
                // move right and up diagonally
                // and if that position is already full
                // then move down

                if (result[(N + i - 1) % N][(N + j + 1) % N] == 0)
                    result[i = (N + i - 1) % N][j = (N + j + 1) % N] = p;
                else
                    result[i = (i + 1) % N][j] = p;
            }
        }
        return result;
    }

    private static void print(int[][] mm) {
        validate(mm);
        for (int[] x : mm)
            System.out.println(Arrays.toString(x));
    }

    private static void validate(int[][] mm) {
        final int X = mm.length;
        int[] rows = new int[X];
        int[] cols = new int[X];
        for (int i = 0; i < X; i++) {
            rows[i] = 0;
            for (int j = 0; j < X; j++) {
                rows[i] += mm[i][j];
            }
        }
        // System.out.println(Arrays.toString(rows));
        for (int i = 0; i < X; i++) {
            cols[i] = 0;
            for (int j = 0; j < X; j++) {
                cols[i] += mm[j][i];
            }
        }
        //System.out.println(Arrays.toString(cols));
        //TODO: add code for diagonals
        final int tot = rows[0];
        for (int i = 0; i < rows.length; i++) {
            if (tot != rows[i]) throw new IllegalArgumentException("");
        }
        for (int i = 0; i < cols.length; i++) {
            if (tot != cols[i]) throw new IllegalArgumentException("");
        }
        //etc
    }
}

/*
Here is a matrix 9 x 9 with above code 

[47, 58, 69, 80, 1, 12, 23, 34, 45]
[57, 68, 79, 9, 11, 22, 33, 44, 46]
[67, 78, 8, 10, 21, 32, 43, 54, 56]
[77, 7, 18, 20, 31, 42, 53, 55, 66]
[6, 17, 19, 30, 41, 52, 63, 65, 76]
[16, 27, 29, 40, 51, 62, 64, 75, 5]
[26, 28, 39, 50, 61, 72, 74, 4, 15]
[36, 38, 49, 60, 71, 73, 3, 14, 25]
[37, 48, 59, 70, 81, 2, 13, 24, 35]

all rows and cols etc add to 369
 */