Valid Sudoku

How to validate Sudoku board and check the input correctness programatically.


Baraa Abuzaid
@baraaabuzaid
Valid Sudoku

So this article is about validating a fun logic game called sudoku. 
Sudoku board is consists of 9×9 gird, which contains 3×3 subgrids.
The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that form the main grid has no duplicate number.

The condition is to:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

So the sudoku validator(Valid Sudoku) we are about to build will validate against the above conditions. While ignores none filled cells.We’ll start with a lengthy solution that’s easier to reason about, then compose it down into a much more concise solution at the end.

#Valid Sudoku Input Format

If we have a 9×9 Sudoku board it can be represented programatically with nested arrays in which each array of the nested array represents a row in the board.

Soduku array representation

#Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition

Let’s assume we’ve got the magical function isValidSubBox(), which would allow us to validate each of the nine 3×3 subgrids. Then all we have to do is to iterate through the board and call isValidSubbox().
Iterating on the board by making the loop outer and inner step size equal to the height and width of the 3×3 grid respectively. If any of the subgrids is not valid sudoku no need to continue, we return false.

Valid sudoku subgrids checking

Now let’s dig down and see what’s isValidSubBox() function is made of. The idea is to iterate over the subgrid column by column. If we encounter the same cell twice, that means it isn’t valid sudoku. Meanwhile, we ignore the empty cells indicated by dots and keep track of other cells using a hash map.

Checking 3×3 subgird is valid

#Each row must contain the digits 1-9 without repetition.

For this we can iterate over each row in Sudoku board array. checking against duplication with help of hash map.

#Each column must contain the digits 1-9 without repetition.

And likewise we do the same steps, only this time we iterate the board column wise.

You can combine all of the above steps and voilà! now you have it. a Sudoku validator. Although, we can do all of the above steps into one nested iteration and make the code more concise, But for the seek of demonstration breaking it into multiple iterations will make the concept clear and easier to grasp.

Show Comments (0)

Comments

Related Articles

General

Coding Identity Matrix in Python

Basically, the identity matrix is a matrix of zero elements except for the main diagonal elements is set to one. a more formal definition could be written as A matrix I ∈...

Posted on by Baraa Abuzaid
AWS

Set a new user with password login on AWS EC2 linux Instance

Login to your elastic compute instance with a private-key each time isn’t quite convenient. So we will change that by creating a new user, set ssh config and enabling...

Posted on by Baraa Abuzaid