Possible speed improvements for a Sudoku board validation algorithm?

Question

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#.

• user985366: Why do you want to make this faster? Why run it a million times? It should be good to run one time on a given puzzle and "validate" -> answer if it's a correct solution or not? If you're practicing/learning programming, I think you'd gain more from moving on to solving another problem rather than optimize something that has no use being optimized.
• Rainer P.: A sudoku validator may become the core of a sudoku solver, which uses random moves with backtracking and calls the validator millions of times. Optimizing the validator for speed is useful. (@user985366)
• user555045: A Sudoku solver should not be based on full-board validation though: it should backtrack as early as possible (that's not a small trick: it saves an exponential amount of work to prune a whole sub-tree of the recursion). This trick with the sums actually doesn't work for partially-filled boards. Of course we can still review this.
• user555045: Actually on second thought it doesn't really work for a full board either: it could be full of fives and pass the test
• iSR5: you focused on the total sum, but you've forgot to check the uniqueness of numbers. You probably need to see Sudoku rules before you go further. masteringsudoku.com/sudoku-rules-beginners

Answer 1

As it was stated by @harold and @iSR5 your current implementation is not bullet-proof. I will not repeat their suggestions.

Rather I want to show you how to reduce repetition.
So, let me share with you my revised version for IsValidSudokuBoard9x9 then I will explain it:

public static bool IsValidSudokuBoard9x9New(int[][] board)
{
 const byte numberOfRows = 9, numberOfColumns = numberOfRows, fullFilledRowOrColumn = 45;
 byte rowMaxIdx = numberOfRows - 1;
 for (byte row = 0; row < numberOfRows; row++)
 if (board[row][0..rowMaxIdx].Sum() != fullFilledRowOrColumn)
 return false;
 byte columnMaxIdx = numberOfColumns - 1;
 for (byte column = 0; column < numberOfColumns; column++)
 if (board[0..columnMaxIdx][column].Sum() != fullFilledRowOrColumn)
 return false;
 for (byte row = 0; row < numberOfRows; row += 3)
 for (byte column = 0; column < numberOfColumns; column += 3)
 {
 columnMaxIdx = (byte)(column + 2);
 rowMaxIdx = (byte)(row + 2);
 if (board[row..rowMaxIdx][column..columnMaxIdx].SelectMany(item => item).Sum() != fullFilledRowOrColumn)
 return false;
 }
 return true;
}

• Rather than repeating 9 over and over again
  • I would suggest to introduce constants with meaningful names like numberOfRows, numberOfColumns
• I would suggest to use row and column variable names instead of x and y in your loops
• I would encourage you to use C# 8's Range and Index feature rather than accessing each element one by one
  • board[row][0..rowMaxIdx]: this will return an IEnumerable<int> on which you can simply call the Sum LINQ operator
  • board[0..columnMaxIdx][column]: it works in the same way as the previous one
  • board[row..rowMaxIdx][column..columnMaxIdx]: this will return an int[][] so first we need to flatten it (reduces its dimensions from 2 to 1) with SelectMany then we can issue the same Sum operator just like before
• Finally a minor thing I've used byte for indexing rather than int because we know that the max index fits into that range

---

Other suggestions:

• I would suggest to consider the usage of GetLength to retrieve the length of each dimension of the board dynamically
  • It gives you the ability to write generic code that can handle other boards than 9x9, for example 5x5 without any code change
• I would also suggest to consider the usage of multidimensional array int[,] instead of jagged array int[][]
  • With the latter one each row can have different number of columns, but we do know that each row should have exactly the same number of columns
• Last but not least, I would suggest to extract each kind of validation into a separate method
  • This will drastically reduce the complexity of each method

Answer 2

Nice work building a very fast Sudoko validator. As others have mentioned, getting beyond the hard-coded size will take some tweaking.

If I were writing a Sudoko solver (and the requisite validator), I'd probably start with the object model before the algorithms.

So, I started thinking about the classes I might implement and sketched out some high-level ideas. In case you decide to flesh out the object model and want to compare notes, here they are. Please note this is pseudo-code.

public class Cell 
{
 public int Value { get; private set; } 
 public int X { get; private set; }
 public int Y { get; private set; } 
 public Set Row { get; private set; }
 public Set Column { get; private set; }
 public Set Box { get; private set; }
}
public class Set //A row, column, or box
{
 public List<Cell> Cells { get; private set; } 
 public bool IsValid() => //check validity - i.e. contains each number only once
}
public class Collection //All rows or all columns or all boxes
{
 public List<Set> Items {get; private set;}
 public bool AreValid() => Items.All(i => i.IsValid());
}
public class Board 
{
 public int Size {get; private set;}
 
 public Collection Rows { get; private set; }
 public Collection Columns { get; private set; }
 public Collection Boxes {get; private set;}
 
 public Board(int size) => Size = size;
 
 public void Generate()
 {
 Rows = new Collection();
 Columns = new Collection();
 Boxes = new Collection();
 Enumerable.Range(1, size).ToList().ForEach(x =>
 { 
 Enumerable.Range(1, size).ToList().ForEach(y => 
 {
 ///generate cells, rows, columns, boxes, 
 //add to collections
 });
 });
 } 
 
 public bool IsValid() => 
 Rows.AreValid() && Columns.AreValid() && Boxes.AreValid();
}
static void Main()
{
 var board = new Board(9);
 board.Generate();
 var isValid = board.IsValid();
}