Python 9x9 and 3x3 array validation excluding 0-CodePudding

I am trying to validate if any numbers are duplicates in a 9x9 array however need to exclude all 0 as they are the once I will solve later. I have a 9x9 array and would like to validate if there are any duplicates in the rows and columns however excluding all 0 from the check only numbers from 1 to 9 only. The input array as example would be:

[[1 0 0 7 0 0 0 0 0]
 [0 3 2 0 0 0 0 0 0]
 [0 0 0 6 0 0 0 0 0]
 [0 8 0 0 0 2 0 7 0]
 [5 0 7 0 0 1 0 0 0]
 [0 0 0 0 0 3 6 1 0]
 [7 0 0 0 0 0 2 0 9]
 [0 0 0 0 5 0 0 0 0]
 [3 0 0 0 0 4 0 0 5]]

Here is where I am currently with my code for this:

#Checking Columns
for c in range(9):
    line = (test[:,c])
    print(np.unique(line).shape == line.shape)

#Checking Rows
for r in range(9):
    line = (test[r,:])
    print(np.unique(line).shape == line.shape)

Then I would like to do the exact same for the 3x3 sub arrays in the 9x9 array. Again I need to somehow exclude the 0 from the check. Here is the code I currently have:

for r0 in range(3,9,3):
    for c0 in range(3,9,3):
        test1 = test[:r0,:c0]
        for r in range(3):
            line = (test1[r,:])
            print(np.unique(line).shape == line.shape)
        for c in range(3):
            line = (test1[:,c])
            print(np.unique(line).shape == line.shape)
``
I would truly appreciate assistance in this regard.

CodePudding user response：

It sure sounds like you're trying to verify the input of a Sudoku board.

You can extract a box as:

for r0 in range(0, 9, 3):
    for c0 in range(0, 9, 3):
       box = test1[r0:r0 3, c0:c0 3]
       ... test that np.unique(box) has 9 elements...

Note that this is only about how to extract the elements of the box. You still haven't done anything about removing the zeros, here or on the rows and columns.

Given a box/row/column, you then want something like:

   nonzeros = [x for x in box.flatten() if x != 0]
   assert len(nonzeros) == len(set(nonzeros))

There may be a more numpy-friendly way to do this, but this should be fast enough.

CodePudding user response：

Excluding zeros is fairly straight forward by masking the array

test = np.array(test)
non_zero_mask = (test != 0)

At this point you can either check the whole matrix for uniqueness

np.unique(test[non_zero_mask])

or you can do it for individual rows/columns

non_zero_row_0 = test[0, non_zero_mask[0]]
unique_0 = np.unique(non_zero_row_0)

You can add the logic above into a loop to get the behavior you want

As for the 3x3 subarrays, you can loop through them as you did in your example.

CodePudding user response：

When you have a small collection of things (small being <=64 or 128, depending on architecture), you can turn it into a set using bits. So for example:

bits = ((2**board) >> 1).astype(np.uint16)

Notice that you have to use right shift after the fact rather than pre-subtracting 1 from board to cleanly handle zeros.

You can now compute three types of sets. Each set is the bitwise OR of bits in a particular arrangement. For this example, you can use sum just the same:

rows = bits.sum(axis=1)
cols = bits.sum(axis=0)
blocks = bits.reshape(3, 3, 3, 3).sum(axis=(1, 3))

Now all you have to do is compare the bit counts of each number to the number of non-zero elements. They will be equal if and only if there are no duplicates. Duplicates will cause the bit count to be smaller.

There are pretty efficient algorithms for counting bits, especially for something as small as a uint16. Here is an example: How to count the number of set bits in a 32-bit integer?. I've adapted it for the smaller size and numpy here:

 def count_bits16(arr):
     count = arr - ((arr >> 1) & 0x5555)
     count = (count & 0x3333)   ((count >> 2) & 0x3333)
     return (count * 0x0101) >> 8

This is the count of unique elements for each of the configurations. You need to compare it to the number of non-zero elements. The following boolean will tell you if the board is valid:

count_bits16(rows) == np.count_nonzero(board, axis=1) and \
    count_bits16(cols) == np.count_nonzero(board, axis=0) and \
    count_bits16(blocks) == np.count_nonzero(board.reshape(3, 3, 3, 3), axis=(1, 3))