Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created December 6, 2017 07: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/f33a7f7021e10167d28132a4485592be to your computer and use it in GitHub Desktop.
Save jianminchen/f33a7f7021e10167d28132a4485592be to your computer and use it in GitHub Desktop.
Sudoku solver - return true or false for a sudoku puzzle using '1', '2', to '9', '.' means unfilled.
using System;
class Solution
{
public static int SIZE = 8;
public static bool SudokuSolve(char[,] board)
{
if(board == null || board.GetLength(0) <= SIZE || board.GetLength(1) <= SIZE ) // 8
{
return false;
}
return SudokuSolveHeler(board, 0, 0); //
}
private static bool SudokuSolveHeler(char[,] board, int row, int col)
{
// base case
if(row == 9) // false
{
return true;
}
var visit = board[row, col]; // '5', '3'
var isDot = visit == '.'; // false
var lastColumn = col == SIZE; // 0 != 8
var nextRow = lastColumn? (row + 1) : row; // 0, 0,
var nextCol = lastColumn? 0 : (col + 1); // 1, 2
if(!isDot)
{
return SudokuSolveHeler(board, nextRow, nextCol); // (0, 1)
}
//
for(int number = 1 ; number <= 9; number++) // 1, 2, 4
{
char current = (char)(number +'0'); // '0'
if(isAvailable(board, row, col, current)) // 1, true, false
{
// DFS
board[row, col] = current; // 1
var result = SudokuSolveHeler(board, nextRow, nextCol);
if(result)
{
return true;
}
board[row, col] = '.';
}
}
return false;
}
private static bool isAvailable(char[,] board, int row, int col, char current) // row = 0, col = 2
{
// check row
for(int column = 0; column <= SIZE; column++ )
{
if(board[row, column] == current)
{
return false;
}
}
// check col
for(int rowIndex = 0; rowIndex <= SIZE; rowIndex++)
{
if(board[rowIndex, col] == current)
{
return false;
}
}
// check 3 * 3 matrix
int startRow = row/3 * 3; // 0
int startCol = col/3 * 3; // 0
for(int rowIndex = startRow; rowIndex < startRow + 3; rowIndex++) // 0, < 3
{
for(int colIndex = startCol; colIndex < startCol + 3; colIndex++) // 0, 3
{
if(board[rowIndex, colIndex] == current)
{
return false;
}
}
}
return true;
}
static void Main(string[] args)
{
}
}
/*
5 3 4 ? 7 ? ? ? ?
what is possible number for this element - check row/ column, 3 * 3 matrix -> 3, 5,6, 7, 8, 9, try 1, 2, 4,
All options - 3 options
return false
DFS/ backtracking
(0,0)
base case: 8 * 8
row = 9 , finish all 8 rows/ 8 columns -> return true;
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment