2

I need generate a matrix and fill with numbers and inactive cells, but that the sum of each columns or rows are equal. I know the magic box and sudoku, but is different. Can you help me please? What kind algorithm I need use for generate this matrix?

E.g

X = 0 = block inactive

  Matrix ( 4x4 )

   0  8  4  X  | 12
   2  0  8  2  | 12
  10  1  X  1  | 12
   0  3  X  9  | 12
   ____________| 
  12 12 12 12

Other example:

  Matrix ( 5x5 )      

  0  2  2  3  5 | 12
  2  4  0  5  1 | 12
  8  2  0  2  0 | 12
  0  4  2  0  6 | 12
  2  0  8  2  0 | 12
  ______________|
  12 12 12 12 12

The result can be any other number, it is not always 12. Just as in Example I was easier to do for me. It's not be symmetrical. Note: This is not magic box, also is not sudoku.

Conclusion:

1) I need build this box and fill with number and block inactive.

2) Always matrix is square(3x3, 4x4, 5x5, NxN, ...)

3) When I fill of space is not block, I can use number one, two or three digits.

4) The sum of all sides must be equal.

5) In the above example, X is block. Block mean not use for player.

6) you can inactive block can be 0, however does not affect the sum.

7) There is also no restriction on how many blocks or inactive will have no

8) To fill cells with numbers, this can be repeated if you want. There is not restriction.

9) The matrix is ​​always a square and may be of different dimensions. (2)

Thanks guys for your help. And sorry that the problem is incomplete and for my english is too bad, but that's all.

rkv
  • 118
  • 2
  • 13
  • 1
    See also: [Magic Square Program (C++)](http://stackoverflow.com/questions/4372554/magic-square-program-c) and [C - 2D Array - Magic Square order 4](http://stackoverflow.com/questions/13176801/c-2d-array-magic-square-order-4) – Ilya Jul 24 '14 at 09:13
  • 1
    I've never studied this but my starting point would be to recast the problem as a linear algebra problem (matrix algebra) and go from there. – Bathsheba Jul 24 '14 at 09:15
  • If the dimension of the square is small, you can use backtrack – Fallen Jul 24 '14 at 09:26
  • What are your contrainsts? – user189 Jul 24 '14 at 09:32
  • What do you exactly need to do? Do you need to solve this kind of matrix (having the inactive cells fixed or to be determined?) or to create it to be after solved by people? In this latter case what are the output given? (sum value and specific X positions?) – Diego Mazzaro Jul 24 '14 at 09:32
  • Backtract? Did not seek backtract possible solutions? This Box I need build with number block and inactive. Thanks you for you reply. – rkv Jul 24 '14 at 09:33
  • How about an empty matrix or a matrix with all elements equal? – Abhishek Bansal Jul 24 '14 at 09:34
  • Sorry I didn't understand the problem before. Okay so the right questions are: 1) Is an `X` cell any different from putting a `0` in the cell? (I mean, could there be an active cell which value is `0`?) 2) The number that each row and column must sum, is given, or can be any as long as every sum is the same? 3) Is there any restriction about the amount of inactive cells you can put? – jdehesa Jul 24 '14 at 09:41
  • Could you use zero for the inactive blocks or is zero a valid active value? – olivecoder Jul 24 '14 at 09:42
  • 1) you can inactive block can be 0, however does not affect the sum. 2) There is also no restriction on how many blocks or inactive will have no – rkv Jul 24 '14 at 09:44
  • The problem description is incomplete. It allows trivial solutions as other users say. Do the numbers need to be different? Does the matrix have to be random in some sense? – Jakub Jul 24 '14 at 10:43

2 Answers2

3

In terms of agorithms, I would approach it as a system of linear equations. You can put the box as a matrix of variables:

x11 x12 x13 x14
x21 x22 x23 x24
x31 x32 x33 x34
x41 x42 x43 x44

Then you would make the equations as:

row1 = row2  (x11 + x12 + x13 + x14 = x21 + x22 + x23 + x24)
row1 = row3  (...)
row1 = row4
row1 = col1
row1 = col2
row1 = col3
row1 = col4

For N = 4, you would have 16 variables and 7 equations, so you would have a solution with a number of degrees of freedom (at least 9, as pointed out by @JamesMcLeod, and exactly 9, as stated by @Chris), so you could generate every possible matrix satisfying the restrictions just giving values to every free parameter. In the resulting matrix, you could mark every cell with 0 as an inactive cell.

To do this however you would need a library or software package with the ability to solve systems of linear equations with degrees of freedom (several math software packages can do this, but right now only Maple comes to my mind).

PD: I've just read that numbers must have one, two or three digits (and be positive, too?). To address this, you could just "take care" when choosing the values for the free parameters once the system of equations is solved, or you could add inequalities to the problem like:

x11 < 1000
x11 >= 0  (if values must be positive)
x12 < 1000
(...)

But then it would be a linear programming problem. You may approach it like this too.

PD2: You can also make simple cases with diagonal matrices:

7 X X X
X 7 X X
X X 7 X
X X X 7

But I guess you already knew that...

Edit: Thanks James McLeod and Chris for your corrections.

jdehesa
  • 58,456
  • 7
  • 77
  • 121
  • 1
    I make it seven linearly independent equations (r1 = r2, r1 = r3, r1 = r4, r1 = c1, r1 = c2, r1 = c3, r1 = c4) so if I recall correctly, 9 degrees of freedom. – James McLeod Jul 24 '14 at 10:29
  • @JamesMcLeod You are right, I was making more equations because I was including things like r2 = r3, r3 = c2 or c2 = c4, but all of them are redundant. And yes, that would make _at least_ 9 degrees of freedom. – jdehesa Jul 24 '14 at 10:38
  • 16 variables and 7 equations means exactly 9 degrees of freedom doesn't it? – Chris Jul 24 '14 at 10:42
  • @Chris For this problem, maybe it's true (I would need some paper and pen to check it), but in the general case you could have linearly dependent equations. If you have a problem with vars `x1` and `x2` and your equations are `x1 = x2`, `2*x1 = 2*x2` and `3*x1 = 3*x2`, you would still have one degree of freedom, even though you have two variables and three equations. – jdehesa Jul 24 '14 at 10:45
  • 1
    True. But in this case they are guaranteed linearly independent due to the nature of their formation. – Chris Jul 24 '14 at 10:49
  • @Chris I didn't check, but I'll take your word for it and edit the solution, then :) – jdehesa Jul 24 '14 at 10:52
  • 1
    +1 for the bit on range restrictions; if this is supposed to work on some subset of the naturals, then it gets far trickier because they're not a vector space. – G. Bach Jul 24 '14 at 14:22
0

do you fill the matrix with random numbers? You need a function that has an argument as 1 dimension vector which will verify if the sum of the row's elements is 12, then you can still use this function for columns(with a loop) into your main.

sharabarati
  • 21
  • 8