[Shane75776]

I am supposed to come up with a recursive backtracking algorithm to build a 3x3 magic square. Currently I am quite lost I have tried a few approaches but feel like I am over complicating something that should be fairly easy.

We are given the algorithm, yet i'm still kinda lost on it.

recursive_funtion(position) {
 	for number from 1 to 9, not used elsewhere already {
 		put this number on this position, make it unavailable
 		if solution valid {
 			if solution complete {
  				done, show solution
  			}else{
  				recursive_function(next_position)
 			}
 		}
 		(make this space blank again, and the number available)
 		}
}

I have a hard time understanding from text for some reason, but if I am given code examples to look at I can easily understand whats going on and pick up on it that way.

Any help is appreciated. Thanks.

[GregBrannon]

We'll help you with your possibly overcomplicated approaches. Show what you've tried.

If you haven't already, you could start by coding the above pseudo-code.

[Shane75776]

GregBrannon, on 17 April 2012 - 01:32 PM, said:

We'll help you with your possibly overcomplicated approaches. Show what you've tried.

If you haven't already, you could start by coding the above pseudo-code.

This is what I have done thus far, and a few other attempts but I know its completely wrong and it seems like I am just not understanding the pseudo-code correctly.

int[][] square = new int[3][3];
	ArrayList<Integer> used_nums = new ArrayList<Integer>();
	
	
	public MagicSquare()
	{
		rec_backtrack(0);
		print_square();
	}
	public void rec_backtrack(int level)
	{
		int step = 0;
		for(int i = 1; i < 10; i++)
		{
			if(!used_nums.contains(i))
			{
				square[step][level] = i;
				used_nums.add(i);
				step++;
			}
			if(step == 3) //we have inserted to all 3 spots now, check for solution
			{
				if((square[0][level] + square[1][level] + square[2][level]) == 15) //acceptable solution
				{
					rec_backtrack(level++);
				}
				else
				{
					step--;
				}
			}
		}
	}

[GregBrannon]

Do you know or can you use sets yet?

[Shane75776]

GregBrannon, on 17 April 2012 - 01:36 PM, said:

Do you know or can you use sets yet?

We have not done anything with sets yet. All we were told was that this should be a fairly simple recursive method with the given pseudo-code. I'm just not seeing it or something. I feel kinda stupid because I have done more complicated things than this before. Yet I can't seem to wrap my head around it.

[Shane75776]

Can anyone possibly help me to get started on this. I'm still very much lost. I have done a ton of googling and have not turned up anything helpful.

Thanks.

[GregBrannon]

There's more to this problem that the pseudocode doesn't adequately cover. The pseudocode is a reasonable description of a generalized backtracking algorithm:

Try something
  if it works: keep it;
     if done, stop (return);
     if not done, move to next problem (recursive call);
  if it doesn't work: discard it, and try something else;

What the pseudocode doesn't do is define the assumptions, any initial conditions, backtracking beyond a previous solution, what to do if there is no solution found, etc. Those come from analytical thought by the programmer. Here's an example of how someone else thought through the problem:

The Magic Squares problem requires more thought and some tailoring of the pseudocode you were given. This is a good starting discussion of the whole problem.

Here's how I thought through the problem:

The Magic Square has 8 quantities that must sum to 15: the 3 horizontal rows, the 3 vertical columns, and the 2 major diagonals.
Using the 9 possible numbers, 1 - 9, there are 8 unique 3-number combinations that sum to 15.
One square of the Magic Square (the center) is contained in 4 of the sums (at a time), 4 squares each (the corners) are in 3 sums, and 4 squares each (the remaining) are in 2 sums.
Of the 8 unique, 3-number combinations, only the number 5 is common to 4 of them.

From the above, the number 5 must be in the center square. Similarly, by defining the numbers common to 3 and then 2 of the possible combinations, the possible numbers for the corner and remaining squares can be identified. Knowing the possible solutions (or the impossible ones) significantly reduces the solution set.

How does that help you?
5 in the center square is a given.
Determining the numbers for each corner square requires examining 3 sums, but there are only 4 numbers to consider.
Determining the numbers for each remaining square requires examining 2 sums, but there are only 4 numbers to consider.

Using a tailored backtracking concept and the 'facts' above, you can find a solution in relatively few attempts, because 1) there aren't that many possiblities to consider, and 2) there aren't that many solutions.

I think the hardest part is deciding how to begin. Do you fill the squares (except for the center) randomly and work from there? Or do you fill the center square with 5, each of the corners with one of the 4 possible numbers, and then the remaining squares with each of those 4 possible numbers? I think the latter is a reasonable starting point. There may be a better one.

Note that it'll help to tailor the pseudocode to consider only the possible numbers for the square you're working. It won't be 1 of the total 9 numbers but 1 of the possible 4 numbers.

So, as I said, this problem is more complicated than the pseudocode suggests, but with a little thought and tailoring of the psuedocode, a reasonable solution can be found.

Good luck! Let me know if you have any questions.