Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created May 23, 2017 18:45
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/66e745d8008101bb4fe20dcb4c035da0 to your computer and use it in GitHub Desktop.
Save jianminchen/66e745d8008101bb4fe20dcb4c035da0 to your computer and use it in GitHub Desktop.
Sudoku solver - leetcode 37 - 2017 - make it simple -
public class Solution {
public void SolveSudoku(char[,] board) {
// your code goes here
SudokuSolveHelper(board, 0,0);
}
/// <summary>
/// recursive design, start from left top corner of board, and go
/// through one row from left to right, top to down.
/// </summary>
/// <param name="board"></param>
/// <param name="row"></param>
/// <param name="col"></param>
/// <returns></returns>
public static bool SudokuSolveHelper(char[,] board, int row, int col)
{
// base case
if(row == 9)
{
return true;
}
var nextOne = getNextOne(row, col) ;
var visit = board[row, col];
bool isEmpty = visit == '.';
if (!isEmpty)
{
// recursive to next one -> lastColumn, next column/ next row
return SudokuSolveHelper(board, nextOne[0], nextOne[1]);
}
for (int value = 1; value <= 9; value++)
{
var current = (char)('0' + value);
// pass 3 checking - column checking/ row checking/ small check
if (checkConstraints(board, row, col, current))
{
board[row, col] = current;
// next col/ next col
if (SudokuSolveHelper(board, nextOne[0], nextOne[1]))
{
return true;
}
}
board[row, col] = '.'; // backtracking
}
return false; // compiler error - not all path returns value
}
private static int[] getNextOne(int row, int col)
{
const int SIZE = 8;
int nextRow = (col == SIZE)? (row + 1) : row;
int nextCol = (col == SIZE)? 0 : (col + 1);
return new int[]{nextRow, nextCol};
}
private static bool checkConstraints(char[,] board, int row, int col, int search)
{
const int SIZE = 8;
// check row
for (int index = 0; index <= SIZE; index++)
{
var current = board[row, index];
if (current == search)
{
return false;
}
}
// check column
for (int index = 0; index <= SIZE; index++)
{
var current = board[index, col];
if (current == search)
{
return false;
}
}
// check 3*3 small matrix
int startX = row / 3 * 3;
int startY = col / 3 * 3;
for (int i = startX; i < startX + 3; i++)
{
for (int j = startY; j < startY + 3; j++)
{
var current = board[i, j];
if (current == search)
{
return false;
}
}
}
return true;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment