Check if a Sudoku board is filled out correctly

Question

The code below takes a filled out Sudoku board of size NxN, with sub-blocks of nxn, and checks if the solution is correct.

main_function takes a board as input. This function calls check_rows and check_blocks. The first of the two is used to check both the rows and columns of the board. The second one is used to check the nxn sub-blocks.

check_if_all_numbers takes a vector of numbers as input and checks if the vector contains all numbers 1 2 ... n. This function is called by both check_rows and check_blocks

check_rows takes a board as input, loops over each of the rows and checks whether it contains all numbers 1 2 ... n using check_if_all_numbers.

check_blocks takes a board as input, divides it into blocks and checks if each block contains all numbers 1 2 ... n using check_if_all_numbers.

The main_function will stop once it finds an incorrect row, columns or block. For a correct board, the output from the function will look like this:

Function main_function() is called

Checking rows:
All rows are correct
Checking columns:
All columns are correct
Checking blocks:
All blocks are correct

These are the function definitions:

import numpy as np

def main_function(board):
    print('Function main_function() is called\n')
    # If the input is of type "list", convert it to a numpy array
    # Otherwise keep it as it is    
    if type(board) == list:
        board = np.asarray(board)

    print('Checking rows:')        
    rows_are_correct = check_rows(board)

    if not rows_are_correct:
        print('There are incorrect rows on the board')
        return

    else:
        print('All rows are correct')

    print('Checking columns:') 
    # Transpose board and do the same operations as with the columns
    transposed_board = board.transpose()

    cols_are_correct = check_rows(transposed_board)   
    if not cols_are_correct:
        print('There are incorrect columns on the board')
        return
    else:
        print('All columns are correct')  

    # Check if all nxn blocks are correct
    print('Checking blocks:')
    blocks_are_correct = check_blocks(board)
    if not blocks_are_correct:
        print('There are incorrect blocks on the board')
        return
    else:
        print('All blocks are correct')

def check_blocks(board):
    size_of_blocks = int(np.sqrt(board.shape[1]))   # Number of cols/rows in each sub-block   
    indices = np.arange(0,size_of_blocks)           # Create a vector [0,1,..n] that represents
                                                    # the row and columns indices of each block
    is_permutation = True                           # Initialize is_permutation to True
    for x in range(0,size_of_blocks):               # Double loop over rows and columns
        for y in range(0,size_of_blocks):
            rid = indices + y*size_of_blocks        # row index[0,1,..,n] then [0,1]+1*n...
            cid = indices + x*size_of_blocks        # column index
            sub_block = board[np.ix_(rid,cid)]      # Subtract sub-blocks using np.ix_
            flat_block = sub_block.flatten()        # flatten the block and pass
            is_permutation = check_if_all_numbers(flat_block)   # and pass it to check_if_all_numbers
            if not is_permutation:
                return is_permutation                
    return is_permutation

def check_if_all_numbers(numbers):

    all_numbers = np.arange(1,numbers.size+1)   # List of numbers 1-N
    sorted_numbers = np.sort(numbers)           # Sort numbers

    is_permutation = np.array_equal(sorted_numbers, all_numbers) # Check if all numbers are present
    return is_permutation

def check_rows(board):                  # Initialize is_permutation to True
    is_permutation = True
    for n in range(0,board.shape[1]):   # Loop over the rows/columns
        is_permutation = check_if_all_numbers(board[n]) # Check if all numbers are present
        if not is_permutation:
            return is_permutation
    return is_permutation

This is saved as "sudoku_checker.py". I have the following lines in the bottom of the file.

board = [[1,2,3,4],[4,3,1,2],[2,1,4,3],[3,4,2,1]]
main_function(board)

board = [[9,4,2,7,6,1,8,5,3],[3,8,7,5,9,2,6,4,1],[6,1,5,8,3,4,2,9,7], \
[2,6,3,1,4,7,5,8,9],[8,7,1,9,2,5,3,6,4],[4,5,9,3,8,6,1,7,2], \
[7,9,6,2,1,8,4,3,5],[5,2,8,4,7,3,9,1,6],[1,3,4,6,5,9,7,2,8]]
main_function(board)

I'm using Spyder, with Python 2.7. The program is called by simply clicking "Run". To be honest, I don't know how to call if from the command prompt.

How can I improve this code. I'm a beginner in Python and I'm looking for any improvements.

• I've used a lot of Numpy in the code. Would it be better to do this in plain Python, or is Numpy a good choice? If so, how? I tried this at first but failed, and went for Numpy instead.
• Should I have used plain Python and set's instead?
• Is the way I've divided the code into separate functions good?
• What about the indexing in check_blocks?
• Any general tips regarding best practice etc.?

Answer 1

