CODEWITHSUNDEEP
python
ljd03
ljd03

Reputation: 63

Backtracking to create squares

a = []
def make_squares(arr, length, nums):
    if not nums:
        print(arr)
        a.append(arr)
        return
    r = 0
    while r < len(arr) and len(arr[r]) == length:
        r += 1
    for i in nums:
        nums.remove(i)
        arr[r].append(i)
        make_squares(arr, length, nums)
        nums.append(i)
        arr[r] = arr[r][:-1]
make_squares([[] for i in range(3)], 3, [i+1 for i in range(3**2)])
print(a)

I'm trying to use the above code to create nxn matrices each with a permutation of the numbers i+1...n^2. I have printed every matrix that gets appended to a and they appear correct, but when I print a in the end, I get [[[], [], []], [[], [], []], ...]. It doesn't make any sense to me.

The expected result would be

[[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [4, 5, 6], [7, 9, 8]], ...]

Upvotes: 1

Views: 38

Answers (1)

AKX
AKX

Reputation: 169416

The order may not be the same as in your expected result, but this does the trick with the standard library itertools module:

import itertools

def make_squares(w):
    size = w * w
    for perm in itertools.permutations(range(1, size + 1)):
        # "grouper" from the itertools recipe list
        yield list(itertools.zip_longest(*[iter(perm)] * w))

for square in make_squares(3):
    print(square)

prints

[(1, 2, 3), (4, 5, 6), (7, 8, 9)]
[(1, 2, 3), (4, 5, 6), (7, 9, 8)]
[(1, 2, 3), (4, 5, 6), (8, 7, 9)]
[(1, 2, 3), (4, 5, 6), (8, 9, 7)]
[(1, 2, 3), (4, 5, 6), (9, 7, 8)]
[(1, 2, 3), (4, 5, 6), (9, 8, 7)]
[(1, 2, 3), (4, 5, 7), (6, 8, 9)]
[(1, 2, 3), (4, 5, 7), (6, 9, 8)]
[(1, 2, 3), (4, 5, 7), (8, 6, 9)]
[(1, 2, 3), (4, 5, 7), (8, 9, 6)]
[(1, 2, 3), (4, 5, 7), (9, 6, 8)]
[(1, 2, 3), (4, 5, 7), (9, 8, 6)]
[(1, 2, 3), (4, 5, 8), (6, 7, 9)]
[(1, 2, 3), (4, 5, 8), (6, 9, 7)]
[(1, 2, 3), (4, 5, 8), (7, 6, 9)]
...

Upvotes: 1

Related Questions