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 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));
}
}
