Return SudokuSolveHelper(board, nextRow, nextCol) If (board = null || board.GetLength(0) 8) Public static bool SudokuSolve(char board) The structure is more simple without double for loop. 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. I try to use my question to help the review of the most popular algorithm as well. One of my favorite review on Sudoku solver is solving Sudoku using backtracking. 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 81 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. I also like to share my algorithm of time complexity analysis. After first two practices, I always like to write Sudoku solver using the following structure: 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. Sudoku solver algorithm is one of algorithms I have learned from various peers last 6 months. 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. And the code is much easy to read because the structure of depth first search is very clear. Do not write any double loops such as two nested for loops. 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. I practiced this algorithm through mock interview starting from this March 4 or 5 times. In every 3x3 sub-board that is illustrated below, all characters ‘1’,‘2’,…,‘9’ appear exactly once. In every column of the array, all characters ‘1’,‘2’,…,‘9’ appear exactly once. In every row of the array, all characters ‘1’,‘2’,…,‘9’ appear exactly once. 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'. The dot character '.' stands for a blank space. Similar to Leetcode 37 Sudoku solver, the algorithm is to determine if the sudoku board can be filled with ‘1’,‘2’,…,‘9’.Ī sudoku board is represented as a two-dimensional 9x9 array, each element is one of the characters ‘1’,‘2’,…,‘9’ or the '.' character.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |