Brute force magic squares

Question

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

Answer 1

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.

Answer 2

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.