Advanced Formula Challenge #9: One Per Row, One Per Column 8

The challenge this week is as follows: given a 4×4 grid, here in A1:D4, in which each entry is a single-digit integer, and also a target value, here in F2, which is also an integer, though ranging from 1-36, a single formula in G2 to return the number of combinations of four distinct values from that grid whose total is equal to the value in F2, subject to the condition that each of those four values cannot occupy the same row or column as any of the other three.

In the example below, the answer would be 6:

One Per Row, One Per Column

since the following are the only 6 arrangements which meet the conditions outlined above:

One Per Row, One Per Column (2)

Solution next week. Best of luck!

8 comments

  1. Nice puzzle. Here’s an attempt:

    =SUM(N(MMULT(N(OFFSET(A1,MID(Permutations,{1,2,3,4},1)-1,{0,1,2,3})),{1;1;1;1})=F2))

    Permutations:

    ={1234;1243;1324;1342;1423;1432;2134;2143;2314;2341;2413;2431;3124;3142;3214;3241;3412;3421;4123;4132;4213;4231;4312;4321}

    A formula to generate this list in Office 2013 is:

    =MODE.MULT(IF(MMULT(-ISERR(FIND({0,1,2,3},BASE(ROW(1:256)-1,4,4))),{1;1;1;1})={0,0},BASE(ROW(1:256)-1,4)+1111)) 

    In earlier versions the BASE() part could be replaced with:

    BaseArray:

    =TEXT(MMULT(MOD(INT((ROW(1:256)-1)/4^{3,2,1,0}),4),10^{3;2;1;0}),"0000")
  2. Thanks, Lori. Excellent solution! Well done!

    Yes – I was rather hoping that solvers would avoid manually creating a static array as you give for Permutations – not that it’s “cheating”, but this is supposed to be “Advanced” Excel Techniques, after all!

    I will have to upgrade to 2013 as well soon if they have such functions as BASE – looks extremely useful and also a function which, as evident here, will save a lot of prior groundwork in such constructions.

    My only comment might be that, although I did not specify this as a “Shortest Formula Challenge”, and although your MOD/INT construction is generally more to the point and will offer more flexibility for larger datasets, since the problem in hand is restricted to the 4×4 case then there is no great loss in running the FIND over a much larger array, i.e. ROW(INDIRECT(“1234:4321”)). Considerably more resource-hungry (and of course restricted to no more than the analogous 6×6 case), but also less work and certainly more succinct.

    Great work and congratulations once more!

  3. I hadn’t thought of using the range 1234:4321, that would definitely be preferable in versions 2010 and prior to the unweildy final formula i posted. I’d be interested to see your answer next week as well as any other suggestions.

    And yes, my suggestion is a bit quick and dirty. I’d usually try and generalise by substituting the constants with functions ROW, COLUMN, ROWS, etc. But didn’t go further here, partly as the 4×4 case was fixed and i judged it may be clearer to leave it that way for readers. Also the generalised aproach would still only allow up to 7×7 tables (since there are then 7^7 numbers to check.) Striking an appropriate balance between different criteria like brevity, generality, speed and readability is a matter of personal preference in these situations.

  4. Striking an appropriate balance between different criteria like brevity, generality, speed and readability is a matter of personal preference in these situations.”

    Wonderfully put. And yet so many seem to tip that balance to one side or the other to a not inconsiderable degree.

    And here too I tend to agree with you. Although I’ll present the solution, as you did, particular to this 4×4 case, I’ll also mention the necessary constructions for generalizing each of these constants next week – readers may well be familiar with some of them, though perhaps not e.g. the 256, etc. in your BaseArray construction.

    Now what really is a Holy Grail (probably since it’s simply not possible!) is a means by which to generate some of these arrays with the minimum number of “extraneous” elements as possible. Kind of like some sort of optimisation problem in mathematics – perhaps, a bit like the famous sphere-packing problem, we can somehow go one further than this MOD/INT construction by the odd element or two and create the “most efficient” (i.e. least number of non-desired elements) array possible.

    Thanks again and look forward to hearing from you again soon.

  5. Interesting puzzle. I see the number of possible permutations whereby each of the values cannot share a column or rows given by the factorial of n, and that you can identify manually the pattern of permutations by checking a Normal Magic Square (an arrangement of the numbers 1, 2, 3, … n2 in a square array) to confirm that all combinations add to =n*(n^2+1)/2.

    I’ve got no idea whether that is of use here. I wouldn’t in a million years come up with your approach to generate your ‘permutations’ array, Lori.

  6. Hi Jeff and welcome to the site!

    Yes – interesting from a mathematical point of view as well as an Excel one, this.

    The permutation part of it can also be interpreted as the mathematics/chess problem of placing n rooks on an nxn chessboard such that no one rook is attacking any other. There’s some fascinating (and complex) mathematics involved in this book: Across the Board: The Mathematics of Chessboard Problems if you ever come across it.

    And I like your analysis/conclusion re Magic Squares here. I’m not sure if that can help in tackling the issue I outlined re reducing the number of elements in our array of permutations to consider, though it may well do, and it’s certainly a step in the right direction!

    Thanks a lot.

  7. “Quick and dirty” solution for 4×4 in Google Sheets. Seems to work so far XD:

    =ArrayFormula(sum(--(if(iserror(find({1;2;3;4},split(concatenate(if(iserror(find({1;2;3;4},split(concatenate(if({1;2;3;4}{1,2,3,4},{1;2;3;4}&char(9),"")),char(9)))),(split(concatenate(if({1;2;3;4}{1,2,3,4},{1;2;3;4}&char(9),"")),char(9)))&char(9),"")),char(9)))),split(concatenate(if(iserror(find({1;2;3;4},split(concatenate(if({1;2;3;4}{1,2,3,4},{1;2;3;4}&char(9),"")),char(9)))),(split(concatenate(if({1;2;3;4}{1,2,3,4},(A1:A4+transpose(B1:B4))&char(9),"")),char(9))+C1:C4)&char(9),"")),char(9))+D1:D4,"")=F2)))

    Link to spreadsheet: https://docs.google.com/spreadsheets/d/19tTBOBCuDpI7MDYrOd-LZSjZdpHvsvIqrOs4vJ0ARNk/edit#gid=2087298590

  8. =SUM((MMULT(2^INT(MOD((ROW(1:256)-1)/4^{0,1,2,3},4)),{1;1;1;1})=15)*(MMULT(N(OFFSET(A1,MOD((ROW(1:256)-1)/4^{0,1,2,3},4),{0,1,2,3})),{1;1;1;1})=F2))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s