James Michael Hare

# re: Little Puzzlers–Validate a Sudoku Board

"not to determine if the puzzle has a solution or is solvable."

Isn't this a requirement of testing whether the board has errors?

I mean it would be easy to test for obvious errors where they've got duplicate numbers on a row. The hard question is testing whether they've added any numbers that make the puzzle impossible to solve. I would think the only way to answer that is to know whether the puzzle is solvable in its current state?

# re: Little Puzzlers–Validate a Sudoku Board

@Rob: not necessarily for our purposes. I'm defining the puzzle in error as a mistake in the rules of Sudoku as the board stands. Sort of the difference between being syntactically correct but not making sense.

Obviously, solving the Sudoku puzzle to determine if a solution is possible would be harder, though interesting.

It's not so much an exercise in solving the puzzle, as writing an efficient means of determining if the puzzle is in error.

# Send Rakhi for Brother in Canada

The ritual of Raksha Bandhan, also known as Rakhi is the best way of showing your love and dedication towards your brother or sister. Send Rakhi Gifts to Canada to your sister or brother and shower them with your love and care. Send Rakhi to Canada from India to your loved ones and that too from the comfort of your home.

# re: Little Puzzlers–Validate a Sudoku Board

Looking for an efficient algorithm for a data structure based on chars is probably not the right approach. It'd be like looking for the optimal way to dig holes using a teaspoon..

# re: Little Puzzlers–Validate a Sudoku Board

internal sealed class Program
{
private static void Main()
{
var board = new char[9, 9]
{
{'5', '3', ' ', ' ', '7', ' ', ' ', ' ', '5'},
{'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'},
};

Console.WriteLine(Program.IsBoardValid(board));
Console.ReadKey();
}

private static bool IsBoardValid(char[,] board)
{
// Build a list of all 27 number sets (9 rows, 9 columns, and 9 3x3 blocks).
var sets = new List<IEnumerable<char>>(27);
for (int row = 0; row < 9; row++) sets.Add(Program.RowSet(board, row));
for (int col = 0; col < 9; col++) sets.Add(Program.ColumnSet(board, col));
for (int row = 0; row < 9; row += 3)
{
for (int col = 0; col < 9; col += 3)
{
sets.Add(Program.BlockSet(board, row, col));
}
}

// Return whether all 27 number sets are valid.
return sets.Aggregate(true, (areAllSetsValid, set) => areAllSetsValid && Program.IsSetValid(set));
}

// Enumerates the 9 cells in a single row of a board.
private static IEnumerable<char> RowSet(char[,] board, int row)
{
for (int columnIndex = 0; columnIndex < 9; columnIndex++) yield return board[row, columnIndex];
}

// Enumerates the 9 cells in a single column of a board.
private static IEnumerable<char> ColumnSet(char[,] board, int column)
{
for (int rowIndex = 0; rowIndex < 9; rowIndex++) yield return board[rowIndex, column];
}

// Enumerates the 9 cells in a single 3x3 block of a board.
private static IEnumerable<char> BlockSet(char[,] board, int row, int column)
{
for (int rowIndex = 0; rowIndex < 3; rowIndex++)
{
for (int columnIndex = 0; columnIndex < 3; columnIndex++)
{
yield return board[row + rowIndex, column + columnIndex];
}
}
}

private static bool IsSetValid(IEnumerable<char> set)
{
IEnumerable<char> populatedCells = set.Where(cell => cell != ' ');
return populatedCells.Count() == populatedCells.Distinct().Count();
}
}

# re: Little Puzzlers–Validate a Sudoku Board

@Robert: I like it!

# re: Little Puzzlers–Validate a Sudoku Board

@Morten: why? yes data structures have some overhead when storing char, but there are many ways to solve the puzzle algorithmicly, and not all are the same efficiency.

I'm not asking for the optimal in terms of space (in which case you could easily get by with some bit flipping), but for an efficient algorithm for scanning the board.

# re: Little Puzzlers–Validate a Sudoku Board

@Robert:

> return populatedCells.Count() == populatedCells.Distinct().Count();

Clever!

# re: Little Puzzlers–Validate a Sudoku Board

@Robert:

Admittedly, I'm a VB.NET guy, not a C# guy, but wouldn't using .All() instead of .Aggregate() be marginally more efficient, in that it'll short-circuit the enumeration itself once it finds an invalid set?

> // Return whether all 27 number sets are valid.
> return sets.Aggregate(true, (areAllSetsValid, set) => areAllSetsValid && Program.IsSetValid(set));

...could be:

return sets.All(Program.IsSetValid);

# re: Little Puzzlers–Validate a Sudoku Board

My own unoptimized Functional-style solution without for loops:

http://pastebin.com/SkBh9xuw