1
\$\begingroup\$

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');
    }
}
\$\endgroup\$
  • \$\begingroup\$ I added a little explanation. \$\endgroup\$ – venerik Jul 13 '17 at 21:16
  • 1
    \$\begingroup\$ Each column, row and sub grid can contain at most one occurrence of each of the numbers 1 to 9. So, all empty cells is ok. \$\endgroup\$ – venerik Jul 14 '17 at 6:53
1
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for your feedback and your solution. I agree on the row and column part. But coming up with a good name is quite hard in this case. The grid is defined as an array of arrays of chars by the CodeFights challenge. Otherwise I would certainly have picked an 2-dimensional array of ints as you did. I know the problem could have been solved with one pass through the grid but I chose clarity (of code) over speed. Maybe I'll try to work out a clear 1 pass solution in the future. \$\endgroup\$ – venerik Jul 13 '17 at 21:23
  • \$\begingroup\$ Uh i and j. I don't think you code is more clear. \$\endgroup\$ – paparazzo Jul 14 '17 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.