# A cool algorithm to check a Sudoku field?

asked Nov 14, 2008

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.

Best Regards,

Michael

answered Jan 14, 2008 by

Let's say int sudoku[0..8,0..8] is the sudoku field.

``````bool CheckSudoku(int[,] sudoku)
{
int flag = 0;

// Check rows
for(int row = 0; row < 9; row++)
{
flag = 0;
for (int col = 0; col < 9; col++)
{
// edited : check range step (see comments)
if ((sudoku[row, col] < 1)||(sudoku[row, col] > 9))
{
return false;
}

// if n-th bit is set.. but you can use a bool array for readability
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}

// set the n-th bit
flag |= (1 << sudoku[row, col]);
}
}

// Check columns
for(int col= 0; col < 9; col++)
{
flag = 0;
for (int row = 0; row < 9; row++)
{
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
flag |= (1 << sudoku[row, col]);
}
}

// Check 3x3 boxes
for(int box= 0; box < 9; box++)
{
flag = 0;
for (int ofs = 0; ofs < 9; ofs++)
{
int col = (box % 3) * 3;
int row = ((int)(box / 3)) * 3;

if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
flag |= (1 << sudoku[row, col]);
}
}
return true;
``````

}

answered Jan 14, 2008

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.

answered Jan 14, 2008 by

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.

answered Jan 14, 2008 by

You could extract all values in a set (row, column, box) into a list, sort it, then compare to '(1, 2, 3, 4, 5, 6, 7, 8, 9)

answered Jan 14, 2008
``````array = [1,2,3,4,5,6,7,8,9]
sudoku = int [][]
puzzle = 9 #9x9
columns = map []
units = map [] # box
unit_l = 3 # box width/height
check_puzzle()

def strike_numbers(line, line_num, columns, units, unit_l):
count = 0
for n in line:
# check which unit we're in
unit = ceil(n / unit_l) + ceil(line_num / unit_l) # this line is wrong - rushed
if units[unit].contains(n): #is n in unit already?
return columns, units, 1
if columns[count].contains(n): #is n in column already?
return columns, units, 1
line.remove(n) #remove num from temp row
return columns, units, line.length # was a number not eliminated?

def check_puzzle(columns, sudoku, puzzle, array, units):
for (i=0;i< puzzle;i++):
columns, units, left_over = strike_numbers(sudoku[i], i, columns, units) # iterate through rows
if (left_over > 0): return false
``````

Without thoroughly checking, off the top of my head, this should work (with a bit of debugging) while only looping twice. O(n^2) instead of O(3(n^2))

answered Jan 15, 2008

I did this once for a class project. I used a total of 27 sets to represent each row, column and box. I'd check the numbers as I added them to each set (each placement of a number causes the number to be added to 3 sets, a row, a column, and a box) to make sure the user only entered the digits 1-9. The only way a set could get filled is if it was properly filled with unique digits. If all 27 sets got filled, the puzzle was solved. Setting up the mappings from the user interface to the 27 sets was a bit tedious, but made the rest of the logic a breeze to implement.

answered Nov 14, 2008 by

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

answered Nov 14, 2008 by

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't 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.

answered Nov 14, 2008 by

Peter Norvig has a great article on solving sudoku puzzles (with python),

http://norvig.com/sudoku.html

Maybe it's too much for what you want to do, but it's a great read anyway

Create an array of booleans for every row, column, and square. The array's index represents the value that got placed into that row, column, or square. In other words, if you add a 5 to the second row, first column, you would set rows[2][5] to true, along with columns[1][5] and squares[4][5], to indicate that the row, column, and square now have a `5` value.