A cool algorithm to check a Sudoku field?

Question

Does anyone know a simple algorithm to check if a Sudoku-Configuration is valid? The simplest algorithm I came up with is (for a board of size n) in Pseudocode

for each row
  for each number k in 1..n
    if k is not in the row (using another for-loop)
      return not-a-solution

..do the same for each column

But I'm quite sure there must be a better (in the sense of more elegant) solution. Efficiency is quite unimportant.

Answer 1

You need to check for all the constraints of Sudoku :

• check the sum on each row
• check the sum on each column
• check for sum on each box
• check for duplicate numbers on each row
• check for duplicate numbers on each column
• check for duplicate numbers on each box

that's 6 checks altogether.. using a brute force approach.

Some sort of mathematical optimization can be used if you know the size of the board (ie 3x3 or 9x9)

Edit: explanation for the sum constraint: Checking for the sum first (and stoping if the sum is not 45) is much faster (and simpler) than checking for duplicates. It provides an easy way of discarding a wrong solution.

Answer 2

You can check if sudoku is solved, in these two similar ways:

• Check if the number is unique in each row, column and block.

A naive solution would be to iterate trough every square and check if the number is unique in the row, column block that number occupies.

But there is a better way.

• Sudoku is solved if every row, column and block contains a permutation of the numbers (1 trough 9)

This only requires to check every row, column and block, instead of doing that for every number. A simple implementation would be to have a bitfield of numbers 1 trough 9 and remove them when you iterate the columns, rows and blocks. If you try to remove a missing number or if the field isn't empty when you finish then sudoku isn't correctly solved.

Answer 3

Create cell sets, where each set contains 9 cells, and create sets for vertical columns, horizontal rows, and 3x3 squares.

Then for each cell, simply identify the sets it's part of and analyze those.

Answer 4

Just a thought: don't you need to also check the numbers in each 3x3 square?

I'm trying to figure out if it is possible to have the rows and columns conditions satisfied without having a correct sudoku

Answer 5

One minor optimization you can make is that you can check for duplicates in a row, column, or box in O(n) time rather than O(n^2): as you iterate through the set of numbers, you add each one to a hashset. Depending on the language, you may actually be able to use a true hashset, which is constant time lookup and insertion; then checking for duplicates can be done in the same step by seeing if the insertion was successful or not. It's a minor improvement in the code, but going from O(n^2) to O(n) is a significant optimization.

Answer 6

Let's assume that your board goes from 1 - n.

We'll create a verification array, fill it and then verify it.

grid [0-(n-1)][0-(n-1)]; //this is the input grid
//each verification takes n^2 bits, so three verifications gives us 3n^2
boolean VArray (3*n*n) //make sure this is initialized to false


for i = 0 to n
 for j = 0 to n
  /*
   each coordinate consists of three parts
   row/col/box start pos, index offset, val offset 
  */

  //to validate rows
  VArray( (0)     + (j*n)                             + (grid[i][j]-1) ) = 1
  //to validate cols
  VArray( (n*n)   + (i*n)                             + (grid[i][j]-1) ) = 1
  //to validate boxes
  VArray( (2*n*n) + (3*(floor (i/3)*n)+ floor(j/3)*n) + (grid[i][j]-1) ) = 1
 next    
next

if every array value is true then the solution is correct. 

I think that will do the trick, although i'm sure i made a couple of stupid mistakes in there. I might even have missed the boat entirely.