4
\$\begingroup\$

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.

enter image description here

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 981 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));
    }
}
\$\endgroup\$
  • \$\begingroup\$ I continue to learn the Sudoku solver algorithm last few months. I wrote the Sudoku solver algorithm in mock interview on March 14, 2018. I wrote the analysis, code and passed all test cases in 30 minutes. The code is integrated all code reviews from this post. Here is the code: gist.github.com/jianminchen/f1c8497ea3e4f53a850758295ae5f5d3 \$\endgroup\$ – Jianmin Chen Mar 15 '18 at 18:19
3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ great code review. Here is my feedback, code to interface related to return function argument HashSet<int> is great teaching for me to learn as a concrete example, I give it 10 if I rate using 1 to 10. Write string "123456789" instead of using char array {'1', '2', '3', '4', '5', '6', '7', '8', '9'} , also my personal favorite advice. Based on IEnumerate<char> since in mock interview I only have 30 - 35 minutes, I am seeking ways to expedite the coding. Also I give it best rating on the advice. \$\endgroup\$ – Jianmin Chen Nov 6 '17 at 16:35
  • \$\begingroup\$ I think that the comment to help explain base case should like "//Base case: if the row is incremented to 9 which is bigger than maximum row value of matrix 8, then all elements are filled with correct value.", good advice to remind me to work on an explanation. \$\endgroup\$ – Jianmin Chen Nov 6 '17 at 16:38
  • \$\begingroup\$ I like to give your feedback on pulling out intermediate variables. It is learning experience, I try to follow TED principle, E - express the intent, when I write code, I may have short memory and quickly forget what I like to express, so in mock interview/ Hackerrank contest, I prefer to write explicitly what I try to do, avoid giant expression, do one thing a time in one statement. I journal my practice and practice again until I can write and fit in 30 minutes with a working solution to pass all test cases for mock interview algorithm. \$\endgroup\$ – Jianmin Chen Nov 6 '17 at 19:37
  • 1
    \$\begingroup\$ It seems to me that it would be more useful to print the 81 digits of the solution (board) rather than the bool return value of SudokuSolve. If the reason is that that was the spec required by whoever set the question, then fair enough. \$\endgroup\$ – Peter Taylor Nov 7 '17 at 7:50
  • 1
    \$\begingroup\$ (1) Why assume? I have a feeling that the comment is part of a pseudo-code-comment that was there before the actual code. i.e. it means "from this point on, we can assume that the board is (at least) 9*9". OP may not care about larger boards since he is able to ignore additional rows and columns. (2) availableNumbers is used once, so I personally would inline it The added benefit of not inlining it is ease of debugging, it makes it easier to look up the value. Plus, the method seems complex enough that OP has tested its output plenty of times :) \$\endgroup\$ – Flater Feb 2 '18 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.