How to make a 3x3 matrix that represents weather or not a box on a sudoku board (9x9 matrix) contain-CodePudding

I am creating a Sudoku bot in python and I need to create a 3x3 matrix where each value represents a box on the board. The value will be False if there is an instance of value in the box and True if not.

Currently I have

temp_board = ma.masked_where(board == value, board, True)
boxes = np.full((3, 3), False)
for x in range(3):
    for y in range(3):
        boxes[x, y] = not np.any(temp_board.mask[x * 3:(x   1) * 3, y * 3:(y   1) * 3])

board is a 9x9 matrix containing numbers 0-9 but value can only equal 1-9

Here is an example of what the output should look like

# input
board = np.array([[4, 0, 9, 0, 7, 2, 0, 1, 3],
                  [7, 0, 2, 8, 3, 0, 6, 0, 0],
                  [0, 1, 6, 0, 4, 9, 8, 7, 0],
                  [2, 0, 0, 1, 0, 0, 0, 6, 0],
                  [5, 4, 7, 0, 0, 0, 2, 0, 0],
                  [6, 9, 0, 0, 0, 4, 0, 3, 5],
                  [8, 0, 3, 4, 0, 0, 0, 0, 6],
                  [0, 0, 0, 0, 0, 3, 1, 0, 0],
                  [0, 6, 0, 9, 0, 0, 0, 4, 0]])
value = 9
# output

[[False False  True]
 [False  True  True]
 [ True False  True]]

The method I am using works but is terribly inefficient, I was wondering if there was a faster way to do this.

CodePudding user response：

One way, not very subtle, but fast, would be to have a lookup index table

look=np.zeros((9,9,9), dtype=bool)
look[0,:3,:3]=True
look[1,:3,3:6]=True
look[2,:3,6:]=True
look[3,3:6,:3]=True
look[4,3:6,3:6]=True
look[5,3:6,6:]=True
look[6,6:,:3]=True
look[7,6:,3:6]=True
look[8,6:,6:]=True

def inblock(board, blnum, val):
    return val in board[look[blnum]]

To get directly you matrix, you can then

~(look*board == value).any(axis=(1,2)).reshape(3,3)

look*board is a 9x9x9 matrix, filtering only one block each ((look*board)[k] contains 0 everywhere, but in block k, which are a copy of the board).

(look*board == value) is a boolean version of that.

so (look*board == value).any(axis=(1,2)) are 9 values, True iff block[k] contains value.

Since I use a 1 dimension block array, you can reshape to get 3x3 matrix.

And then negate the result to imitate your output.

Note that there are surely more subtle ways to build the look table. For example, using your own for loop, slightly modified. But well, that in only one time.

Alternative

Just to be even more direct (and, frankly, what I was looking for, when I started to think to your question), would be this

look=np.zeros((3,3,9,9), dtype=bool)
for i in range(3):
    for j in range(3):
        look[i,j,i*3:(i 1)*3,j*3:(j 1)*3] = True

~np.einsum('ijkl,kl', look, board==value)

The fact that I use (3,3,9,9) shape and then avoid reshape is not really the point (it is the same cost, just a presentation problem). I could have done that for the previous solution.

Nor is the fact that this time, I use a double loop to create the look table. That again, I could have done it before. It is not look that changes. Just the usage of einsum. It is not better than my previous solution. But it is what I had in mind at first: use a sort of matrix multiplication.

Timings

~(look*board == value).any(axis=(2,3)) : 18.9 μs (Note this is my previous solution, adapted to (3,3,9,9) shape

~np.einsum('ijkl,kl', look, board==value) : 13.6 μs

So, my second solution is not only the one I wanted. But it appears it is also faster.