Generating unique 2D numpy arrays with 2 adjacent row elements swapped while using BFS in Python

Question

So I have a 12 x 6 2D numpy array for input which consists of 7 possible board objects (characters from 'abcdefg'). From a 2D numpy array I wish to generate all the possible unique 2D arrays, in whose parent array 2 adjacent elements in each row have been swapped. In the worst case this means 60 (5*12) swaps for each parent node. However 2 adjacent elements can be the same, so I omit the duplicate nodes where a swap doesn't generate a unique child array. For instance, given an array (simplified case):

np.array([['a', 'a', 'c'],
          ['d', 'e', 'f'],
          ['g', 'a', 'b']])

I would get the following visited tuples for depth 1 (not in order of swapping cause it's a set):

(('a', 'a', 'c'), ('d', 'e', 'f'), ('a', 'g', 'b'))
(('a', 'a', 'c'), ('d', 'e', 'f'), ('g', 'b', 'a'))
(('a', 'c', 'a'), ('d', 'e', 'f'), ('g', 'a', 'b'))
(('a', 'a', 'c'), ('d', 'e', 'f'), ('g', 'a', 'b')) # parent node
(('a', 'a', 'c'), ('e', 'd', 'f'), ('g', 'a', 'b'))
(('a', 'a', 'c'), ('d', 'f', 'e'), ('g', 'a', 'b'))

The aforementioned function is ran through a breadth-first search function, where given a certain depth, it will find all the unique visited nodes (as a set of tuple of tuples). Since the complexity of BFS is O(b^n), the non unique positions generated would be at least 60^4 (for depth 4), and under a billion for depth 5. For my current implementation depth 4 takes 80-90 seconds, depth 3 is about 2-3 seconds. My goal would be to try and optimize it to 5 seconds max for depth 5, which would be a satisfactory result. Here is the code:

import numpy as np
import time

B = np.array([['a', 'a', 'c', 'a', 'a', 'b'],
              ['d', 'e', 'f', 'a', 'b', 'c'],
              ['a', 'b', 'd', 'd', 'e', 'b'],
              ['b', 'c', 'f', 'd', 'e', 'e'],
              ['a', 'b', 'd', 'b', 'd', 'd'],
              ['b', 'c', 'f', 'f', 'e', 'e'],
              ['d', 'e', 'f', 'g', 'b', 'c'],
              ['d', 'e', 'f', 'a', 'b', 'c'],
              ['a', 'b', 'd', 'b', 'd', 'd'],
              ['b', 'c', 'f', 'f', 'e', 'e'],
              ['d', 'e', 'f', 'a', 'b', 'c'],
              ['d', 'e', 'f', 'a', 'g', 'c']], dtype=object)

def elementswap_getchildren(matrix):

    height, width = matrix.shape

    for i, j in [(i, j) for i in range(height) for j in range(width - 1) if (matrix[i, j] != matrix[i, j + 1])]:

        child = matrix.copy()

        child[i, j], child[i, j + 1] = child[i, j + 1], child[i, j]

        yield child

def bfs(initial, depth):
    visited = set()

    queue = [initial]

    i, j, k, toggle = 0, 0, 0, 0

    while queue:

        node = queue.pop(0)

        node_tuple = tuple(map(tuple, node))

        if node_tuple not in visited:

            visited.add(node_tuple)

            if depth != 0:
                for child in elementswap_getchildren(node):

                    queue.append(child)
                    i += 1

            if toggle == 0:

                k = i
                depth -= 1
                toggle = 1
        j += 1

        if j == k:
            k = i
            if depth != 0:
                depth -= 1

    return visited


start = time.time()
results = bfs(B, 3)
end = time.time()

print('Visited', len(results), 'positions')
print('This took', end - start, 'seconds')

Needles to say, most of the bottleneck is likely from the following areas that I have not been able to find a more optimal solution to:

1. Using for loops instead of a vectorized way to do a, b = b, a but I haven't been able to figure out how to reduce that.
2. Having to use copy() on the argument 2D array for a temporary matrix every iteration of i*j. If I didn't use it inside the inner loop, each child wouldn't be swapping elements in the argument matrix (while keeping the argument matrix unchanged), but swapping elements in their earlier iterations, which is what I don't need.
3. The queue list in the BFS grows very big, about 50000 on depth 3. I'm not accessing it at all during operation, only pop()'ing it. It may be something I cannot implement differently due to it being essential to BFS.

Another thing to point out is, I intend to give each unique board state, that is found before the max depth, a score/value depending on certain combinations of characters present. This will increase overhead, as well as reduce number of branches, because they do not need to be investigated further. But I refrain from complicating this problem before the tree search can't be further optimized.

This is my first time actually coding something this performance/optimization orientated, so I am simply stuck due to inexperience and lack of knowledge in further optimization.

Any help or pointers are welcome, as well as suggesting a completely different approach.

Answer 1

I have not completely thought this through but noticed that the swaps only occur in rows. Could you do this first row-by-row, recording the depth somehow, and then combine these row results with filtering out those with cumulative depth greater than the required depth?