Hello, it has been a minute but I finally have a tutorial for you all: Sudoku Validator. I first saw this question on Pramp.com (and yes I bombed it). I finally came up with a great solution that I feel is teachable enough. The question goes, “given a 9×9 grid, verify whether it is a valid Sudoku.” Just like the game, a valid Sudoku is when all numbers across a row, down a column and within a square contain all unique numbers from 1-9. If a Sudoku is valid, return True. If not, False. This is in object-oriented Python (don’t run, you got this).
Before the breakdown, here is the full code:
Here are some links regarding Python classes:
First we want to create a class called, Sudoku_Checker. Within the class, we have the constructor that will instantiate the board we give it. All other methods will inherit from this constructor.
Now on to our first method, we have the board_validator, this method should return True or False after verifying if all methods below it evaluate to True/False. In order for the board to return true, all methods below it must equal true. Once we have hit the return action in this method, it calls the other methods to action, starting with checkRows.
Our second method, compareAll, contains a variable, compare, that generates a list of unique numbers from 1-9. In Python 2, you can use compare = range(1,10) but in Python 3 you must create the list compare = [1,2,3,4,5,6,7,8,9]. This method works along side the method below it, checkRows. When checkRows calls compareAll, it passes it a row in the grid. compareAll takes this row and sorts it. It then checks whether the sorted list passed in is equal to the variable compare. If so, it will return True.
Finally the meat of the algorithm in the three methods below.
As stated earlier, in Sudoku we want an entire row to have all unique characters from 1-9. checkRows takes the board as an argument and iterates through the grid, grabbing a row at each iteration. This is the row it passes to compareAll. Once compareAll returns True for all rows, the entire method returns True. If one row returns False, the entire method is False and the Sudoku is not valid.
To check whether all columns in a grid are valid we have the checkCols method. checkRows takes the board as an argument. We will be using a double for loop, which isn’t too bad here since we know the grid is a 9×9. The first for loop will iterate from 0 to the length of the grid (which is 9). Then we are defining a variable called hold and setting it equal to an empty list. Our second for loop will add to this list. Our second for loop grabs the length of the first row. We know all rows are the same length, so how ever many items are in a row are how many columns there are. In the following line within the loop, we begin to append to our hold list. Look carefully at ‘hold.append(board[j][i])’. This may be a bit challenging to grasp but I will try my best to explain. We know that we want to grab the first column. What do all items in the first column have in common? Their indices are all 0 in a row. What is different? Their indices increase as you move down the grid. We know that the outside loop will not increment until the inside loop has finished. Therefore we will reverse the order of i and j to append to hold.
Iteration 1 will append ]: (first row first column)
Iteration 2 will append : (second row first column)
Iteration 3 will append : (third row first column)
Iteration 4 will append : (fourth row first column)
…… and so forth.
j is incrementing up to 9. Once j has grabbed the last row, first column, i will increment by 1 to grab the second column. So the second iteration of i will look like this:
Iteration 1 will append ]: (first row second column)
Iteration 2 will append : (second row second column)
Iteration 3 will append : (third row second column)
…… and so forth.
Anyways back to the first iteration of i. So while i is still 0 and we have finished adding all of the elements to the hold list, we will pass the list, hold, to the method compareAll to see if all elements in that particular row are valid. If the hold list is valid, it should return True and i can increment to the next column.
Okay, so we checked if the rows are valid. They were, good looks. The columns. Are those valid too? They are? Okay perfect so now let’s check the squares. Like I said previously, all 3×3 squares within the 9×9 grid must have all unique numbers from 1-9. I’d like to take a moment to shout out Stack Overflow for their help with this function. It took me a minute. I wouldn’t have gotten this method with out their help.
Here is where I also recommend you take this entire code snippet and drop it into Pythontutor.com because…this is gonna be a bit hard to explain, but i’ll try.
So anyways, the squares. We will be using the range function to its max. Range can take three arguments as range(start,stop,step). checkSquares takes in the board. The first for loop utilizes the 3 range arguments, range(0,9,3). Essentially, we are starting at 0 and stopping at 9 but taking 3 steps at a time. So instead of range incrementing by 1 in a for loop, it will increment by 3 as so: 0 -> 3 -> 6 -> and stop before 9. This first for loop will allow us to get the rows in the grid, but the second for loop within it will allow us to access the items.
Now the nums variable:
nums = board[i][j:j+3] + board[i+1][j:j+3] + board[i+2][j:j+3]
What is going on?
This variable is holding an entire 3×3 square. board[i][j:j+3] on first iteration equates to board[0:0+3], which are the first 3 items in the first row, [5,3,4]. It is concatenating the first row and first 3 items to the second row, and first 3 items, board[0+1][0:0+3] = [6,7,2]. Same with the third row, board[0+2][0:0+3] = [1,9,8].
Using the example grid above, nums should equate [5,3,4,6,7,2,1,9,8] on first iteration. Then we pass it to compareAll to check if it is a valid list of unique numbers 1-9. If so, j increments to 3 and nums looks like this:
nums = board[3:3+3] + board[0+1][3:3+3] + board[0+2][3:3+3]
Which is this list: [6,7,8,1,9,5,3,4,2]
In the end, if everything looks good checkSquares will return True and call back to the board_validator which should return True.
*In order for your tests to work, you need to have your Sudoku_Checker class in a file called, __init__.py, and in a folder titled, ValidSudoku. The tests below need to be on the outside of this folder to run correctly.