Krdytkyu

Problem statement

Similar to Leetcode 37 Sudoku solver, the algorithm is to determine if the sudoku board can be filled with ‘1’,‘2’,…,‘9’.

A sudoku board is represented as a two-dimensional 9x9 array, each element is one of the characters ‘1’,‘2’,…,‘9’ or the '.' character. The dot character '.' stands for a blank space. The sudoku solver should fill the blank spaces with characters such that each row and each column and each 3 * 3 matrix forming 9 * 9 matrix have each character of '1', '2', ...,'9' exactly once.

In every row of the array, all characters ‘1’,‘2’,…,‘9’ appear exactly once.
In every column of the array, all characters ‘1’,‘2’,…,‘9’ appear exactly once.
In every 3x3 sub-board that is illustrated below, all characters ‘1’,‘2’,…,‘9’ appear exactly once.

My practice of algorithms

I practiced this algorithm through mock interview starting from this March 4 or 5 times. First time the peer complained to me that I do not know how to write a depth first search algorithm, I did not explicitly write down base case at the beginning of the function; Second time I was interrupted and told to write as simple solution as possible, specially showing that base case is to finish the depth first search and go to row 9 which is out of matrix. Do not write any double loops such as two nested for loops. And the code is much easy to read because the structure of depth first search is very clear. So I practiced a few times to write depth first search like the following, besides I started to read leetcode discussion panel for various solution.

Learning through mock interview

Sudoku solver algorithm is one of algorithms I have learned from various peers last 6 months. The peer with senior experience gave me feedback from low rate like "Do not know how to write code" since I did not write base case inside the function at the beginning, and then next practice I was coached by a younger peer to write depth first search from (0,0) and avoid any two for loops. After first two practices, I always like to write Sudoku solver using the following structure:

  base case

  depth first search

     recursive function calls

     back tracking if need

Algorithm analysis

I also like to share my algorithm of time complexity analysis. My analysis of the algorithm is that any element of matrix has at most 9 choice to fill from '1' to '9', and there is 81 elements in the matrix, so the time complexity can go up to 9⁸¹ possibility, since the board already is filled with some elements, the backtrack and also early return, the time complexity can lower down, but the time complexity is unknown.

Favorite code review

One of my favorite review on Sudoku solver is solving Sudoku using backtracking. I try to use my question to help the review of the most popular algorithm as well. My review for the question is to use clear structure, explicitly write down base case using comment and also put base case in the first line of depth first search function, and start from (0,0) to do depth first search and use recursive function to help iterate the matrix, avoid double for loop. The structure is more simple without double for loop.

using System;

using System.Collections.Generic;



class Solution

{

    public static bool SudokuSolve(char[,] board)

    {

        // your code goes here

        if (board == null || board.GetLength(0) < 9 || board.GetLength(1) < 9)

        {

            return false;

        }



        // assume that 9 * 9

        return SudokuSolveHelper(board, 0, 0);

    }



    private static bool SudokuSolveHelper(char[,] board, int row, int col)

    {

        // base case

        if (row > 8)

        {

            return true;

        }



        var visit = board[row, col];

        var isDot = visit == '.';



        var nextRow = col == 8 ? (row + 1) : row;

        var nextCol = col == 8 ? 0 : (col + 1);



        if (!isDot)

        {

            return SudokuSolveHelper(board, nextRow, nextCol);

        }



        // assume that it is digit number 

        var availableNumbers = getAvailableNumbers(board, row, col);



        foreach (var option in availableNumbers)

        {

            board[row, col] = option;



            var result = SudokuSolveHelper(board, nextRow, nextCol);



            if (result)

            {

                return true;

            }



            board[row, col] = '.';

        }



        return false;

    }



    private static HashSet<Char> getAvailableNumbers(char[,] board, int currentRow, int currentCol)

