.. is not difficult, but intriguing.
Usually solved with blind back tracking. But it felt soul-less. I want to solve like humans do.
Step 1: Solve each cell which can be guessed with 100% probability.
Step 2: Pick one of the available options and move to next.
Step 3: If nothing matches, back-track and change one of previous cells done in step 2. If reached start still nothing – no solution found.
The whole program is at https://github.com/chavakiranasdev/kichavaLibrary/blob/master/leet/hard/sudoku/Sudoku/Solution.cs
It is written and tested on Leetcode, so we ended up converting input to our object and reconverted back to required format.
CellState
/// <summary>
/// Represents state of single Cell.
/// </summary>
internal enum CellState
{
Empty, // Not yet filled.
InitialValue, // This value is already given
SolvedWithConfidence, // We found it with 100% probability.
InProgress, // Currently in progress.
}
CellLocation
/// <summary>
/// Represents a single cell location.
/// Used during backtracking to remember path
/// </summary>
internal class CellLocation
{
public int Row { set; get; }
public int Column { set; get; }
}Cell
/// <summary>
/// Represents a cell
/// </summary>
internal class Cell
{
public CellState State { get; set; }
public int CurrentValue { get; set; }
// We tried this number & it is not fit here.
// Used during backtracking to not re-use discarded values.
public List<int> NotFitForThisCell { get; set; }
public Cell()
{
State = CellState.Empty;
NotFitForThisCell = new List<int>();
}
public void Reset()
{
CurrentValue = 0;
State = CellState.Empty;
}
public void ClearNotFitForThis()
{
NotFitForThisCell.Clear();
}
}Find a match with 100% probability
// This checks if there is only one fit for this cell.
// If it finds more than one fit, then we return zero.
private int GetBestFit(int row, int column)
{
var gridKey = GetGridNumber(row, column);
var availableInAllThree = rowAvailableList[row].Intersect(columnAvailableList[column]).Intersect(gridAvailableList[gridKey]);
if (availableInAllThree.Count() == 1)
{
return availableInAllThree.First();
}
return 0;
}
Datastructures
// Constants
// we can generally solve sudoku of any size.
// So far, tested only for size 9
private int SizeOfSudoku { get; set; }
// Private variables.
// Later, we create a board of given size (e.g.. 9X9)
private Cell[,] cellBoard;
// Next three dictionaries (hash's) represent each row, column, grid and still available values at any instance.
// For example, once we initialize with input values, we remove them from corresponding row, column, grid.
// Instead of three hashe's we could use 9X9 hashes to do same for each cell. That should be good for perf, for now this what I used.
Dictionary<int, List<int>> rowAvailableList = new Dictionary<int, List<int>>();
Dictionary<int, List<int>> columnAvailableList = new Dictionary<int, List<int>>();
Dictionary<int, List<int>> gridAvailableList = new Dictionary<int, List<int>>();Constructor
public Solution(int sizeOfSudoku = 9)
{
SizeOfSudoku = sizeOfSudoku;
cellBoard = new Cell[SizeOfSudoku, SizeOfSudoku];
}Solution
public void SolveSudoku(char[][] board)
{
Console.WriteLine("Start...");
InitializeAllAvailableLiistsWithEverything();
// Initialize given char array into our cell array.
InitializeCellArray(board);
// First round - find all those which doesn't need guessing.
bool isAtleastOneBestFitFound;
int currentRow;
int currentColumn;
do
{
isAtleastOneBestFitFound = false;
// Solve each row.
currentRow = 0;
while (currentRow < SizeOfSudoku)
{
currentColumn = 0;
while (currentColumn < SizeOfSudoku)
{
if (cellBoard[currentRow, currentColumn].CurrentValue == 0)
{
var bestFit = GetBestFit(currentRow, currentColumn);
if (bestFit != 0)
{
// We have a match. Update the cell with this value.
isAtleastOneBestFitFound = true;
UpdateCellValue(currentRow, currentColumn, bestFit, CellState.SolvedWithConfidence);
}
}
currentColumn++;
}
currentRow++;
}
} while (isAtleastOneBestFitFound);
// Second round - Try to do best guess
bool response = true;
response = SolveByRow();
if (response == false)
{
Console.WriteLine("Bug: Unable to solve given Sudoku");
}
// we should be done now.
// Just put final result into char array instead of cell object array
for (int i = 0; i < SizeOfSudoku; i++)
{
for (int j = 0; j < SizeOfSudoku; j++)
{
board[i][j] = Convert.ToChar(cellBoard[i, j].CurrentValue + 48);
}
}
}SovleByRow
private bool SolveByRow()
{
bool response = true;
if (!SolveGivenSubBlock(rowStart: 0, rowEnd: SizeOfSudoku - 1, columnStart: 0, columnEnd: SizeOfSudoku - 1))
{
response = false;
Console.WriteLine("Bug? Unable to solve some of the grid");
}
return response;
}SolveGivenSubBlock
private bool SolveGivenSubBlock(int rowStart, int rowEnd, int columnStart, int columnEnd)
{
bool response = true;
for (int currentRow = rowStart; currentRow <= rowEnd; currentRow++)
{
for (int currentColumn = columnStart; currentColumn <= columnEnd; currentColumn++)
{
if (!SolveGivenCell(currentRow, currentColumn))
{
response = false; // do not overwrite this value for next cell's success, and thus above if
}
}
}
return response;
}SolveGivenCell
private bool SolveGivenCell(int currentRow, int currentColumn)
{
bool response = true;
var currentCell = cellBoard[currentRow, currentColumn];
if (currentCell.CurrentValue == 0)
{
// go back tracking.
// This will first attempt to find best guess if not found then back tracks.
if (!BackTrackRealThisTime(currentRow, currentColumn))
{
response = false;
Console.WriteLine($"Bug? Unable to solve {currentRow} :: {currentColumn}");
}
}
return response;
}Backtracking
private bool BackTrackRealThisTime(int currentRow, int currentColumn)
{
var stack = new Stack<CellLocation>();
// clear not fit for this, if any from prevous attempts.
cellBoard[currentRow, currentColumn].ClearNotFitForThis();
stack.Push(new CellLocation() { Row = currentRow, Column = currentColumn });
while (stack.Count != 0)
{
var currentTopOfStack = stack.Peek();
var bestGuess = GetBestGuess(currentTopOfStack.Row, currentTopOfStack.Column);
if (bestGuess != 0)
{
// We have a guess. Update the cell with this value.
UpdateCellValue(currentTopOfStack.Row, currentTopOfStack.Column, bestGuess, CellState.InProgress);
stack.Pop(); // Remove this from stack.
continue;
}
var previousCellLocation = GetPreviousInProgressCellLocation(currentTopOfStack);
// Push this cell onto stack after emptying it.;
var previousCell = cellBoard[previousCellLocation.Row, previousCellLocation.Column];
previousCell.NotFitForThisCell.Add(previousCell.CurrentValue);
RemoveCellValue(previousCellLocation.Row, previousCellLocation.Column);
// Now that we are moving further back, current cell's notfit is no longer valid.
cellBoard[currentTopOfStack.Row, currentTopOfStack.Column].ClearNotFitForThis();
stack.Push(previousCellLocation);
}
return true; // stack is empty
}Conclusion
I tried to be lazy and backtrack in random, without remembering path – but on my machine it works, leetcode always timed out. Forcing me to be a better 🙂
Get rest of the code from above github link.