I tested this algorithm on 9x9 boards and on average, if the board passed to the function is a (valid) solution, it takes 0.13-0.14 seconds for 1 million executions on my machine. I ran my code in Release mode in Visual Studio and timed it using Stopwatch
. I found the idea to use summing of all digits in rows, columns and square cells from another StackOverflow post on suggestions for making a sudoku validator. Note that I gave my code capabilities to work with perfect squares (perfect square is assumed in code) for the board size, where the size is assumed to be the same in all dimensions. I am also planning to build a sudoku solver in the near future.
The sudoku board validating function:
public static bool IsValidSudokuBoard(int[][] board)
{
int size = board.Length, cellSize = (int)Math.Sqrt(size), sumOfAllNums = (int)SumAllUpTo(size);
for (int row = 0; row < size; row++)
if (Sum(board[row]) != sumOfAllNums)
return false;
for (int column = 0; column < size; column++)
{
int columnSum = 0;
for (int row = 0; row < size; row++)
columnSum += board[row][column];
if (columnSum != sumOfAllNums)
return false;
}
for (int row = 0; row < size; row += cellSize)
for (int column = 0; column < size; column += cellSize)
{
int cellSum = 0;
for (int rowOffset = 0; rowOffset < cellSize; rowOffset++)
for (int columnOffset = 0; columnOffset < cellSize; columnOffset++)
cellSum += board[row + rowOffset][column + columnOffset];
if (cellSum != sumOfAllNums)
return false;
}
return true;
}
Where SumAllUpTo
is defined as follows:
public static double SumAllUpTo(double end, double start = 0d)
=> end * Math.Floor((end + 1d) / 2d) - ((start == 0d) ? 0d : SumAllUpTo(start));
And Sum
is defined as follows:
public static int Sum(this int[] array)
{
int result = 0;
for (int x = 0; x < array.Length; x++)
result += array[x];
return result;
}
Today (06.06.2021) I tested whether the function would run faster if it always assumed the board passed to it was of size 9x9, and it turns out that it is about twice as fast, with the same input. It is only 1.5x slower than looking up each element of a 9x9 board 1 million times. The resulting slowest time for the 9x9 only function is 0.063 seconds for 1 million executions.
public static bool IsValidSudokuBoard9x9(int[][] board)
{
for (int y = 0; y < 9; y++)
if (board[y][0] + board[y][1] + board[y][2] + board[y][3] + board[y][4] + board[y][5] + board[y][6]
+ board[y][7] + board[y][8] != 45)
return false;
for (int x = 0; x < 9; x++)
if (board[0][x] + board[1][x] + board[2][x] + board[3][x] + board[4][x] + board[5][x] + board[6][x]
+ board[7][x] + board[8][x] != 45)
return false;
for (int y = 0; y < 9; y += 3)
for (int x = 0; x < 9; x += 3)
if (board[y][x] + board[y][x + 1] + board[y][x + 2] + board[y + 1][x] + board[y + 1][x + 1]
+ board[y + 1][x + 2] + board[y + 2][x] + board[y + 2][x + 1] + board[y + 2][x + 2] != 45)
return false;
return true;
}
At this point, I could write each of the loops down by hand and remove them, but the code would be extremely messy and it wouldn't get faster than 0.04 seconds (time for 1 million full 9x9 board look-ups, for each element). I can now confidently say that I have one of the fastest 9x9 sudoku board validation algorithms out there in C#.