Check if a given grid is a valid Sudoku

Question

At CodeFights I found a question about the validity of Sudoku grid. Given a grid, return true if it is valid, return false otherwise. The grid is valid when each row, each column and each 3x3 sub grid contains at most one occurrence of the numbers 1 to 9.

I solved it using C# and I would like some feedback on my solution.

The provided grid is guaranteed to be 9x9 and to only contain the characters 1 through 9 and . (for empty cells). So I did not include any error checking.

Solution

using System;

public static class Program
{
    public static void Main()
    {
        char[][] grid = {
            new char[] {'.', '.', '.', '1', '4', '.', '.', '2', '.'}, 
            new char[] {'.', '.', '6', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '1', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '6', '7', '.', '.', '.', '.', '.', '9'},
            new char[] {'.', '.', '.', '.', '.', '.', '8', '1', '.'},
            new char[] {'.', '3', '.', '.', '.', '.', '.', '.', '6'},
            new char[] {'.', '.', '.', '.', '.', '7', '.', '.', '.'},
            new char[] {'.', '.', '.', '5', '.', '.', '.', '7', '.'}
        };

        var sudoku = new Sudoku(grid);
        Console.WriteLine(sudoku.IsValid());
    }
}

public class Sudoku
{
    char[][] _grid;

    public Sudoku(char[][] grid)
    {
        _grid = grid;
    }

    public bool IsValid()
    {
        return RowsAreValid() 
            && ColumnsAreValid() 
            && SquaresAreValid();
    }

    bool RowsAreValid()
    {
        return Validate(GetNumberFromRow);
    }

    bool ColumnsAreValid()
    {
        return Validate(GetNumberFromColumn);
    }

    bool SquaresAreValid()
    {
        return Validate(GetNumberFromSquare);
    }

    bool Validate(Func<int, int, int> numberGetter)
    {
        for (var row = 0; row < 9; row++)
        {
            var usedNumbers = new bool[10];
            for (var column = 0; column < 9; column++)
            {
                var number = numberGetter(row, column);
                if (number != 0 && usedNumbers[number] == true)
                {
                    return false;
                }

                usedNumbers[number] = true;
            }
        }

        return true;
    }

    int GetNumberFromRow(int row, int column)
    {
        return ToNumber(_grid[row][column]);
    }

    int GetNumberFromColumn(int row, int column)
    {
        return ToNumber(_grid[column][row]);
    }

    int GetNumberFromSquare(int block, int index)
    {
        var column = 3 * (block % 3) + index % 3;
        var row = index / 3 + 3 * (block / 3);
        return ToNumber(_grid[row][column]);
    }

    int ToNumber(char c)
    {
        if (c == '.')
            return 0;
        return (int)(c - '0');
    }
}

Answer 1

Nice use of Func

I don't like the use of row and column in Validate and that is not really what it is

Looks like you call GetNumberFromSquare more than you need to.

Consider a byte[,] ba = new byte[9, 9]; array and use 0 for blank.

A little more compact

public class Sudoku2
{
    byte[,] gridy = new byte[9, 9] { { 0, 0, 0, 1, 4, 0, 0, 2, 0 },
                                     { 0, 0, 6, 0, 0, 0, 0, 0, 0 },
                                     { 0, 0, 0, 0, 0, 6, 0, 0, 0 },
                                     { 0, 0, 1, 0, 0, 0, 0, 0, 0 },
                                     { 0, 6, 7, 0, 0, 0, 0, 0, 9 },
                                     { 0, 0, 0, 0, 0, 0, 8, 1, 0 },
                                     { 0, 3, 0, 0, 0, 0, 0, 0, 6 },
                                     { 5, 0, 0, 0, 0, 7, 0, 0, 0 },
                                     { 0, 0, 0, 5, 0, 0, 0, 7, 0 },
                                    };
    public bool Validate(byte[,] grid)
    {
        for (int i = 0; i < 9; i++)
        {
            bool[] row = new bool[10];
            bool[] col = new bool[10];

            for (int j = 0; j < 9; j++)
            {
                if(row[grid[i,j]] & grid[i, j] > 0)
                {
                    return false;
                }
                row[grid[i, j]] = true;

                if (col[grid[j, i]] & grid[j, i] > 0)
                {
                    return false;
                }
                col[grid[j, i]] = true;

                if ((i + 3) % 3 == 0 && (j + 3) % 3 == 0)
                {
                    bool[] sqr = new bool[10];
                    for (int m = i; m < i + 3; m++)
                    {
                        for (int n = j; n < j + 3; n++)
                        {
                            if (sqr[grid[m, n]] & grid[m, n] > 0)
                            {
                                return false;
                            }
                            sqr[grid[m, n]] = true;
                        }
                    }
                }

            }
        }
        return true;
    }

    public Sudoku2()
    {
        bool good = Validate(gridy);
    }
    public Sudoku2(byte[,] grid)
    {
        bool good = Validate(grid);
    }
}

Answer 2

Review

