CODEWITHSUNDEEP
c#algorithmmagic-square
user3193861
user3193861

Reputation: 43

Magic square brute force algorithm

Basically for an assignment I need to create a C# program that will take a number as input (n) then create a 2D array size n*n with the numbers 1 to (n*n). It needs to use a brute force method. I have done this but at the moment the program will just randomly generate the order of the numbers each time, so it will sometimes check the same order more than once. Obviously this means it takes a really long time to check any number above 3, and even for 3 it can take a few minutes. Basically I'm wondering if there is any way for me to make it only check each order once. I am only allowed to use "basic" C# functions, so just things like *, /, +, - and nothing like .Shuffle etc.

Upvotes: 1

Views: 2158

Answers (2)

Eric Lippert
Eric Lippert

Reputation: 659994

Let me make sure I understand the question: you wish to enumerate all permutations of the numbers 1 through n squared, and check whether the permutation produces a magic square. You are now generating permutations randomly, but instead you wish to generate all permutations.

I wrote a series of articles on generating permutations; it is too long to easily summarize here.

http://ericlippert.com/2013/04/15/producing-permutations-part-one/

Upvotes: 3

Mzf
Mzf

Reputation: 5260

Choosing random order, as you found, is not a good idea.

I suggest that you put all the number 1 ... (n*n) in array , and than find all the permutation.

when you have all the permutation, it's easy to create square (1 .. n ==> the first row, n+1 ... 2n ==> the second row and so on).

Now, finding all the permutation can be done with the basic operation with recursion

Upvotes: 1

Related Questions