Today I was scrolling HackerRank for some interesting problems to solve and I stumbled across something I thought could challenge me for an evening. The following is the description for the challenge:
Given a 9×9 grid with empty cells marked as 0, fill the grid so that each row, column, 3×3 block, and both main diagonals contain numbers 1 to 9 exactly once.
Once I realised the posted solutions were wrong and the test cases published were invalid, I found a nice cafe in North Vancouver (shout out 49th parallel for elite wifi!) and dug my teeth in to fix that.
To ensure I actually learn something, all was written by hand (as is the theme of things posted on my website)
Solution Overview
Lets start with the intuition behind my solution to give you an idea of what in general is happening at each step:
- Start with a sudoku grid state
- Update all internal sets that represents columns, rows, squares, and diagonals
- Find positions in the grid that have a missing value
- For a given position with a missing value, find all candidate values that could go there
- For each candidate, update the grid and repeat the process
graph LR
%% Node Definitions
Start(["Start: Sudoku Grid State (Input)"])
Step1["Update Internal Sets:<br>Rows, Columns, Squares, and Diagonals"]
Step2{"Found a<br>Position with<br>Missing Value?"}
SolvedGrid(["Sudoku Puzzle Solved / Success"])
GetPos["Get Position (i, j)"]
Step3["Find All Valid<br>Candidates for (i, j)"]
CheckCandidates{"Candidates<br>Exist?"}
Backtrack1(["Return Null"])
subgraph RecursiveCall["Loop"]
Step4["For Each candidate value at a given position:"]
RecursiveStep["Update Grid: <br>Grid[i, j] = candidate<br>2. Call solve(Updated Grid)"]
ResultCheck{"Did recursive<br>call find solution?"}
Reset["Continue Loop"]
end
%% Connections
Start --> Step1
Step1 --> Step2
Step2 -- No --> SolvedGrid
Step2 -- Yes --> GetPos
GetPos --> Step3
Step3 --> CheckCandidates
CheckCandidates -- No --> Backtrack1
CheckCandidates -- Yes --> Step4
Step4 --> RecursiveStep
RecursiveStep --> ResultCheck
RecursiveStep --> Start
ResultCheck -- No --> Reset
Reset --> Step4
%% Styling
classDef startEnd fill:#fff5cc,stroke:#d4b35e,stroke-width:1px;
classDef step fill:#cce5ff,stroke:#85a8cc,stroke-width:1px;
classDef decision fill:#d9f2d9,stroke:#90c290,stroke-width:1px;
class Start,SolvedGrid,Backtrack1,ReturnSuccess,ReturnFailure startEnd;
class Step1,GetPos,Step3,Step4,RecursiveStep,Reset step;
class Step2,CheckCandidates,ResultCheck decision;
style RecursiveCall fill:#f5e6fa,stroke:#c299cc,stroke-width:1px;
Helper Functions
Let’s start with some simple helper functions that solve small but important bits of this solution.
Square ID
Beginning with a function that maps a given position on a 9×9 grid to its corresponding “ID” on a 3×3 grid. All positions in the first 3×3 square in the top left of the 9×9 grid are given a square Id of ‘0’ and all the positions the last 3×3 square in the bottom right of the 9×9 grid are given a square ID of ‘8’:
static int getSquareId(int row, int col)
{
return (row / 3) * 3 + (col / 3);
}
Create sets from grid
We want to be able to search what number(s) from 1-9 are not present in at a location in our sudoku grid. My solution requires the rows, columns, squares, and diagonals to be in sets, because it lets us do a neat trick to solve this problem which I will explain further on. So I have a function that does this list to set conversion, noting that additionally, if a ‘0’ value is found, it adds this location to a list of missing values.
static (List<HashSet<int>> squares,
List<HashSet<int>> columns,
List<HashSet<int>> rows,
List<HashSet<int>> diagonals,
List<(int,int)> missingList)
createSetsFromGrid(List<List<int>> grid)
{
List<HashSet<int>> squares = new List<HashSet<int>>();
List<HashSet<int>> columns = new List<HashSet<int>>();
List<HashSet<int>> rows = new List<HashSet<int>>();
List<HashSet<int>> diagonals = new List<HashSet<int>>();
// 0 is leading diagonal
List<(int,int)> missingList = new List<(int,int)>();
// We initialise two hashsets for the two diagonals
diagonals.Add(new HashSet<int>());
diagonals.Add(new HashSet<int>());
// Iterate over each element, adding to respective set
for (int i = 0; i < grid.Count(); i ++)
{
List<int> row = grid[i];
rows.Add(row.ToHashSet());
for (int j = 0; j < grid.Count(); j++)
{
int element = row[j];
if (element == 0)
{
missingList.Add((i,j));
}
// will create 9 sets representing each column
if (i == 0)
{
columns.Add(new HashSet<int>());
}
columns[j].Add(element);
// Build the squares hashset
int squareSelection = getSquareId(i, j);
// will create 9 sets representing each 3x3 square
if (squareSelection >= squares.Count())
{
squares.Add(new HashSet<int>());
}
squares[squareSelection].Add(element);
// Adds value to diagonal
if (i == j) {
diagonals[0].Add(element);
}
if (i == 8 - j)
{
diagonals[1].Add(element);
}
}
}
return (squares, columns, rows, diagonals, missingList);
}
It’s important to note that a location is mapped to at minimum 3 sets, possibly 4 sets if it is on the diagonal. For example, position row = 0 and column = 8 will be mapped to the rows[0], columns[8], squares[2],diagonal[1].
Find Candidates
This is where the magic of our efforts to convert lists to sets pays off. To know what possible values can go on a missing square can be thought of by a Venn diagram. We start with all possible values for a spot (1-9) and remove options based on our columns, sets, rows, and (maybe) the diagonal.
If we subtract the union of all three sets on the left to the set of all values on the right, the remaining set of values meets our criteria of only being in a row, column, and square a single time. We can get this behaviour using the `ExceptWith` method on our sets.
HashSet<int> getCandidates(
List<HashSet<int>> squares,
List<HashSet<int>> columns,
List<HashSet<int>> rows,
List<HashSet<int>> diagonals,
int row, int col,
HashSet<int> cache = null)
{
int i = row;
int j = col;
HashSet<int> candidates = new HashSet<int>() {1, 2, 3, 4, 5, 6, 7, 8, 9};
// subtract rows, cols, squares from candidates set
candidates.ExceptWith(rows[i]);
candidates.ExceptWith(columns[j]);
candidates.ExceptWith(squares[getSquareId(i, j)]);
// only subtract diagonal set if value lies on diagonal
if (i == j) candidates.ExceptWith(diagonals[0]);
if (i == 8 - j) candidates.ExceptWith(diagonals[1]);
return candidates;
}
Note we only subtract the diagonal set if the position we are finding our candidates on lies on the leading or trailing diagonal.
Solve
With all our helper functions out the way, we can now start to solve the sudoku puzzle. The general loop is as follows:
- Use our helper function to create sets from a given grid state
- Get the position of an empty cell
- Use our helper function to find all candidates for the empty cell
- Iterate through each candidate, updating the grid with the value
- Call the solve method on the updated grid until a solution is found
List<List<int>>? solve(List<List<int>> grid, Dictionary<(int, int), HashSet<int>> cache)
{
(List<HashSet<int>> squares, List<HashSet<int>> columns, List<HashSet<int>> rows, List<HashSet<int>> diagonals, List<(int,int)> missingList) = createSetsFromGrid(grid);
// solution has been found
if (missingList.Count == 0) return grid;
// get position to find candidates for
(int i, int j) = missingList[0];
HashSet<int> candidates = getCandidates(squares,columns,rows,diagonals, i, j);
// If no candidates and there are missing values, return
if (candidates.Count == 0)
{
return null;
}
foreach (int candidate in candidates.AsEnumerable())
{
grid[i][j] = candidate;
List<List<int>>? candidateGrid = solve(grid, cache);
if (candidateGrid != null) return candidateGrid;
else continue;
}
// If no solutions have been found, reset the position
grid[i][j] = 0;
return null;
}
A few things to note:
- We can assume the grid is solved when there are no more missing values
- If execution reaches to a point where there are missing values but there are no candidates for a missing value, there is no solution to this ‘path’
Final solution
All together there is a reasonably fast way to solve a sudoku puzzle
public static List<List<int>> completeDiagonalSudokuGrid(List<List<int>> grid)
{
static int getSquareId(int row, int col)
{
return (row / 3) * 3 + (col / 3);
}
// Builds data structures and finds missing values
static (List<HashSet<int>> squares,
List<HashSet<int>> columns,
List<HashSet<int>> rows,
List<HashSet<int>> diagonals,
List<(int,int)> missingList)
createSetsFromGrid(List<List<int>> grid)
{
List<HashSet<int>> squares = new List<HashSet<int>>();
List<HashSet<int>> columns = new List<HashSet<int>>();
List<HashSet<int>> rows = new List<HashSet<int>>();
List<HashSet<int>> diagonals = new List<HashSet<int>>(); // 0 is leading diag
List<(int,int)> missingList = new List<(int,int)>();
// two hashsets for diagonal
diagonals.Add(new HashSet<int>());
diagonals.Add(new HashSet<int>());
for (int i = 0; i < grid.Count(); i ++)
{
List<int> row = grid[i];
rows.Add(row.ToHashSet());
for (int j = 0; j < grid.Count(); j++)
{
int element = row[j];
if (element == 0)
{
missingList.Add((i,j));
}
if (i == 0)
{
columns.Add(new HashSet<int>());
}
columns[j].Add(element);
// Build the squares hashset
int squareSelection = getSquareId(i, j);
if (squareSelection >= squares.Count())
{
squares.Add(new HashSet<int>());
}
squares[squareSelection].Add(element);
if (i == j) {
diagonals[0].Add(element);
}
if (i == 8 - j)
{
diagonals[1].Add(element);
}
}
}
return (squares, columns, rows, diagonals, missingList);
}
// build hashsets from input
// Gets candidates for a specific position on the grid
HashSet<int> getCandidates(
List<HashSet<int>> squares,
List<HashSet<int>> columns,
List<HashSet<int>> rows,
List<HashSet<int>> diagonals,
int row, int col)
{
int i = row;
int j = col;
HashSet<int> candidates = new HashSet<int>() {1, 2, 3, 4, 5, 6, 7, 8, 9};
candidates.ExceptWith(rows[i]);
candidates.ExceptWith(columns[j]);
candidates.ExceptWith(squares[getSquareId(i, j)]);
if (i == j) {
candidates.ExceptWith(diagonals[0]);
}
if (i == 8 - j)
{
candidates.ExceptWith(diagonals[1]);
}
return candidates;
}
List<List<int>>? solve(List<List<int>> grid)
{
(List<HashSet<int>> squares, List<HashSet<int>> columns, List<HashSet<int>> rows, List<HashSet<int>> diagonals, List<(int,int)> missingList) = createSetsFromGrid(grid);
if (missingList.Count == 0) return grid;
(int i, int j) = missingList[0];
HashSet<int> candidates = getCandidates(squares,columns,rows,diagonals, i, j);
if (candidates.Count == 0)
{
return null;
}
foreach (int candidate in candidates.AsEnumerable())
{
grid[i][j] = candidate;
List<List<int>>? candidateGrid = solve(grid);
if (candidateGrid != null) return candidateGrid;
else continue;
}
grid[i][j] = 0;
return null;
}
List<List<int>>? solvedGrid = solve(grid);
return solvedGrid;
}
}