Created
March 15, 2018 03:39
-
-
Save jianminchen/f1c8497ea3e4f53a850758295ae5f5d3 to your computer and use it in GitHub Desktop.
Sudoku solver - March 14, 2018 - 8 pm mock interview - pass all test cases, but I had a few issues
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
class Solution | |
{ | |
public static bool SudokuSolve(char[,] board) | |
{ | |
if(board == null || board.GetLength(0) != 9 || board.GetLength(1) != 9) | |
return false; | |
return sudokuSolveHelper(board, 0, 0); | |
} | |
private static bool sudokuSolveHelper(char[,] board, int startRow, int startCol) | |
{ | |
// base case | |
if(startRow == 9) | |
return true; | |
var current = board[startRow, startCol]; | |
var isDot = current == '.'; // here... | |
var isLastColumn = startCol == 8; | |
var nextRow = isLastColumn ? (startRow + 1) : startRow; | |
var nextCol = isLastColumn ? 0 : (startCol + 1); | |
if(!isDot) | |
{ | |
return sudokuSolveHelper(board, nextRow, nextCol); | |
} | |
else | |
{ | |
foreach(char item in getAvailable(board, startRow, startCol)) | |
{ | |
board[startRow, startCol] = item; | |
var result = sudokuSolveHelper(board, nextRow, nextCol); | |
if(result) | |
{ | |
return true; | |
} | |
board[startRow, startCol] = '.'; | |
} | |
return false; | |
} | |
} | |
private static HashSet<char> getAvailable(char[,] board, int startRow, int startCol) | |
{ | |
var numbers = new HashSet<char>("123456789"); | |
// by row | |
for(int index = 0; index < 9; index++) | |
{ | |
numbers.Remove( board[startRow, index]); // check by row | |
numbers.Remove( board[index, startCol]); | |
} | |
// 0 - 8 -> 0 - 2 -> 0, 3, 6 | |
int smallRow = startRow / 3 * 3; | |
int smallCol = startCol / 3 * 3; | |
for(int row = smallRow; row <= smallRow + 2; row++) | |
{ | |
for(int col = smallCol; col <= smallCol + 2; col++) | |
{ | |
numbers.Remove(board[row, col]); | |
} | |
} | |
return numbers; | |
} | |
static void Main(string[] args) | |
{ | |
} | |
} | |
/* | |
9 * 9 | |
digits from 1 to 9 | |
. blank space -> 1 to 9 | |
constraints: check row, no duplication | |
check column, no duplication | |
check 3 * 3 matrix | |
asked for if there is an existing solution | |
DFS - recursive - backtracking | |
0,0 -> row = 0, col = 2, each from 1 - 9, if there is availble -> check row/ col/ 3 * 3 matrix -> number available -> hashset -> | |
recusive call -> subproblem with row, col -> nextRow, nextCol -> return true -> find a solution | |
_> backtracking, try next number | |
all numbers from 1 - 9, return false; // | |
Base case: | |
row = 9, row 0 - 8 -> true | |
*/ | |
/* | |
Julia spent 30 minutes to analyze, and write code and fix all bugs. | |
1. First the interviewer asked me to optimize the time, I check row/ col/ 3 * 3 matrix 9 times. | |
It can be optimized to check once. | |
2. Second the hashset should be added "123456789" first, and then remove those numbers | |
in the selected row, col and selected 3 * 3 matrix; What I did is wrong, I put everything in the hashset. | |
I need to find "123456789" excluding the set. | |
3. Fail last test case, matrix with all dot symboles 9 rows * 9 columns. I checked that line 65 missing = sign | |
in the term col <= smallCol + 2. | |
*/ | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment