Validating if a Sudoku solution is valid

Posted on November 19th, 2012 by alfredo

I got this problem today has part of a conversation that I was having and thought I was interesting. Basically how can you in O( n ) validate that a 9×9 soduku is valid.

There are 3 rules that need to be followed for a validation to return true:

For each row there can only be and instance of each numbers.
For each column there can only be and instance of each numbers.
For each cluster of 9 there can only be and instance of the set of numbers.

The trivial solution that comes to mine is to go and count for each of this different conditions but that would require at least 3 passes tru the grid. For my solution i decided to just store a hashset for each of the conditions that need to be valid and stop on a negative. We use the numbers has distinct markers and not has numbers in particular since being number has no properties that help us. Solution is below:

using System.Collections.Generic;

namespace Algorithms
{
public class SudokuPuzzleValidator
{
readonly int[,] _board;

public SudokuPuzzleValidator():this(newint[9, 9])

{}

public SudokuPuzzleValidator(int[,] board)

{

_board = board;

}

public bool Validate()
{
const int integersInGame = 9;
var rowSet = new HashSet<int>[integersInGame];
InitializeSet(integersInGame, rowSet);
var columnSet = new HashSet<int>[integersInGame];
InitializeSet(integersInGame, columnSet);
var subGridSet = new HashSet<int>[integersInGame];
InitializeSet(integersInGame, subGridSet);

for (var row = 0; row < integersInGame; row++)
{
for (var column = 0; column < integersInGame; column++)
{
var cval = _board[row, column];
if (rowSet[row].Contains(cval))
{
return false;
}
rowSet[row].Add(cval);
if (columnSet[column].Contains(cval))
{
return false;
}
columnSet[column].Add(cval);
var subGridNumber = FigureOutSubGrid(row, column);
if (subGridSet[subGridNumber].Contains(cval))
{
return false;
}
subGridSet[subGridNumber].Add(cval);
}
}
return true;
}

private static void InitializeSet(int integersInGame, HashSet<int>[] rowSet)
{
for (var i = 0; i < integersInGame; i++)
{
rowSet[i] = new HashSet<int>();
}
}

private static int FigureOutSubGrid(int row, int column)
{
return column/3 + row/3*3;
}
}
}

Tags: programming

Categories: Personal project, Programming

2 Responses to 'Validating if a Sudoku solution is valid'

Pavel says:

November 20, 2012 at 5:00 pm

Refactor out the block

var cval = _board[row, column];
if (rowSet[row].Contains(cval))
{
return false;
}

And you will have a nicer code

I took a little bit different approach though. Validating the way you wrote down is handy but if you need to do it every time player enter the number – is not very convenient to start over again. I had a class that was SudokuCollection() it accepted the specific number of cells in it (no matter what the orientation) and had same checking mechanisms (ensure you have all numbers but no duplicates)

Another code review comment – your constructors:

public SudokuPuzzleValidator(): this (new int[9,9]){}

public SudokuPuzzleValidator(int[,] board)
{
_board = board;
}
alfredo says:

November 20, 2012 at 7:06 pm

Do actually not sure of how to refactor that specific block do you mean extract the method since the lofgic is similar and combine it into one if ? (If is that seems like i should try it).

I think the approach you suggest is better is you are building a game persay. This solution is only for the case in which you are just working on a prefilled board(completely full).
The other people on the table would call a function and past a linear array with 9 values which also works but it made you iterate over more times.

Will definetely edit the constructor comment.

alfredoalvarez.com

Validating if a Sudoku solution is valid

2 Responses to 'Validating if a Sudoku solution is valid'

Tags

Admin