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?
Re: Magic Squares Guessing
by Ratazong (Monsignor) on Nov 03, 2011 at 07:49 UTC

I would create a datastructure consisting of
 a partly filled square
 the list of numbers you need to place
Then you could use a recursive algorithm like the following:
 select an element from the numberlist (*)
 select an empty position
 place the element at the position
 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 numberlist
 if no, restore the previous state (of numberlist and square) and try with the next number and/or position
If the numberlist is empty in step 1, you have found a solution.
Once you have your basic algorithm, you can optimize. E.g. your selectionalgorithms and your consistencychecks.
That's when the real fun starts :) (because you can add "intelligence" instead of pure "bruteforce")
Hope this helps! Rata
(*) a basic selectionalgorithm could be going from first to last.
 [reply] 
Re: Magic Squares Guessing
by JavaFan (Canon) on Nov 03, 2011 at 10:14 UTC

What I would do:
 If no open squares remain, you're done.
 If there's an open square that is the only open square in its row or column, goto 3. Else, goto 4.
 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.
 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.
 [reply] 
Re: Magic Squares Guessing
by spx2 (Deacon) on Nov 03, 2011 at 10:44 UTC

 [reply] 
