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

Check each row, column and box such that it contains the numbers 1-9 each, with no duplicates. Most answers here already discuss this.

But how to do that efficiently? Answer: Use a loop like

result=0;
for each entry:
  result |= 1<<(value-1)
return (result==511);

Each number will set one bit of the result. If all 9 numbers are unique, the lowest 9 bits will be set. So the "check for duplicates" test is just a check that all 9 bits are set, which is the same as testing result==511. You need to do 27 of these checks.. one for each row, column, and box.

Answer 2

It would be very interesting to check if:

when the sum of each row/column/box equals n*(n+1)/2
and the product equals n!
with n = number of rows or columns

this suffices the rules of a sudoku. Because that would allow for an algorithm of O(n^2), summing and multiplying the correct cells.

Looking at n = 9, the sums should be 45, the products 362880.

You would do something like:

for i = 0 to n-1 do
  boxsum[i] := 0;
  colsum[i] := 0;
  rowsum[i] := 0;
  boxprod[i] := 1;
  colprod[i] := 1;
  rowprod[i] := 1;    
end;

for i = 0 to n-1 do
  for j = 0 to n-1 do
    box := (i div n^1/2) + (j div n^1/2)*n^1/2;
    boxsum[box] := boxsum[box] + cell[i,j];
    boxprod[box] := boxprod[box] * cell[i,j];
    colsum[i] := colsum[i] + cell[i,j];
    colprod[i] := colprod[i] * cell[i,j];
    rowsum[j] := colsum[j] + cell[i,j];
    rowprod[j] := colprod[j] * cell[i,j];
   end;
end;

for i = 0 to n-1 do
  if boxsum[i] <> 45
  or colsum[i] <> 45
  or rowsum[i] <> 45
  or boxprod[i] <> 362880
  or colprod[i] <> 362880
  or rowprod[i] <> 362880
   return false;

Answer 3

First, you would need to make a boolean, "correct". Then, make a for loop, as previously stated. The code for the loop and everything afterwards (in java) is as stated, where field is a 2D array with equal sides, col is another one with the same dimensions, and l is a 1D one:

for(int i=0; i<field.length(); i++){
    for(int j=0; j<field[i].length; j++){
        if(field[i][j]>9||field[i][j]<1){
            checking=false;
            break;
        }
        else{
            col[field[i].length()-j][i]=field[i][j];
        }
    }
}

I don't know the exact algorithim to check the 3x3 boxes, but you should check all the rows in field and col with "/*array name goes here*/[i].contains(1)&&/*array name goes here*/[i].contains(2)" (continues until you reach the length of a row) inside another for loop.

Answer 4

Some time ago, I wrote a sudoku checker that checks for duplicate number on each row, duplicate number on each column & duplicate number on each box. I would love it if someone could come up one with like a few lines of Linq code though.

char VerifySudoku(char grid[81])
{
    for (char r = 0; r < 9; ++r)
    {
        unsigned int bigFlags = 0;

        for (char c = 0; c < 9; ++c)
        {
            unsigned short buffer = r/3*3+c/3;

                        // check horizontally
            bitFlags |= 1 << (27-grid[(r<<3)+r+c]) 
                        // check vertically
                     |  1 << (18-grid[(c<<3)+c+r])
                        // check subgrids
                     |  1 << (9-grid[(buffer<<3)+buffer+r%3*3+c%3]);

        }

        if (bitFlags != 0x7ffffff)
            return 0; // invalid
    }

    return 1; // valid
}

Answer 5

if the sum and the multiplication of a row/col equals to the right number 45/362880

Answer 6

This is my solution in Python, I'm glad to see it's the shortest one yet :)

The code:

def check(sud):
    zippedsud = zip(*sud)

    boxedsud=[]
    for li,line in enumerate(sud):
        for box in range(3):
            if not li % 3: boxedsud.append([])    # build a new box every 3 lines
            boxedsud[box + li/3*3].extend(line[box*3:box*3+3])

    for li in range(9):
        if [x for x in [set(sud[li]), set(zippedsud[li]), set(boxedsud[li])] if x != set(range(1,10))]:
            return False
    return True  

And the execution:

sudoku=[
[7, 5, 1,  8, 4, 3,  9, 2, 6],
[8, 9, 3,  6, 2, 5,  1, 7, 4], 
[6, 4, 2,  1, 7, 9,  5, 8, 3],
[4, 2, 5,  3, 1, 6,  7, 9, 8],
[1, 7, 6,  9, 8, 2,  3, 4, 5],
[9, 3, 8,  7, 5, 4,  6, 1, 2],
[3, 6, 4,  2, 9, 7,  8, 5, 1],
[2, 8, 9,  5, 3, 1,  4, 6, 7],
[5, 1, 7,  4, 6, 8,  2, 3, 9]]

print check(sudoku)