CODEWITHSUNDEEP
algorithmbrute-forcemagic-square
foo
foo

Reputation: 2311

Brute force magic squares

Basically I have a 3 x 3 grid that is filled with two digit numbers 00 - 99. Some of the numbers are given as input the rest are unknown. What are some suggestions on how to solve such a problem with brute force in C?

EDIT: Sorry I forgot part of the problem. Every row and column and diagonal must add up to the same number. I don't want any code just some ideas to get started with algorithm

Upvotes: 3

Views: 5410

Answers (5)

Donal Fellows
Donal Fellows

Reputation: 137567

Magic squares are really a system of (simple) simultaneous equations. You solve those by converting into a matrix and using Gaussian elimination, which is brute force but reasonably elegant at the same time. If the solution is not unique, you'll at least a reduced set of constraints on what the solution can be, which should make doing the solution much simpler.

Upvotes: 4

Jim Balter
Jim Balter

Reputation: 16406

There is a simple recursive solution to your problem, which is an example of a type of brute force called backtracking (google that).

The recursive function (say, fill_next) finds the next cell with unknown value. If there is no such cell, it checks the square to see if it fits the requirements (the sums are correct) and if so prints the square as a solution; it then returns. If there is a cell with an unknown value, it loops, trying each of the values 0 to 99 in turn for that cell then calling itself recursively to fill in the next unknown cell.

How to get to the next cell with unknown value: you can simply pass to find_next the number of the next cell to start looking at; you would start the whole thing off by calling fill_next(0). The cell number is 0 through 8 since you have 9 cells. If you are storing the square in a 2D array, just use num%3 and num/3 as the indices.

This would be much easier to describe by just giving you the few lines of code it takes, but you said you don't want that.

Upvotes: 4

Girish Rao
Girish Rao

Reputation: 2669

Brute force for magic square problem is pretty straightforward.

  1. Iterate over each row and compute sum for each row (keep i constant, j++) (3 sums)
  2. Iterate over each column and compute sum for each column(keep j constant, i++) (3 sums)
  3. Iterate over both diagonals and compute sum (i++, j++, such that i equals j) (2 sums)

If sum is not the same as the first sum you compute at any point, then you're done. If all sums are equal, then you've found the magic square.

Upvotes: 0

Christian
Christian

Reputation: 28125

A 3x3 grid sounds like a 2d array.

Some example code in JS:

var a=[
    [ 11, 12, 13 ],
    [ 21, 22, 23 ],
    [ 31, 32, 33 ]
];
for(var r=0; r<a.length; r++)
    for(var c=0; c<a[r].length; c++)
        console.log(r+','+c+' = '+a[r]+','+a[r][c]);

a - the 3x3 grid array (array of arrays) r - current row iteration c - current column iteration

Optionally, a.length and a[r].length can both be constants of 3 (in your case).

Upvotes: 0

invisible bob
invisible bob

Reputation: 864

What is your problem? Are you trying to find out what each number is? is their any criteria that the numbers have to meet? If so, just guess each possible number in each ?? spot until a combination fits the criteria.

Upvotes: 1

Related Questions