A valid Sudoku problem checks whether a given 9x9 grid adheres to the rules of Sudoku. The rules are:
- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the nine 3x3 subgrids must contain the digits 1-9 without repetition.
Here’s a simple implementation in C# that checks if a given Sudoku board is valid:
using System;
using System.Collections.Generic;
public class SudokuValidator
{
public static bool IsValidSudoku(char[][] board)
{
HashSet<string> seen = new HashSet<string>();
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
char num = board[i][j];
if (num != '.')
{
// Create a unique string for each number in its context
string rowKey = $"{num} in row {i}";
string colKey = $"{num} in col {j}";
string boxKey = $"{num} in box {i / 3}-{j / 3}";
// Check if we have seen this number in the same row, column or box
if (!seen.Add(rowKey) || !seen.Add(colKey) || !seen.Add(boxKey))
{
return false; // If we have seen it, it's invalid
}
}
}
}
return true; // If we pass all checks, the Sudoku is valid
}
public static void Main(string[] args)
{
char[][] board = new char[][]
{
new char[] { '5', '3', '.', '.', '7', '.', '.', '.', '.' },
new char[] { '6', '.', '.', '1', '9', '5', '.', '.', '.' },
new char[] { '.', '9', '8', '.', '.', '.', '.', '6', '.' },
new char[] { '8', '.', '.', '.', '6', '.', '.', '.', '3' },
new char[] { '4', '.', '.', '8', '.', '3', '.', '.', '1' },
new char[] { '7', '.', '.', '.', '2', '.', '.', '.', '6' },
new char[] { '.', '6', '.', '.', '.', '.', '2', '8', '.' },
new char[] { '.', '.', '.', '4', '1', '9', '.', '.', '5' },
new char[] { '.', '.', '.', '.', '8', '.', '.', '7', '9' }
};
bool isValid = IsValidSudoku(board);
Console.WriteLine($"The Sudoku board is valid: {isValid}");
}
}
Explanation
-
Data Structure:
- A
HashSet<string>
is used to keep track of the numbers we have seen in the current row, column, and 3x3 subgrid.
- A
-
Iterate Through the Board:
- We use two nested loops to go through each cell of the 9x9 board.
-
Check Each Cell:
- If a cell contains a number (not ‘.’), we create unique keys for that number based on its position: one for the row, one for the column, and one for the 3x3 box.
-
Validity Check:
- If adding any of these keys to the
HashSet
returnsfalse
, it means we’ve seen that number before in the same context, which violates Sudoku rules, and we returnfalse
.
- If adding any of these keys to the
-
Final Result:
- If we finish checking all cells without finding duplicates, we return
true
, indicating that the board is valid.
- If we finish checking all cells without finding duplicates, we return
Usage
- You can change the
board
variable to test different Sudoku configurations. The output will indicate whether the board is valid according to Sudoku rules.