    {

        var numbers = new char { '1', '2', '3', '4', '5', '6', '7', '8', '9' };

        var available = new HashSet<char>(numbers);        



        // check by row

        for (int col = 0; col < 9; col++)

        {

            var visit = board[currentRow, col];

            var isDigit = visit != '.';



            if (isDigit)

            {

                available.Remove(visit);

            }

        }



        // check by col

        for (int row = 0; row < 9; row++)

        {

            var visit = board[row, currentCol];

            var isDigit = visit != '.';



            if (isDigit)

            {

                available.Remove(visit);

            }

        }



        // check by 3 * 3 matrix 

        var startRow = currentRow / 3 * 3;

        var startCol = currentCol / 3 * 3;

        for (int row = startRow; row < startRow + 3; row++)

        {

            for (int col = startCol; col < startCol + 3; col++)

            {

                var visit = board[row, col];

                var isDigit = visit != '.';



                if (isDigit)

                {

                    available.Remove(visit);

                }

            }

        }



        return available;

    }



    static void Main(string args)

    {

        var board = new char[,]{

        {'.','.','.','7','.','.','3','.','1'},

        {'3','.','.','9','.','.','.','.','.'},

        {'.','4','.','3','1','.','2','.','.'},

        {'.','6','.','4','.','.','5','.','.'},

        {'.','.','.','.','.','.','.','.','.'},

        {'.','.','1','.','.','8','.','4','.'},

        {'.','.','6','.','2','1','.','5','.'},

        {'.','.','.','.','.','9','.','.','8'},

        {'8','.','5','.','.','4','.','.','.'}};



        Console.WriteLine(SudokuSolve(board));

    }

}

The code looks reasonably clean and simple, but there are some minor things which in my opinion could be improved.

        // your code goes here

This comment is a message to you about how to use the template which some system (Leetcode?) has given you. It's not a message to the maintenance programmer about your code, so you should delete it as soon as you've implemented that method.

        if (board == null || board.GetLength(0) < 9 || board.GetLength(1) < 9)

        {

            return false;

        }



        // assume that 9 * 9

Why return false and not throw new ArgumentException(nameof(board))? Well, ok, personally I'd split out ArgumentNullException and ArgumentOutOfRangeException cases, but the point is that these look like exception conditions rather than "no solution" conditions.

Why assume? Would it not make more sense to require that the board size be exactly 9 x 9?

    private static bool SudokuSolveHelper(char[,] board, int row, int col)

    {

        // base case

        if (row > 8)

        {

            return true;

        }

I can figure out what's going on here based on the other code and the context provided in the question, but I think it would be worth a comment explaining why this is the base case, or a method-level doc comment explaining that the method searches in a given order (from which I can infer the base case).

        var availableNumbers = getAvailableNumbers(board, row, col);



        foreach (var option in availableNumbers)

availableNumbers is used once, so I personally would inline it. However, this is a matter of taste, and I wouldn't be surprised if someone else has previously given you the opposite feedback. What I can say is that the code is consistent about always pulling out these intermediate values, and consistency is good, so well done for that.

    private static HashSet<Char> getAvailableNumbers(char[,] board, int currentRow, int currentCol)

Why HashSet<Char>? Firstly, since nothing in the calling code cares about it being a HashSet<>, the principle of coding to the interface rather than the implementation says that this method should return an IEnumerable<>. Secondly, the use of Char rather than char is inconsistent with the method body. I personally prefer to use the keywords for those System. types which have them, but this is again a matter of taste.

        var numbers = new char { '1', '2', '3', '4', '5', '6', '7', '8', '9' };

There's nothing wrong with using char, but string is also an IEnumerable<char>, and it's less fiddly to type and to read var numbers = "123456789";.

            var isDigit = visit != '.';



            if (isDigit)

            {

                available.Remove(visit);

            }

This is a microoptimisation. I would be inclined to say that since we know that available doesn't contain '.' we can simplify to

            available.Remove(visit);

and make it easier to see the method as a whole on screen.

        Console.WriteLine(SudokuSolve(board));

Is there any reason for writing True rather than the actual solution?

Finally, a note on magic numbers. If I asked you to modify this to solve 16 x 16 Sudokus, how much would you need to change? How about 12 x 12 Sudokus, with the blocks being 3 x 4?

I am not sure what the HashSet is doing for you. You add every digit to the HashSet and then remove what doesn't work. If you had a list and just added what worked that would be the same, right? Also the C++ code you pointed to has in the comments an efficient way to check row/column and box in a single loop as opposed to the 3 you have.

Finally, the guy who wrote "Do not know how to write code" probably had an inflated sense of how good he is. All code can be improved, but that is no reason to put people down.