Nov. 3, 2021
Here is the link.
C# | Depth first search | DFS with Backtracking - space efficiency | Warmup practice in 2021
Nov. 3, 2021
Introduction
It is so important for me to warm up my coding skills, and then I choose to write a C# solution to solve Sudoku solver 37.
Depth first search | Back tracking | Run a test case
The problem asked is to gurantee that there is a solution, so I choose to add a test case to run the code, and make sure that the code will return true if DFS is run to try to find first working solution.
I spent a few minutes to add the test case using given matrix in the problem statement.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _37_sudoku_solver
{
class Program
{
static void Main(string[] args)
{
RunTestcase();
}
public static void RunTestcase()
{
var board = new char[9][];
int index = 0;
board[index++] = "53..7....".ToCharArray();
board[index++] = "6..195...".ToCharArray();
board[index++] = ".98....6.".ToCharArray();
board[index++] = "8...6...3".ToCharArray();
board[index++] = "4..8.3..1".ToCharArray();
board[index++] = "7...2...6".ToCharArray();
board[index++] = ".6....28.".ToCharArray();
board[index++] = "...419..5".ToCharArray();
board[index++] = "....8..79".ToCharArray();
SolveSudoku(board);
}
/// <summary>
/// warmup algorithm - need more practice to write C# code
/// board.length == 9
/// board[i].length == 9
/// board[i][j] is a digit or '.'.
/// It is guaranteed that the input board has only one solution.
/// </summary>
/// <param name="board"></param>
public static void SolveSudoku(char[][] board)
{
var result = RunDepthFirstSearch(board, 0, 0);
//Debug.Assert(result);
}
/// <summary>
/// classical DFS algorithm to work on
/// </summary>
/// <param name="board"></param>
/// <param name="row"></param>
/// <param name="col"></param>
/// <returns></returns>
private static bool RunDepthFirstSearch(char[][] board, int row, int col)
{
//base case
if (row > 8)
{
return true;
}
var isLastColumn = col == 8;
int nextRow = isLastColumn ? (row + 1) : row;
int nextCol = isLastColumn ? 0 : (col + 1);
var current = board[row][col];
bool isDot = current == '.';
bool isNumber = (current - '0') >= 0 && (current - '0') <= 9;
if (isNumber)
{
return RunDepthFirstSearch(board, nextRow, nextCol);
}
foreach (var digit in getAvailableDigits(board, row, col))
{
board[row][col] = digit;
if(RunDepthFirstSearch(board, nextRow, nextCol))
{
return true;
}
board[row][col] = '.';
}
return false;
}
/// <summary>
/// Given a position in the matrix, check current row and current column, and also it's small matrix 3 x 3
/// Idea is to remove existing chars from given string "123456789" which has all chars
/// </summary>
/// <param name="board"></param>
/// <param name="currentRow"></param>
/// <param name="currentCol"></param>
/// <returns></returns>
private static IEnumerable<char> getAvailableDigits(char[][] board, int currentRow, int currentCol)
{
var hashSet = new HashSet<char>("123456789".ToCharArray());
for (int index = 0; index < 9; index++)
{
hashSet.Remove(board[currentRow][index]);
hashSet.Remove(board[index][currentCol]);
}
// small 3 x 3 matrix - one of 9 3 x 3 matrixes
var smallRow = currentRow / 3 * 3; // 0, 3, 6
var smallCol = currentCol / 3 * 3; // 0, 3, 6
for (int row = smallRow; row < smallRow + 3; row++)
{
for (int col = smallCol; col < smallCol + 3; col++)
{
hashSet.Remove(board[row][col]);
}
}
return hashSet;
}
}
}
