Sudoku Checker in Python

Question

I am trying to create a sudoku checker in python:

ill_formed = [[5,3,4,6,7,8,9,1,2],
              [6,7,2,1,9,5,3,4,8],
              [1,9,8,3,4,2,5,6,7],
              [8,5,9,7,6,1,4,2,3],
              [4,2,6,8,5,3,7,9],  # <---
              [7,1,3,9,2,4,8,5,6],
              [9,6,1,5,3,7,2,8,4],
              [2,8,7,4,1,9,6,3,5],
              [3,4,5,2,8,6,1,7,9]]
easy = [[2,9,0,0,0,0,0,7,0],
       [3,0,6,0,0,8,4,0,0],
       [8,0,0,0,4,0,0,0,2],
       [0,2,0,0,3,1,0,0,7],
       [0,0,0,0,8,0,0,0,0],
       [1,0,0,9,5,0,0,6,0],
       [7,0,0,0,9,0,0,0,1],
       [0,0,1,2,0,0,3,0,6],
       [0,3,0,0,0,0,0,5,9]]

I am expecting input like that- a list of 9 lists. The zeros represent number that have not been filled in by the user. They can appear multiple times in a row, column or 3x3.

def check_sudoku(grid):
if len(grid) == 9:
    numsinrow = 0
    for i in range(9):
        if len(grid[i]) == 9:
            numsinrow += 1
    if numsinrow == 9:
        for i in range(9):
            rowoccurence = [0,0,0,0,0,0,0,0,0,0]
            for j in range(9):
                rowoccurence[grid[i][j]] += 1
                temprow = rowoccurence[1:10]
                if temprow == [1,1,1,1,1,1,1,1,1]:
                    return True
                else:
                    return False
    else:
        return False
else:
    return False

I obviously need to check that there is a 9x9 list of lists (grid), and that there are no duplicates in each row, column and 3x3 small square. In the code, I first check to see if there are a proper number of rows (There should be 9). Then I check that each row has 9 elements in it (with the ill_formed example you see that this is not the case). I then attempt to check duplicates in each row but I am having some trouble doing so. I thought that I could loop over each row and loop over each element in that row, and add 1 to a list of ints (rowoccurence). For example, if the first number is a 2, then rowoccurence[2] should be equal to 1. The zeros are in rowoccurence[0] and are not checked(I have a temporary list which should take everything except that first element- the zeros- because there could be more than 1 zero in a row and the grid could still be legit). I try to check the temp list (basically rowoccurence) against a reference list of correct values but it does not seem to be working. Could you help me check the rows for duplicates in this sudoku checker? Thank you so much in advance!

Answer 1

I came up with a very straight forward and quite readable approach for validating a sudoku stored in a 2-dimensional list. The function assumes that a full 9x9 matrix is passed as an argument.

