Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Magic Squares Guessing

by walkingthecow (Friar)
on Nov 03, 2011 at 03:00 UTC ( #935568=perlquestion: print w/ replies, xml ) Need Help??
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?

Comment on Magic Squares Guessing
Re: Magic Squares Guessing
by Ratazong (Prior) 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 (Chaplain) on Nov 03, 2011 at 10:44 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://935568]
Approved by ww
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (11)
As of 2014-07-22 11:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (110 votes), past polls