Not A Magic Square But Similar

[Limbic~Region]

All,
A magic square is an NxN square filled with distinct integers where all columns, rows and diagonals add up to the same value. Here is an example 3x3:

4 3 8
9 5 1
2 7 6

What I am trying to create has similar properties (all selections add up to the same value). A selection is defined where N numbers are chosen from the square such that each column and row may only have 1 number selected from it. Here are the possible choices for a 3x3.

SQUARE

A B C
D E F
G H I

SELECTIONS (order is not important)
A E I
A H F
D B I
D H C
G B F
G E C

This would be trivial if there wasn't a requirement for distinct values (making all values 1 for instance would suffice). Making a 2x2 is also trivial.

3 9
1 7

3 + 7 = 10
1 + 9 = 10

Ultimately, I would like squares for N=3, N=4, N=5 and possibly N=6. It doesn't matter what sum the selections add up to provided that each value is a distinct integer. Can you do it?

[LanX]

I'm not sure if you want some Perl number crunching or a mathematical approach...

The 3² square is actually a finite affine plane of order 3

Your "selections" are nothing else then the parallels of the diagonals¹. That means resorting the rows and columns of any magical square is also a solution for your problem.

As a proof of concept:

 magical square
4 3 8
9 5 1
2 7 6

mapping rows and columns to diagonals

 derived solution
4 1 7
6 3 9
5 2 8

I.a.W.: You can reuse any known algorithm for magic squares.

Nota Bene: your problem class is not equivalent but even more general (i.e. simpler) b/c the "diagonal"-requirement is missing (i.e. 2-5-8 and 4-6-5 summing up to 15 isn't needed)

HTH

UPDATE

¹) in the case 3x3

[kennethk]

For the 3² square, you are correct; we have 6 constraints, as opposed to the magic square's 8 (or really 5 as opposed to 7, given arbitrary normalization). However, for 4², we have 24 constraints as opposed to a magic square's 10; in general, constraint count grows factorially as opposed to the magic square's linear. Of course, I'm out of my depth w.r.t. geometry here, so maybe there's another mapping I'm missing.

[LanX]

Nope I was too lazy to update the cases of non-parallel "sections"¹, only mentioned it in reply to hdb (whose solution makes mine obsolete).

But I think that hdb's solution resp. your generalization already describe the complete solution room and that all possible magic square can be found there by mapping rows to diagonals.

So since the other way round works you will always find a back-projection from magic to "limbic" square.

Too tired to dig into proving it, but looking into the literature for magic squares should show it's trivial.

(unproven opinion)

update

¹) and I'm still not sure if L~R really wants them.

[hdb]

1 2
3 4

1 2 3
4 5 6
7 8 9

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

etc

[kennethk]

Also:

1 2 3
4 5 6
8 9 10

1 2 3
5 6 7
9 10 11

1 2 4
5 6 8
9 10 12

Any additive offset to a row or column from a valid state that doesn't cause a value collision also satisfies the permutation condition.

3 6 9
2 5 8
1 4 7

1 2 3
7 8 9
4 5 6

2 1 3
5 4 6
8 7 9

Rotations, row swaps and column swaps also yield valid results. Of course, these are actually a subset of the additive transformation. If you think about it, the 1 .. 9 square is just the all 1's square subjected to 9 row additions and 3 column additions; the minimum necessary number to achieve element uniqueness.

The real question for me is are there valid results which are not mappable via addition to the base square.

[Limbic~Region]

kennethk,
The real question for me is are there valid results which are not mappable via addition to the base square

Yes and I am kicking myself for not including this in the list of trivial cases I had considered (as this is not my intent). In any event, if I had to make this work I could but I isn't what I was hoping for.

[LanX]

Best solution so far! hdb++

Works also always¹ for "selections" which are not parallels of a diagonal, like 1-10-7-16.

¹) prove left for interested readers.

[Laurent_R]

I built a Sudoku puzzle solver and builder a few years back, at the time when it became popular. Generating all possible combinations is quite simple, the difficulty lies in modeling simply the way to list the rules that make some authorized (or others forbidden). I think that an approach similar to the eight queens problem on a chess board should probably work. Interesting challenge, it is just a pity I don't have enough time to try anything before at least a few hours, possibly nor before tomorrow.

[Anonymous Monk]

GNU Prolog (gprolog)

[Anonymous Monk]

GNU Prolog (gprolog)

Is that an answer to some question the OP asked?

[Limbic~Region]

Anonymous Monk,
No, but it isn't entirely a bad answer either. Prolog is a constraint driven paradigm. It is probably better suited to this task then Perl is. On the other hand, I was looking for an algorithm not a language.