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
[download]

mapping rows and columns to diagonals

 derived solution
4 1 7
6 3 9
5 2 8
[download]

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

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.

---

#11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

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)

Cheers Rolf

( addicted to the Perl Programming Language)

update

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

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
[download]

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
[download]

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
[download]

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.

---

#11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

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.

Cheers - L~R

Best solution so far! hdb++

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

Cheers Rolf

( addicted to the Perl Programming Language)

¹) prove left for interested readers.

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.

GNU Prolog (gprolog)

Is that an answer to some question the OP asked?

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.

Cheers - L~R