http://www.perlmonks.org?node_id=935568

walkingthecow has asked for the wisdom of the Perl Monks concerning the following question:

I would provide some example code, but not even sure where to start on this one. I have a 7x7 magic square with random numbers filled in, and I have to fill in the numbers that are empty (my daughter's 3rd grade math homework got me on this). So, on line one I have 22, blank space, 30, blank space, 38, 21, 46. On line 2 I have 47, 23, blank space, 31, blank space, 39, blank space. Now, each line needs to equal 175, both down and across. I know that 20 numbers are missing (1 through 20), and that each number can only be used once. For fun, I've been trying to figure out the best way to script this, but my brain is not cooperating with me. Any suggestions on where to start with this?

Replies are listed 'Best First'.
Re: Magic Squares Guessing
by Ratazong (Monsignor) on Nov 03, 2011 at 07:49 UTC

I would create a data-structure consisting of

• a partly filled square
• the list of numbers you need to place

Then you could use a recursive algorithm like the following:

1. select an element from the number-list (*)
2. select an empty position
3. place the element at the position
4. check, if the square is still consistent (all completely filled lines sum up to 175)
• if yes, repeat the step with the new square and the reduced number-list
• if no, restore the previous state (of number-list and square) and try with the next number and/or position
If the number-list is empty in step 1, you have found a solution.

Once you have your basic algorithm, you can optimize. E.g. your selection-algorithms and your consistency-checks. That's when the real fun starts :-) (because you can add "intelligence" instead of pure "brute-force")

Hope this helps! Rata

(*) a basic selection-algorithm could be going from first to last.

Re: Magic Squares Guessing
by JavaFan (Canon) on Nov 03, 2011 at 10:14 UTC
What I would do:
1. If no open squares remain, you're done.
2. If there's an open square that is the only open square in its row or column, goto 3. Else, goto 4.
3. Pick an open square that is the only open square in its row or column. Calculate what the value should be. If the value is invalid (used already, greater than 20, less than 1, or different for the row and columns), return (from recursion, or overall -- in the latter case, it's unsolvable). If it's valid, fill in. Goto 1.
4. Find a row or a column with the least number of open squares (but one that still has open squares). Pick one of its open squares. For each unused value 1 .. 20 try filling it in in the open square. Recurse.
Re: Magic Squares Guessing
by spx2 (Deacon) on Nov 03, 2011 at 10:44 UTC