Solution to Little Puzzlers–Validate a Sudoku Board

<< Little Puzzlers–Validate a Sudoku Board | Home | C#/.NET Little Wonders: Null Conditional Operator in C# 6 >>

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 (9x9 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:         {

            throw new ArgumentException("Board is not valid size for Sudoku");

        }

  

        this.board = board;

    }

  

    public bool Validate()

    {

        // yes, i could use BitArray for space efficiency, but i like the logical feel

        // of the set and how it returns false on Add() if already there.

        var rows = Enumerable.Range(1, 9).Select(i => new HashSet<char>()).ToArray();

        var columns = Enumerable.Range(1, 9).Select(i => new HashSet<char>()).ToArray();

        var cubes = Enumerable.Range(1, 9).Select(i => new HashSet<char>()).ToArray();

  

        // process each cell only once

        for (int row = 0; row < 9; ++row)

        {

            for (int column = 0; column < 9; ++column)

            {

                var current = board[row, column];

                if (char.IsDigit(current))

                {

                    // determine which of the "cubes" the row/col fall in

                    var cube = 3 * (row / 3) + (column / 3);

  

                    // if add to any set returns false, it was already there.

                    if (!rows[row].Add(current) || !columns[column].Add(current) || !cubes[cube].Add(current))

                    {

                        return false;

                    }

                }

            }

        }

  

        return true;

    }

}

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.

Share This Post:
Short Url: http://wblo.gs/gdy

Print | posted on Wednesday, June 3, 2015 2:52 AM |

Feedback

# re: Solution to Little Puzzlers–Validate a Sudoku Board

This solution was a lot cleaner than mine. I need to remember to use what the framework already gives me instead of re-inventing the wheel.

6/3/2015 6:54 AM | Tyler Palesano

# re: Solution to Little Puzzlers–Validate a Sudoku Board

Wow. I barely understand what you did there but it looks pretty cool and clean. I'm a beginner and I made the puzzle in 170+ lines. This is going to be helpful to improve and understand new methods and ways to reach a solution to this kind of problems.

Regards.

(PD: I'll take your code to analyze it :))

6/3/2015 11:04 AM | J. M.

# re: Solution to Little Puzzlers–Validate a Sudoku Board

Looks like I was on the right track when using HashSet.Add() to check for duplicates and Enumerable.Range to build the collections, but in my fervor to eliminate For loops, I ended up needing to iterate over the source array multiple times, when you're only iterating over it once.

Very clean!

6/3/2015 11:36 AM | Mike C

# re: Solution to Little Puzzlers–Validate a Sudoku Board

I just try to lear F# with this puzzle.

Here is my solution:

let filterEmpty (list:List<char>) = List.filter (fun x -> x <> ' ') list

let distinct (list:List<char>) = List.ofSeq (query {
for n in list do
distinct
})

let isOk (list:List<char>) =
let filtered = filterEmpty list
if (filtered = (distinct filtered))
then true
else false

let getColumn (list:List<List<char>>) n = List.map (fun (x:List<char>) -> x.[n]) list
let getPart (list:List<List<char>>) getFunc = List.map (fun x -> getFunc list x) [0..8]
let getSquare (list:List<List<char>>) n = [list.[(n/3)*3].[(n%3)*3]; list.[(n/3)*3].[(n%3)*3+1]; list.[(n/3)*3].[(n%3)*3+2]; list.[(n/3)*3+1].[(n%3)*3]; list.[(n/3)*3+1].[(n%3)*3+1]; list.[(n/3)*3+1].[(n%3)*3+2]; list.[(n/3)*3+2].[(n%3)*3]; list.[(n/3)*3+2].[(n%3)*3+1]; list.[(n/3)*3+2].[(n%3)*3+2]; ]

let rec checkRows x = match x with | [] -> true | head :: tail -> (isOk head) && (checkRows tail)
let checkPart (input:List<List<char>>) getFunc = checkRows (getPart input getFunc)
let checkColumns (input:List<List<char>>) = checkPart input getColumn
let checkSquares (input:List<List<char>>) = checkPart input getSquare
let checkSudoku (input:List<List<char>>) = checkRows input && checkColumns input && checkSquares input

let board = [['5'; '3'; ' '; ' '; '7'; ' '; ' '; ' '; ' '];['6'; ' '; ' '; '1'; '9'; '5'; ' '; ' '; ' '];[' '; '9'; '8'; ' '; ' '; ' '; ' '; '6'; ' '];['8'; ' '; ' '; ' '; '6'; ' '; ' '; ' '; '3'];['4'; ' '; ' '; '8'; ' '; '3'; ' '; ' '; '1'];['7'; ' '; ' '; ' '; '2'; ' '; ' '; ' '; '6'];[' '; '6'; ' '; ' '; ' '; ' '; '2'; '8'; ' '];[' '; ' '; ' '; '4'; '1'; '9'; ' '; ' '; '5'];[' '; ' '; ' '; ' '; '8'; ' '; ' '; '7'; '9'];]
checkSudoku board

6/4/2015 1:06 AM | Vaclav Pachta

James Michael Hare

My Links

News

Blogs I Read

Tag Cloud

Article Categories

Archives

Post Categories

.NET

CSharp

Little Wonders

Little Wonders

vNext

Solution to Little Puzzlers–Validate a Sudoku Board

My Approach

Summary

Feedback

# re: Solution to Little Puzzlers–Validate a Sudoku Board

# re: Solution to Little Puzzlers–Validate a Sudoku Board

# re: Solution to Little Puzzlers–Validate a Sudoku Board

# re: Solution to Little Puzzlers–Validate a Sudoku Board