Python 9x9 and 3x3 array validation excluding 0

Question

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.

You can filter line elements, and get the `0`s out, `check_line = [elem for elem in line if elem != 0]` , then use check_line to validate. — Daniel, Sep 19 '21 at 17:30

Frank Yellin · Accepted Answer · 2021-09-19T17:45:15.493

1

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.

edited Sep 19 '21 at 17:45

answered Sep 19 '21 at 17:35

Frank Yellin

9,127
1
12
22

Yes I am trying to verify a Sudoku board, thank you – N K Sep 19 '21 at 17:36
Yes, the exclusion of the zeros is where I am suck, I have no idea how to validate the arrays however just excluding 0 – N K Sep 19 '21 at 17:43
Just added some code. And just corrected that code. – Frank Yellin Sep 19 '21 at 17:43
I actually like the other solution posted by @RafazZ. It is certainly more in the spirit of how to do things with Numpy. (I fixed a small typo in his code.). If you were verifying a 100x100 grid, I'd definitely tell you to rewrite the code that way. For a 9x9 grid, it really doesn't matter. – Frank Yellin Sep 19 '21 at 17:56

score 1 · Answer 2 · edited Sep 19 '21 at 17:54

1

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.

edited Sep 19 '21 at 17:54

Frank Yellin

9,127
1
12
22

answered Sep 19 '21 at 17:35

RafazZ

4,049
2
20
39

If I try to test the unique values I still get false: np.unique(line).shape == line.shape also with the proposed non_zero_mask = (test != 0) – N K Sep 19 '21 at 17:39

score 0 · Answer 3 · answered Sep 19 '21 at 18:24

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))

Python 9x9 and 3x3 array validation excluding 0

3 Answers3