• The code is too granular.

  • You have functions that just call functions.

    For example

    public bool IsValid()
    {
        return RowsAreValid() 
            && ColumnsAreValid() 
            && SquaresAreValid();
    }
    

    can be

    public bool IsValid() {
        return Validate(GetNumberFromRow)
            && Validate(GetNumberFromColumn) 
            && Validate(GetNumberFromSquare);
    }
    

    without loss of readability and removing the 3 unneeded functions.

  • What the function ToNumber contains what can be written as a single expression. grid[y][x] == '.' ? 0 : (int) grid[y][x]; Is here a reason it should be a function? What advantage would it have?

• Converting cells to number every time you access a cell is inefficient. Rather do it once when the class Sudoku is instantiate.

• Avoid underscoring names in classes. Rather than use

  char[][] _grid;
  
  public Sudoku(char[][] grid)
  {
      _grid = grid;
  }
  

  Use the underscore for the arguments and that way you dont need the ugly _ when you use grid in Sudoku class.

  char[][] grid;
  public Sudoku(char[][] _grid) {
      grid = _grid;
  }
  

Keep code compact.

I am not a fan of open layouts and thus discourage styles that result in a large number of infer-able lines.

Avoid code noise by using short form of code when and where possible.

• Opening { can be inferred by indentation (some languages only use indentation).

• Using single line statements should ether stay as a single line or use code block delimitation {}. I encourage all statement blocks to be delimited event single line blocks.

• If order of processing is not important consider using while loops rather than for loops as while loops can take up a lot less space.

  NOTE the rewrite uses while (v-- > 0) { The -- only works as a post decrement (the test happens before the value is decremented) in this case, DO NOT use pre-decrement here.

• For simple statements use ternary operator ? for example your ToNumber function can contain a single line return c == '.' ? 0 : (int) c;

Design

• You can increase performance by using lookups and bit-fields (see rewrite)

• The rewrite stores the grid as a 1D array where each cell holds the bit representing the number. For example the number 2 is the second bit (0b10).

• Rows, columns, and squares are defined by offsets stored in arrays. This means that you don't need special functions to test rows, columns or squares. One function can test any shape provided by the offset array.

Rewrite

The rewrite is just an example and is written as a validator. It adds the validation when instantiated as public valid and as a bonus public complete is true if the board has been completed (add to show usefulness of bit-fields)

Note As the Sudoku board has a x,y mirror symmetry the rewrite uses while loops that count down to reduce code noise.

Note Bit positions do not really matter and to avoid the need to align bit positions with number all bits are one position above the number they represent (eg the second bit represents 1).

Note As the validation is a one time operation on the input the grid is not stored only the result of validation is held.

using System;
public static class Program {
    public static void Main() {
        char[][] grid = {
            new char[] {'.', '.', '.', '1', '4', '.', '.', '2', '.'}, 
            new char[] {'.', '.', '6', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '.', '1', '.', '.', '.', '.', '.', '.'},
            new char[] {'.', '6', '7', '.', '.', '.', '.', '.', '9'},
            new char[] {'.', '.', '.', '.', '.', '.', '8', '1', '.'},
            new char[] {'.', '3', '.', '.', '.', '.', '.', '.', '6'},
            new char[] {'.', '.', '.', '.', '.', '7', '.', '.', '.'},
            new char[] {'.', '.', '.', '5', '.', '.', '.', '7', '.'}
        };
        Console.WriteLine(new SudokuValidate(grid).valid);
    }
}

public class SudokuValidate {
    const int SIZE = 9;
    const int COMPLETE = 0b1111111110;
    static int[] offY = {0, 1, 2, 3, 4, 5, 6, 7, 8};         // off for offsets
    static int[] offX = {0, 9, 18, 27, 36, 45, 54, 63, 72};
    static int[] offSqr = {0, 1, 2, 9, 10, 11, 18, 19, 20};
    static int[] offCor = {0, 3, 6, 27, 30, 33, 54, 57, 60};  // cor of corner
    public bool valid = false;
    public bool complete = false;
    int completeCount = 0;

    public SudokuValidate(char[][] inGrid) {        
        int y = SIZE, i = 0;
        int[] grid = new int[SIZE * SIZE];
        while (y-- > 0) {
            int x = SIZE;
            while (x-- > 0) { 
                grid[i++] = inGrid[y][x] == '.' ? 0 : 1 << (int) inGrid[y][x]; 
            }
        }
        valid = Validate(grid);
        complete = completeCount == (3 * SIZE);
    }

    bool Validate(int[] grid) {
        var i = SIZE;
        while (i-- > 0) {
            if (!(ZoneOK(grid, offY[i],   offX) && 
                  ZoneOK(grid, offX[i],   offY) && 
                  ZoneOK(grid, offCor[i], offSqr))) { 
                return false; 
            }
        }
        return true;
    }

    bool ZoneOK(int[] grid, int cell, int[] offsets) {
        int i = 9, used = 0;
        while (i-- > 0) {
            var bit = grid[cell + offsets[i]];
            if ((used & bit) != 0) { return false; }
            used |= bit;
        }
        completeCount += (used & COMPLETE) == COMPLETE ? 1 : 0;
        return true;
    }
}