def validate_sudoku(matrix):
  for y in range(len(matrix)):
    horizontal, vertical, chunk = {}, {}, {}
    chunk_position = (y % 3 * 3, y // 3 * 3)

    for x in range(len(matrix[y])):
      if 1 > matrix[y][x] > 9 or matrix[y][x] in horizontal:
        return False
      horizontal[matrix[y][x]] = None

      if matrix[x][y] in vertical:
        return False
      vertical[matrix[x][y]] = None

      position = matrix[chunk_position[1] + x // 3][chunk_position[0] + x % 3]
      if position in chunk:
        return False
      chunk[position] = None

  return True

---

Explanation

The function checks for invalid numbers (e. g. 0 or 10) and for duplicates in each row, column and chunk. It is kept track of possible duplicates in dictionaries. The values are validated for uniquness by comparing the indexed matrix value with the values in the corresponding dictionary. Rows and column values are simply indexed with matrix[y][x] or respectively matrix[x][y]. The chunk value positions are calculated with % and //.

Answer 2

The question is old, but I leave a new contribution for others who come here, like me.

Correct me if I'm wrong, but I think the solution is quite simple. No need to check for duplicates in row, column and grid. Just check the row. Because if there are duplicates in the column or in the grid, there will also be duplicates in the row. So I think it's enough to check for 0 and duplicates on the row:

from collections import Counter
solved = True
for row in board:
    if max(Counter(row).values()) > 1: solved = False
    elif 0 in row: solved = False

Answer 3

import numpy as np

def is_valid(row):
    # checks whether a given set of values forms a valid row in sudoku
    return len(list(filter(lambda val: type(val) == int and 0 < val < 10, set(row))) == 9

def check_sudoku(grid):
    """ Check a sudoku board is correctly completed or not. """
    # checks whether the grid has 9 rows
    if len(grid) != 9:
        return False

    # checks whether the grid has 9 columns
    for i in range(9):
        if len(grid[i]) != 9:
            return False

    # turns grid from list to numpy array
    grid = np.array(grid)

    # checks whether the grid is filled with integers
    if grid.dtype != np.int:
        return False

    for i in range(9):
        # checks for repetition in rows
        if not is_valid(grid[i, :]):
            return False
        # checks for repetition in columns
        if not is_valid(grid[:, i]):
            return False
        # checks for repetition in squares
        if not is_valid(grid[i//3*3:i//3*3+3, j%3*3:j%3*3+3]):
            return False

    # returns true if none of the conditions reached
    return True

Answer 4

Took reference from @llb 's answer, which did not check for missing values or zeros, here's my solution which would work for negative values, zeros and missing values

def line_ok(e):
    if len(set(e)) != 9: return False
    for i in range(len(e)):
        if e[i] not in range(1,10): return False
    return True
    
def checker(grid):
    bad_rows = [False for row in grid if not line_ok(row)]
    grid = list(zip(*grid))
    bad_cols = [False for col in grid if not line_ok(col)]
    squares = []
    for i in range(0,9,3):
        for j in range(0,9,3):
            square = list(itertools.chain.from_iterable(row[j:j+3] for row in grid[i:i+3]))
            squares.append(square)
    bad_squares = [False for sq in squares if not line_ok(sq)]
    return not any([bad_rows, bad_cols, bad_squares])

print(checker(sudoku_correct))

PS: Due to less reps, couldn't comment. Hope whoever needs it, finds it :)

Answer 5

valid_solution= lambda board: not any([sorted(row)!=list(range(1,10)) for row in board]) and not any([sorted(list(col))!=list(range(1,10)) for col in zip(*board)]) and not any([sorted(board[i][j:j+3]+board[i+1][j:j+3]+board[i+2][j:j+3]) !=list(range(1,10)) for i in range(0,9,3) for j in range(0,9,3)])

Answer 6

I wrote the code on https://github.com/loghmanb/daily-coding-problem

from collections import defaultdict

def solution_valid(board)
    #check row and column is distict no or not?!
    rows = defaultdict(int)
    columns = defaultdict(int)
    squares = defaultdict(int)

    for i in range(9):
        rows.clear()
        columns.clear()
        squares.clear()

        for j in range(9):
            if board[i][j] is not None:
                columns[board[i][j]] += 1
                if columns[board[i][j]]>1:
                    return False
            
            if board[j][i] is not None:
                rows[board[j][i]] += 1
                if rows[board[j][i]]>1:
                    return False

            new_j = (i*3 + j%3)%9
            new_i = (i//3)*3 + j//3
            if squares[board[new_i][new_j]] is not None:
                squares[board[new_i][new_j]] += 1
                if squares[board[new_i][new_j]]>1:
                    return False
    return True

Answer 7

Wrote up a simple class to model a (completed) Sudoku board. Nothing tricky but a simple solution for a 9x9 board.

class SudokuBoard(object):

    DIGITS = set(range(1, 10))

    def __init__(self, values):
        self.values = values

    def row(self, n):
        return self.values[n]

    def rows(self):
        return self.values

    def cols(self):
        return [self.col(i) for i in xrange(9)]

    def col(self, n):
        return [self.values[i][n] for i in xrange(len(self.values))]

    def groups(self):
        return [self.group(i) for i in xrange(9)]

    def group(self, n):
        start_r = (n / 3) * 3
        start_c = n * 3   % 9
        values = []
        for row in xrange(start_r, start_r + 3):
            for col in xrange(start_c, start_c + 3):
                values.append(self.values[row][col])
        return values

    def is_correct(self):
        for row in self.rows():
            if self.DIGITS - set(row):
                return False
        for col in self.cols():
            if self.DIGITS - set(col):
                return False
        for group in self.groups():
            if self.DIGITS - set(group):
                return False
        return True

Answer 8

I am only posting this because most other solutions are hardly readable though they might be really efficient. For someone who is new and just trying to learn I believe that the code below is helpful and very readable. Hope this helps anyone looking to learn how to create a sudoku checker.

def check_sudoku(grid):
    for row in range(len(grid)):
        for col in range(len(grid)):
            # check value is an int
            if grid[row][col] < 1 or type(grid[row][col]) is not type(1):
                return False
            # check value is within 1 through n.
            # for example a 2x2 grid should not have the value 8 in it
            elif grid[row][col] > len(grid):
                return False
    # check the rows
    for row in grid:
        if sorted(list(set(row))) != sorted(row):
            return False
    # check the cols
    cols = []
    for col in range(len(grid)):
        for row in grid:
            cols += [row[col]]
        # set will get unique values, its converted to list so you can compare
        # it's sorted so the comparison is done correctly.
        if sorted(list(set(cols))) != sorted(cols):
            return False
        cols = []
    # if you get past all the false checks return True
    return True

Answer 9

If you want to check a row for duplicates, instead of

rowoccurence = [0,0,0,0,0,0,0,0,0,0]
    for j in range(9):
        rowoccurence[grid[i][j]] += 1
        temprow = rowoccurence[1:10]
        if temprow == [1,1,1,1,1,1,1,1,1]:
            return True
        else:
            return False

count:

b = True
for i in range(9):
    grid[i].count(grid[i][j]) > 1:
        b = False
    return b

Your approach does a bit more than just duplicate checking, it also takes care that only one digit number are present otherwise an out of bound exception will be raised

Answer 10

def check_sudoku(grid):
if len(grid) == 9:
    numsinrow = 0
    for i in range(9):
        if len(grid[i]) == 9:
            numsinrow += 1
    if numsinrow == 9:
        if checkrow(grid):
            if checkcol(grid):
                return True
            else:
                return False
        else:
            return False
    else:
        return False
else:
    return False

def checkrow(grid):
    for i in range(9):
        rowoccurence = [0,0,0,0,0,0,0,0,0,0]
        for j in range(9):
            rowoccurence[grid[i][j]] += 1
        temprow = rowoccurence[1:10]
        for q in range(9):
            if temprow[q] == 1 or temprow[q] == 0:
                continue
            else:
                return False
    return True

def checkcol(grid):
    for num in range(9):
        coloccurence = [0,0,0,0,0,0,0,0,0,0]
        for i in range(9):
            coloccurence[grid[i][num]] += 1
        tempcol = coloccurence[1:10]
        for q in range(9):
            if tempcol[q] == 1 or tempcol[q] == 0:
                continue
            else:
                return False
    return True

Ok guys I am back with a function to check the rows which works. Thank you so much for all the extensive help. I am sort of a noob at this so I did not understand some answers but I realized that I was returning true way too early. I also realized that if there were multiple zeros in a row, then some numbers would not come up in the rowoccurence/temp list. This is why I had to check for both 1's and 0's in the rowoccurence/temp list. I have also written a similar function to check the columns. Thanks again!

Answer 11

You return True too early, so you never make it to the test you hope to see fail:

            if temprow == [1,1,1,1,1,1,1,1,1]:
                return True  # <-- this is the culprit
            else:
                return False

Misc other notes: one easy way to make sure that all elements of some vector are equal to some constant is:

all(i == const for i in vector)

Another, even easier: if vec[1:10] are all 1, then sum(vec[1:10]) must be 9. (bad idea, see comment below.)

Answer 12

Remember, you're not searching for duplicates -- merely nonzero duplicates. Summing a set works for this. You can also check the legality of the row/column at the same time:

def sudoku_ok(line):
    return (len(line) == 9 and sum(line) == sum(set(line)))

def check_sudoku(grid):
    bad_rows = [row for row in grid if not sudoku_ok(row)]
    grid = list(zip(*grid))
    bad_cols = [col for col in grid if not sudoku_ok(col)]
    squares = []
    for i in range(9, step=3):
        for j in range(9, step=3):
          square = list(itertools.chain(row[j:j+3] for row in grid[i:i+3]))
          squares.append(square)
    bad_squares = [square for square in squares if not sudoku_ok(square)]
    return not (bad_rows or bad_cols or bad_squares)

Answer 13

I think the reason your code collapse is because your indent. You should do:

for j in range(9):
    rowoccurence[grid[i][j]] += 1
temprow = rowoccurence[1:10]
if temprow == [1,1,1,1,1,1,1,1,1]:
    return True
else:
    return False

Rather than:

for j in range(9):
        rowoccurence[grid[i][j]] += 1
        temprow = rowoccurence[1:10]
        if temprow == [1,1,1,1,1,1,1,1,1]:
            return True
        else:
            return False

Or use Counter:

from collections import Counter

...
    if numsinrow == 9:
        for i in range(9):
            count = Counter(grid[i])
            return False if max(count.values()) > 1 else True

Answer 14

How about just checking each row/column with:

sorted(row) == range(1,10)

or for python 3

sorted(row) == list(range(1,10))

I imagine the running time is dominated by creating a new list (whether you do the histogram approach or the sorting approach) so the extra factor of log(n) shouldn't be noticeable

In order to check each row,column, and subsquare, I suggest having extractor methods that get the nth row, column, and subsquare from your matrix (ie don't try and put it all in one method).

So for instance:

getSubSquare(m, i):
    subrow = (i // 3) * 3
    subcol = (i % 3) * 3
    v = [0] * 9
    for j in range(9):
        subrj = j // 3
        subcj = j % 3
        v[j] = m[subrow + subrj][subcol + subcj]
    return v

getRow(m,i):
   return m[i]

getCol(m,i):
   return [m[j][i] for j in range(9)]

Answer 15

Define a function to verify that there are no duplicates, then you can use it to check rows, columns, and 3x3 grids. You can reduce the nested blocks by returning early if some condition is not met, for example, number of rows are larger than 9. And only return true at the very end of the function if none of the checks fail.

from collections import Counter

def check_dups(l):
    counts = Counter()
    for cell in l:
        if cell != 0: counts[cell] += 1
        if cell > 9 or counts[cell] > 1: return False
    return True

def check_sudoku(grid):
    if len(grid) != 9: return False
    if sum(len(row) == 9 for row in grid) != 9: return False
    for row in grid:
        if not check_dups(row): return False
    return True