23
\$\begingroup\$

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.?
\$\endgroup\$
  • 1
    \$\begingroup\$ Instead of doing all that np.sort...np.array_equal stuff, have you considered just using Python's built-in set operations to check set equality? It would be a lot shorter and simpler (and probably faster). \$\endgroup\$ – Quuxplusone Jul 8 '16 at 6:19
  • \$\begingroup\$ What happens if you use 6×6 grids where blocks are 2×3? \$\endgroup\$ – 409_Conflict Jul 8 '16 at 9:21
  • \$\begingroup\$ @MathiasEttinger, it won't work for 6x6 grids. "..with sub-blocks of nxn". I know it would be quite easy to adapt it to such a case (take block_size as input and use it to create two different vectors with indices in check_blocks. However, I didn't do it, in order to keep this relatively simple. As I'm a beginner I thought it was better to learn how to do the simpler things well. Expanding it to cover more cases will be easy once I have the correct techniques. =) \$\endgroup\$ – Stewie Griffin Jul 8 '16 at 9:39
24
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ This looks quite nice and easy =) Very easy to read and understand. I see that you have the loops inside the main function instead of splitting it up into several functions. Is that on purpose? Is there a reason why you don't want a separate function for the rows and the blocks? I feel like often the most frequent tip almost regardless of task is: "Split it up into functions". (IMO I think it's easier to read this way, but I feel it goes against what I've seen other places. For instance, the last loop could be inside a function def validate_blocks, which would make the main function cleaner. \$\endgroup\$ – Stewie Griffin Jul 8 '16 at 10:46
  • 4
    \$\begingroup\$ It depends of several factors. Top of them being readability improvement/reduction and usefulness. Often suggesting to split a huge function into tinier parts is done to: 1. improve understanding of the top-level algorithm and 2. extract out redundant parts. None of them really applies here. In fact it's quite the opposite, since the block part relly on values computed earlier, you would have to either recompute them (meh) or pass them as parameters (which make the function less useful on its own). \$\endgroup\$ – 409_Conflict Jul 8 '16 at 10:58
  • \$\begingroup\$ Makes sense. :) \$\endgroup\$ – Stewie Griffin Jul 8 '16 at 11:14
  • \$\begingroup\$ One thing I'd say is use .flat instead of reshape. It is clearer. \$\endgroup\$ – Oscar Smith Jul 10 '16 at 18:17
  • \$\begingroup\$ @OscarSmith Except .flat is an iterator and can't be used as a drop in replacement of an array. But I'll add it as an alternative. \$\endgroup\$ – 409_Conflict Jul 10 '16 at 19:14
11
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ I do think these statements are a bit hard on the eye though: return [item for sublist in list2d for item in sublist]. It's almost like I have to write it down on paper to see what's going on... \$\endgroup\$ – Stewie Griffin Jul 8 '16 at 10:30
  • \$\begingroup\$ Just think of it as a nested for loop in one line. Or if you're a mathematician, read it like set builder notation. There's a slight learning curve but list comprehensions are both idiomatic and useful, when used properly. Of course they can get hard to read if you abuse them, but as a rule of thumb if you can fit it on one line (with descriptive variable names) then someone familiar with the construct should be able to read it as easily as they would a nested for loop. \$\endgroup\$ – machine yearning Jul 8 '16 at 10:49
  • \$\begingroup\$ @StewieGriffin Zen of python #5: Flat is better than nested \$\endgroup\$ – machine yearning Jul 8 '16 at 15:06
  • 2
    \$\begingroup\$ I'd suggest set(row) == required_nums(board) instead of all(n in row for n in required_nums(board)) with required_nums returning a set. \$\endgroup\$ – njzk2 Jul 9 '16 at 3:45
  • 1
    \$\begingroup\$ That's an excellent suggestion, \$\endgroup\$ – machine yearning Jul 10 '16 at 18:43
7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Clever, and yes. It will definitely be much faster =) I'm not sure I will jump straight into manipulating bits in a variable though. I think I might benefit from learning the basic "Pythonic" ways of doing this, not the "tricky/clever" ways. +1, I might actually use this one day. \$\endgroup\$ – Stewie Griffin Jul 8 '16 at 9:47
  • 2
    \$\begingroup\$ Neat trick to use a bitset. Note, however, that 1 << -1 will crash with ValueError: negative shift count. That could be a problem if, for example, you are using 0 to represent an empty square. I recommend def check_if_all_numbers(numbers): return reduce(operator.ior, (1 << n for n in numbers)) == (1 << 10) - 2. \$\endgroup\$ – 200_success Jul 10 '16 at 9:24
3
\$\begingroup\$

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"

\$\endgroup\$
  • \$\begingroup\$ I'll look in to how I can do what you're describing in the second paragraph. It looks pretty simple though, so it shouldn't be too hard =) I tried using all, but I couldn't get it to work, so I changed my approach. That was before I used flatten, maybe I'll get it to work with the code I have now =) \$\endgroup\$ – Stewie Griffin Jul 8 '16 at 9:50
  • \$\begingroup\$ @StewieGriffin It is not hard, remember to use a generator comprehension (do not read ahead if you want to solve it by yourself) return all( check_if_all_numbers(board[n]) for n in range(0,board.shape[1]) ) \$\endgroup\$ – Caridorc Jul 8 '16 at 10:38
3
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ In the last solution, no, given that the set will only contain unique values it will have a length of 1 and return false. @StewieGriffin \$\endgroup\$ – Greenstick Jul 10 '16 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.