Since you are using numpy, you can take advantage of their extended slicing capabilities to easily extract data. For example, using the following array:

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

You can easily extract a row, a colomn or a block:

>>> array[3, :]
array([7, 1, 8, 2, 9, 3, 4, 5, 6])
>>> array[:, 1]
array([1, 3, 1, 1, 7, 3, 8, 1, 3])
>>> array[:3, :3]
array([[9, 1, 4],
       [5, 3, 2],
       [9, 1, 3]])

You can also convert a block to a line using reshape (either using -1 or the right size):

>>> array[:3, :3].reshape(-1)
array([9, 1, 4, 5, 3, 2, 9, 1, 3])
>>> array[:3, :3].reshape(9)
array([9, 1, 4, 5, 3, 2, 9, 1, 3])

This means that you only need one function to check for a line of data and you can use it on rows, columns or reshaped blocks.

This function should be pretty simple, all you need to do is to ensure that all elements in the line are distincts; or in other words unique. This lead to numpy.unique:

>>> numpy.unique(array[2, :])
array([1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> numpy.unique(array[:, 2])
array([1, 2, 3, 4, 5, 6, 7, 8])

Unfortunately, numpy.unique modifies the original ordering, so you can't have, for instance numpy.unique(array) == array to check if you have the right elements. You can, however, compare the sizes (shapes) of each array:

def is_valid(line):
    return numpy.unique(line).shape == line.shape

All is left to do is providing the right values to this function:

def validate_sudoku(grid):
    board = numpy.asarray(grid)
    size, check_size = board.shape
    assert(size == check_size)

    for i in range(size):
        if not is_valid(board[i, :]):
            print 'Row', i+1, 'is invalid'
            return
        if not is_valid(board[:, i]):
            print 'Column', i+1, 'is invalid'
            return

    block_size = int(size**.5)
    for i in range(size):
        block_row, block_column = divmod(i, block_size)
        block = board[block_row*block_size:(block_row+1)*block_size, block_column*block_size:(block_column+1)*block_size]
        if not is_valid(block.reshape(size)):
            print 'Block', i+1, 'is invalid'
            return

     print 'Board is valid'

Now, as suggested by others, you should not print messages but instead have more advanced control flow to empower the caller. I suggest using exceptions:

def validate_sudoku(grid):
    board = numpy.asarray(grid)
    size, check_size = board.shape
    assert(size == check_size)

    for i in range(size):
        if not is_valid(board[i, :]):
            raise ValueError('Row {} is invalid'.format(i+1))
        if not is_valid(board[:, i]):
            raise ValueError('Column {} is invalid'.format(i+1))

    block_size = int(size**.5)
    for i in range(size):
        block_row, block_column = divmod(i, block_size)
        block = board[block_row*block_size:(block_row+1)*block_size, block_column*block_size:(block_column+1)*block_size]
        if not is_valid(block.reshape(size)):
            raise ValueError('Block {} is invalid'.format(i+1))

You could, of course, define your own exceptions to allow for a better granularity. Usage is like:

try:
    validate_sudoku(my_grid)
except ValueError as e:  # Or whatever custom error
    print(e)
else:
    print('Sudoku is correct')

---

In a comment, @OscarSmith suggest using .flat instead of .reshape(). But since flat is an iterator, you'd have to convert it to an array so is_valid doesn't crash:

if not is_valid(numpy.asarray(block.flat)):
    raise ValueError('Block {} is invalid'.format(i+1))

Answer 2

Some general suggestions first.

You should limit your code lines to 80 characters or less. Practice following the official python style guide, it will make you a better pythonista. For now at least read the parts up through the prescriptive naming conventions.

I'd strongly suggest avoiding numpy since, according to the homepage,

NumPy is the fundamental package for scientific computing with Python.

It is built for efficiency and ease-of-use when working with large numerical data sets. I wouldn't call your data set "numerical" per se, since you aren't doing any arithmetic on the numbers - they just serve as names for the different unique values that can appear in each block. The word for this kind of data is "nominal".

Assuming your board is a list of lists, as in your example data, then your code can be implemented using python builtins as as follows:

# All the logic pulled out of main and put into the checker functions
def main_function(board):
    print('Checking rows:')
    # Remove the boolean variable and just check the function's return
    # Also check the positive condition first to eliminate "not"
    if check_rows(board):
        print('All rows are correct')
    else:
        print('There are incorrect rows on the board')
        return

    print('Checking columns:')
    # Put the transpose operation inside a function called "check_colunms"
    if check_columns(board):
        print('All columns are correct')  
    else:
        print('There are incorrect columns on the board')
        return

    # Check if all nxn blocks are correct
    print('Checking blocks:')
    if check_blocks(board):
        print('All blocks are correct')
    else:
        print('There are incorrect blocks on the board')
        return

# Just a useful helper
def required_nums(board):
    return range(1, len(board[0]) + 1)

def check_rows(board):
    # Check that for all rows on board, all required numbers are present
    return all(all(n in row for n in required_nums(board)) for row in board)

def check_columns(board):
    return check_rows(transpose(board))

# Plagiarized this one right from stackoverflow from a google search for
#   "transpose python 2d list"
def transpose(board):
    return zip(*board)

# Now we want to do the block check logic simply just like the column case
def check_blocks(board):
    return check_rows(view_nsquares_as_rows(board))

# A helper just to retrieve a subsquare from our perfect-square sudoku board.
# In an NxN board we have N subsquare-blocks.
def get_nsquare(board, index):
    size = len(board[0])
    # No need to use a library to take square root
    subsize = int(size**(0.5))
    # Get block coordinates using standard array coordinate deflattening trick
    x, y = index % subsize, index / subsize # Note this is integer division
    # Multiply-out to get the subsquare bounds
    x1, x2 = subsize * x, subsize * (x+1)
    y1, y2 = subsize * y, subsize * (y+1)
    return [row[x1:x2] for row in board[y1:y2]]

# This is like a transpose, but putting each block into a row instead
#   of putting each column into a row.
def view_nsquares_as_rows(board):
    return [flatten_2d(get_nsquare(board, i)) for i in range(len(board[0]))]

# One more helper to flatten a 2d list into a single row, also
#  plagiarized from the first google result.
def flatten_2d(list2d):
    return [item for sublist in list2d for item in sublist]

Answer 3

I'm not experienced in Python, but I'd change how you done the check_if_all_numbers function to:

def check_if_all_numbers(numbers):

    bincheck = 0
    goal = 0

    for n in numbers
        bincheck = bincheck | (1 << (n-1)) # set the n'th bit of binCheck to 1
        goal = goal << 1 | 1 # set one more bit to 1 in goal

    return (bincheck == goal) # check all numbers

This is certainly faster because it uses exactly 9 (size of numbers) × 5 basic operations
Where you're creating an array using 9 × 2 operations (without counting array management), sorting the array using log(9) × 9 operations, and comparing the arrays using 9 operations.

Example:

With Numbers = 982 134 675 (correct)
Bincheck = 0b 0000 0000 0000, Goal = 0b 0000 0000 0000 #Init
Bincheck = 0b 0001 0000 0000, Goal = 0b 0000 0000 0001 #Add 9
Bincheck = 0b 0001 1000 0000, Goal = 0b 0000 0000 0011 #Add 8
Bincheck = 0b 0001 1000 0010, Goal = 0b 0000 0000 0111 #Add 2
Bincheck = 0b 0001 1000 0011, Goal = 0b 0000 0000 1111 #Add 1
Bincheck = 0b 0001 1000 0111, Goal = 0b 0000 0001 1111 #Add 3
Bincheck = 0b 0001 1000 1111, Goal = 0b 0000 0011 1111 #Add 4
Bincheck = 0b 0001 1010 1111, Goal = 0b 0000 0111 1111 #Add 6
Bincheck = 0b 0001 1110 1111, Goal = 0b 0000 1111 1111 #Add 7
Bincheck = 0b 0001 1111 1111, Goal = 0b 0001 1111 1111 #Add 5
Bincheck == Goal > it's ok

Another Example:

With Numbers = 982 154 675 (false because 2 times '5' digit, 0 times '3')
Bincheck = 0b 0000 0000 0000, Goal = 0b 0000 0000 0000 #Init
Bincheck = 0b 0001 0000 0000, Goal = 0b 0000 0000 0001 #Add 9
Bincheck = 0b 0001 1000 0000, Goal = 0b 0000 0000 0011 #Add 8
Bincheck = 0b 0001 1000 0010, Goal = 0b 0000 0000 0111 #Add 2
Bincheck = 0b 0001 1000 0011, Goal = 0b 0000 0000 1111 #Add 1
Bincheck = 0b 0001 1001 0011, Goal = 0b 0000 0001 1111 #Add 5
Bincheck = 0b 0001 1001 1011, Goal = 0b 0000 0011 1111 #Add 4
Bincheck = 0b 0001 1011 1011, Goal = 0b 0000 0111 1111 #Add 6
Bincheck = 0b 0001 1111 1011, Goal = 0b 0000 1111 1111 #Add 7
Bincheck = 0b 0001 1111 1011, Goal = 0b 0001 1111 1111 #Add 5
Bincheck != Goal > it's KO

Answer 4

The main function prints the problems it finds, this means that you cannot reuse its results. It can only be the end point of the program.

I suggest you return appropriate constants like SudokuState.ROW_INVALID or SudokuState.BLOCK_INVALID. A thin wrapper may convert this constants to print values by a dictionary.

all

The check_rows function can be simplified with all that better expresses the overall meaning: "The rows are valid if all the rows contain each 1-9 number exactly once"

Answer 5

If you want to use numpy, then you can take advantage of it's many capabilities to make your code very sleek:

import numpy as np

def is_good_sudoku(board):
    board = np.asarray(board)
    assert board.ndim == 2  # Input must be a two-dimensional table.
    N = board.shape[0]
    assert board.shape[1] == N  # Input must be square.
    n = int(np.sqrt(N))
    assert n * n == N  # Input size must be a perfect square.

    numbers_1_N = np.arange(1, N + 1)

    # Check rows and columns
    if (not np.all(np.sort(board, axis=1) == numbers_1_N) or
            not np.all(np.sort(board.T, axis=1) == numbers_1_N)):
        return False

    # Check blocks
    blocks = board.reshape(n, n, n, n).transpose(0, 2, 1, 3).reshape(N, N)
    return np.all(np.sort(board.T, axis=1) == numbers_1_N)

I have assumed that this is not a public function, so it should never receive incorrectly shaped inputs, hence the use of assert to document expectations, rather than raising a proper error as you would do if validating user input.

I have also made it return a boolean, and given the function a corresponding name, so that you can then write code using it that reads like if is_good_sudoku(board): ... which is something niec to have.

In the actual implementation there are a couple of magical steps if you are not familiar with NumPy, but which wouldn't really warrant a comment in code that uses it heavily:

1. The use of broadcasting to simplify the check. The check is done by comparing an array of shape (N, N) to an array of shape (N,). Because of broadcasting, NumPy treats the latter as if it was also of shape (N, N), with all rows being identical to the array of shape (N,) provided.

2. The reshaping to 4D to extract the blocks. This is a little mind bending at first, but once you get the hang of it it's extremely useful. By reshaping the original board to (n, n, n, n) we basically turn it into a square table of (n, n) with each item being itself a square table of (n, n). We then rearrange the axes so that when we undo the reshaping, each row turns into one of the blocks we are interested in. This makes a copy of the full array (the first reshape simply created a view of the same memory), so it may not be very efficient with really large arrays. But for your typical 9x9 sudoku there is no need to even worry about that.

Answer 6

Looking over current answers, it doesn't seem a summing approach to checking the rows, columns, and larger squares of a Sudoku board has yet been discussed. If we discard the naïve approach and instead assume that Sudoku will always be played on a 9x9 grid with the values 1-9, we then know that all rows, columns, and squares should sum to 45.

Thus, for any numpy.array representing a row, column, or square (3x3), we can use Numpy's sum function and check whether the sum is equal to 45. If we were to make this into a function, it may look something like this:

import numpy

def check_array(structure, valid = 45):
    """
    Verifies that a sudoku column, row, or square is valid (assumes a 9x9 grid that requires the unique values 1 - 9 in each array).
    @param
        structure  – numpy.array – required  – a col, row, or square representation to validate
        valid      – integer     – optional  – valid sum value
    @return
        result     – boolean                 – is the array valid?
    """
    result = numpy.sum(array) == valid
    return result

This would serve as a generalizable way of verifying whether each board structure is valid.

Alternatively, without using Numpy, we could also use sets to represent rows, columns, and squares and write a similar function to perform our check:

def check_set(structure, valid = {1, 2, 3, 4, 5, 6, 7, 8, 9}):
    """
    Verifies that a sudoku column, row, or square is valid (assumes a 9x9 grid that requires the unique values 1 - 9 in each array).
    @param
        structure  – set         – required  – a col, row, or square representation to validate
        valid      – set         – optional  – set representation of valid row, col, or square
    @return
        result     – boolean     – is the array valid?
    """
    result = len(array & valid) == len(valid)
    return result

Of course, to use this, you would have to type rows, columns, and squares as sets, which makes this approach less relevant unless you're purposefully pursuing a Python only route.

Finally, is we assume a user who knows nothing of how to play Sudoku, we could address the fringe case (that there are multiple ways of summing to 45) by combining these approaches:

def check_set(structure, valid = {1, 2, 3, 4, 5, 6, 7, 8, 9}):
    """
    Verifies that a sudoku column, row, or square is valid (assumes a 9x9 grid that requires the unique values 1 - 9 in each array).
    @param
        structure  – set         – required  – a col, row, or square representation to validate
        valid      – set         – optional  – set representation of valid row, col, or square
    @return
        result     – boolean     – is the array valid?
    """
    if (len(array & valid) == len(valid)) and (sum(array) == sum(valid)):
        return true
    else:
        return false

Note: indexing and error handling would be done outside of these functions.