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!

Decrease

I wish I had my old computer with my code from CS2, I did this exact thing in freshman year of undergrad. – Indoors

Anyway, Counter will be useful. – Indoors

What does "does not seem to be working" mean? What goes wrong, and where? What sample data are you trying it on, what do you expect it to do, and what does it do instead? Is easy supposed to return True or False? – Diphthongize

Should the checker fail if the grid is not fully filled in or only if more than one number from 1 to 9 is found? – Etymon

Answer 1

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)

Ankylostomiasis

for sudoku_ok -> max(l)+1 == 10 == len(set([0]+l)) might be faster. – Etymon

@Etymon -- that is a quick (albeit confusing to me) way of checking whether a line is a valid answer line in a sudoku, but the OP merely wants to know whether a line is not yet invalid. i.e. zeroes, representing blanks, must be allowed. – Ankylostomiasis

Answer 2

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

Handcar

Not sure if this is relevant after a short look at the code, but if vec[1:10] is [0, 1, 2, 0, 1, 2, 0, 1, 2], then sum(vec[1:10]) would also be 9. – Cataract

@NoctisSkytower: good point, better to use something like all or the direct test. – Handcar

Answer 3

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

Isidoro

Maybe I just didn't get it, but with your method wouldn't be a Sudoku marked as true even if the same two digits were to be in the same 3x3 grid since you are only checking for the rows and columns. – Trinitrotoluene

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

Aguilera

Answer 5

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

Dicast

Why not use len(set([0]+l)) == len([0]+l) to check for no dupes? – Etymon

there are zeros that are ignored, and also check for numbers larger than 9 – Dicast

all(n in range(1,10) for n in l) checks for anything not right. – Etymon

I think my answer is OK for a beginner. On the other hand, how does all verify there are no duplicates? – Dicast

but you can have 9 ones? sorry maybe I cannot see something trivial – Dicast

max(l)+1 == 10 == len(set([0]+l)) ? – Etymon

Answer 6

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

Dorton

Answer 7

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

Topflight

Answer 8

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

Insidious

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

Bechuana

Why? Other than turning a linear algorithm into a quadratic one, what is this supposed to be changing? – Diphthongize

speaking an input size of 9, making it a n^2 algorithm doesn't really matter. but it is much easier to read and understand – Bechuana

The OP showed some code that isn't working, and asked why not. You offered different code, with no explanation, that does the exact same thing as his code. How is that helpful? – Diphthongize

Answer 10

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

Rexrexana

Not that lists that small take a while to sort, but since when was sorting O(log n) in the worst case? – Indoors

I said extra factor of O(logn), meaning it take log n times as long as the histogram approach – Rexrexana

Answer 11

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!

Decrease

Answer 12

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

Zubkoff

Answer 13

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

Strontia

Answer 14

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

Mealtime