Solution to Little Puzzlers–Validate a Sudoku Board

This is the way I went about the “Validate a Sudoku Board” problem. However, keep in mind there are multiple ways to solve this, so don’t worry if your solution has variations and it’s entirely possible there are more efficient ways.

Feel free to suggest your solution in the comments here or in the original post, but please be respectful of others’ efforts.

My Approach

This one is fairly straight-forward, your basic task is to make sure that the value of any given cell isn’t replicated in the cell’s row, column, or “cube”.  The problem is how you go about this.  There is a space-efficient way, but requires more looping, or there is a method that requires only visiting any cell one time, but requires extra space.

Given that the puzzle is fixed in size (9×9 grid), I’ll opt for better algorithmic complexity and use space to hold the set of all numbers seen for each given row, column, and cube.  By using 27 sets to hold these values (9 for the rows, 9 for the columns, 9 for the cubes), we can easily see if we’ve already seen the current number in the given row, column, or cube and immediately declare the puzzle invalid.

Of course, we could get even more space-efficient and use 27 BitArrays (or one large one partitioned, etc.), but then we lose the elegance of set logic.  I like keeping things logically simple and then optimizing for space after determining there is a need, so I’d probably opt to use Sets in my original answer in an evaluation, and then mention that if space were a concern, I would then optimize to BitArray.

So, here’s my solution:

1 : public class SudokuBoard
2 : {
  3 : private readonly char[,] board;
  4 : 5 :  // validate board is a 9x9 array
           6 : public SudokuBoard(char[,] board) 7 : {
    8 : if (board == null || board.GetLength(0) != 9 ||
            board.GetLength(1) != 9) 9 : {
      10 : throw new ArgumentException("Board is not valid size for Sudoku");
      11:
    }
    12 : 13 : this.board = board;
    14:
  }
  15 : 16 : public bool Validate() 17 : {
    18 :  // yes, i could use BitArray for space efficiency, but i like the
          // logical feel
          19
        :  // of the set and how it returns false on Add() if already there.
           20
        : var rows =
              Enumerable.Range(1, 9).Select(i => new HashSet<char>()).ToArray();
    21 : var columns =
             Enumerable.Range(1, 9).Select(i => new HashSet<char>()).ToArray();
    22 : var cubes =
             Enumerable.Range(1, 9).Select(i => new HashSet<char>()).ToArray();
    23 : 24 :  // process each cell only once
               25 : for (int row = 0; row < 9; ++row) 26 : {
      27 : for (int column = 0; column < 9; ++column) 28 : {
        29 : var current = board[row, column];
        30 : if (char.IsDigit(current)) 31 : {
          32 :  // determine which of the "cubes" the row/col fall in
                33 : var cube = 3 * (row / 3) + (column / 3);
          34 : 35 :  // if add to any set returns false, it was already there.
                     36
              : if (!rows[row].Add(current) || !columns[column].Add(current) ||
                    !cubes[cube].Add(current)) 37 : {
            38 : return false;
            39:
          }
          40:
        }
        41:
      }
      42:
    }
    43 : 44 : return true;
    45:
  }
  46:
}

Note that I’m not checking for invalid characters for the sake of brevity, though we could easily do this in the constructor, or in the Validate() method itself:

1 : var current = board[row, column];
2 : if (char.IsDigit(current)) 3 : {
  4 :  // blah blah blah
       5:
}
6 : else if (!char.IsWhiteSpace(current)) 7 : {
  8 : return false;
  9:
}

Finally, here’s a simple driver to illustrate usage:

1 : public static class Driver
2 : {
  3 : public static void Perform() 4 : {
    5 : var board = new char[9, 9] 6 : {
      7 : { '5', '3', ' ', ' ', '7', ' ', ' ', ' ', ' ' },
      8 : { '6', ' ', ' ', '1', '9', '5', ' ', ' ', ' ' },
      9 : { ' ', '9', '8', ' ', ' ', ' ', ' ', '6', ' ' },
      10 : { '8', ' ', '2', ' ', '6', ' ', ' ', ' ', '3' },
      11 : { '4', ' ', ' ', '8', ' ', '3', ' ', ' ', '1' },
      12 : { '7', ' ', ' ', ' ', '2', ' ', ' ', ' ', '6' },
      13 : { ' ', '6', ' ', ' ', ' ', ' ', '2', '8', ' ' },
      14 : { ' ', ' ', ' ', '4', '1', '9', ' ', ' ', '5' },
      15 : { ' ', ' ', ' ', ' ', '8', ' ', ' ', '7', '9' },
      16 :
    };
    17 : 18 : var validator = new SudokuBoard(board);
    19 : 20 : Console.WriteLine("The Sudoku board is " +
                                (validator.Validate() ? "valid" : "invalid"));
    21:
  }
  22:
}

Summary

Hope you had fun with this one!  Of course, I’m sure many out there can tweak the answer for performance in various ways – but you get the point.

Have a solution that worked for you but was totally different?  I’d love to hear about it!

Stay tuned next week for the next Little Puzzler.