Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 15, 2018 03:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/f1c8497ea3e4f53a850758295ae5f5d3 to your computer and use it in GitHub Desktop.
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
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