It generates the 7040 solutions in 1-2 minutes (61 seconds on my machine, but it is a relatively new one). If sum(attempt for i in range(0,4)) != 34:įor p in itertools.permutations(rest,3-pos):īase=34-sum( for i in range(0,pos+1)])įor p in itertools.permutations(rest,2-pos): If sum(attempt for j in range(0,4)) != 34: However if you generate a column after having a row in place, you are dealing with a 2-element permutation only (because the first element is known and the last one is calculated).Įxample implementation (without pre-generation): import itertools,time One may pre-generate/filter all the individual permutations having the sum of 34, and pick candidates based on what is already there in the square.Īnother trick is connected to this one: if you always generate rows, you always try a lot of things, 3+1 brand new elements. In fact the first two element can already create an upper/lower limit for the remaining ones, for example 1,2 means that the remaining two elements will be 15 and 16. If such element never existed (like 1,2,3,28), or is already in use (like 1,3,15,15), that attempt will not work and you can proceed to the next one without generating the rest of the table. ![]() For example you never need to generate a 4-element permutation, because you know that their sum is 34, thus the 4th element even in the first row has to be 34-sum(first 3 elements). The trick is to depend on already generated cells. I ultimately would like to speed this up by excluding unnecessary permutations. When removing the "isMagic" check, which simply prints all combinations, including those that arent "magic", it takes a painfully long time for the function to print the squares. # this is where I imagine the exceptions would be made For example, I want it so that if the first row of the matrix doesn't sum up to 34, skip that permutation and proceed to the next one (and so on and so forth for the proceeding rows). ![]() I'm not sure how to implement a check in the recursive call to optimize it though. This function takes a length 16 array, which is representative of the square, and prints all possible combinations that fit the "magic" criteria. I already have the recursive algorithm to permute all combinations. I'm attempting to optimize my permutation algorithm, which currently lists all possible 4 x 4 matrices using digits ranging from 1-16, to skip over certain permutations if the current matrix doesn't match the magic square criteria. For 4 x 4 magic squares, that constant is 34. A "magic square" consists of an n x n matrix where the rows, columns, and diagonals all equal a constant.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |