Created
June 13, 2017 17:28
-
-
Save jianminchen/d90fbca1a34cd49df214e0da00243b2f to your computer and use it in GitHub Desktop.
Sudoku - Leetcode 37 - mocking interview code passes online judge - find the bug on line 84, line 93, line 111
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; | |
class Solution | |
{ | |
// June 12, 2017 | |
// write the code in the mocking experience. | |
// brute force search - 9 * expontial | |
// DFS - backtrack | |
// 9 backtrack -> n ^2, 81 cells - at most 81 emtpy cells | |
// | |
static void Main(string[] args) | |
{ | |
char[,] board = new char[9,9]; | |
board = new char[9,9]{ | |
{'5','3',' ',' ','7',' ',' ',' ',' '}, | |
{'6',' ',' ','1','9','5',' ',' ',' '}, | |
{' ','9','8',' ',' ',' ',' ','6',' '}, | |
{'8',' ',' ',' ','6',' ',' ',' ','3'}, | |
{'4',' ',' ','8',' ','3',' ',' ','1'}, | |
{'7',' ',' ',' ','2',' ',' ',' ','6'}, | |
{' ','6',' ',' ',' ',' ','2','8',' '}, | |
{' ',' ',' ','4','1','9',' ',' ','5'}, | |
{' ',' ',' ',' ','8',' ',' ','7','9'}, | |
}; | |
Console.WriteLine(sudokuSolve(board)); | |
} | |
static bool sudokuSolve(char[,] board) | |
{ | |
// your code goes here | |
return sudokuSolveHelper(board, 0, 0); | |
} | |
// | |
private static bool sudokuSolveHelper(char[,] board, int row, int col) | |
{ | |
// base case | |
if (row > 8) // 0 - 8 , row = 9 | |
{ | |
return true; | |
} | |
var current = board[row, col]; | |
bool isEmtpy = current == ' '; | |
bool isNumber = (current - '0') >= 0 & (current - '0') <= 9; | |
if (isNumber) // 3 | |
{ | |
bool isLastColumn = col == 8; | |
int nextRow = isLastColumn ? (row + 1) : row; | |
int nextCol = isLastColumn ? 0 : col + 1; | |
return sudokuSolveHelper(board, nextRow, nextCol); // 0, 1, (0, 2) | |
} | |
else // | |
{ | |
for (int number = 1; number <= 9; number++) | |
{ | |
if (isAvailable(board, number, row, col)) | |
{ | |
board[row, col] = (char)(number + '0'); // add '0' | |
if (sudokuSolveHelper(board, row, col)) | |
{ | |
return true; | |
} | |
else | |
{ | |
board[row, col] = ' '; | |
} | |
} | |
} | |
return false; | |
} | |
// unreachable code | |
} | |
private static bool isAvailable(char[,] board, int number, int row, int col) | |
{ | |
// check row | |
for (int column = 0; column < 9; column++) | |
{ | |
if (board[row, column] - number == '0') // add '', should be '0' instead of 0 | |
{ | |
return false; | |
} | |
} | |
// check column | |
for (int rowIndex = 0; rowIndex < 9; rowIndex++) | |
{ | |
if (board[rowIndex, col] - number == '0') // add '', should be '0' instead of 0 | |
{ | |
return false; | |
} | |
} | |
// check 3 * 3 matrix | |
// row -> row/3 | |
// col -> col/3 | |
int smallMatrixRow = row / 3; // 0 | |
int smallMatrixCol = col / 3; // 2 | |
int startRow = smallMatrixRow * 3; | |
int startCol = smallMatrixCol * 3; | |
for (int r = startRow; r < startRow + 3; r++) // 5, 3, 6, 8, 9 - 1 avaiable | |
{ | |
for (int c = startCol; c < startCol + 3; c++) | |
{ | |
if (board[r, c] - number == '0') // add '', should be '0' instead of 0 | |
{ | |
return false; | |
} | |
} | |
} | |
return true; | |
} | |
} | |
// 5 3 ? - 7 - - - - | |
// 1 - 9, each row -> 3, 5, 7, 8 | |
// 1, 2, 3, 4, 6, 9 | |
// 1, -> return true | |
// ? -> 2, return true | |
// ? -> 3, ... | |
// ? -> 9, return true | |
// false | |
// DFS -> backtracking | |
// constraints - row checking, column check, 3 * 3 checking | |
// base case row * col 9 * 9, 0 - 8, row = 9 | |
// row, col -> row, col + 1, if it is not last column, increment row ++ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment