Search code examples
algorithmbrute-forcemagic-square

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


Solution

  • 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.