25

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.

1
  • Add to all of the algorithms here: check that no numbers are higher than your number of squares-on-a-side. Oct 13, 2009 at 18:04

25 Answers 25

25

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.

13
  • 16
    Sudoku doesn't involve sums.
    – cjm
    Nov 14, 2008 at 19:12
  • 14
    The sum of any row or column will be the same ie 1+2+3+4+5+6+7+8+9 = 45 and the dupe checks are because 45 can be reached in other ways if there are duplicates. The rules above ARE the constraints required to get a valid configuration. Feb 23, 2009 at 22:18
  • 25
    This answer is wrong. The sum constraints are unnecessary, because there is no way to obtain a sum of 45 in any other way without violating one of the 3 actual constraints.
    – sykora
    Apr 29, 2009 at 9:21
  • 24
    Checking for the sum beforehand may give better performance than just a naive duplicate check, but it is not a requirement. Checking for duplicates is sufficient.
    – Svante
    Apr 29, 2009 at 9:25
  • 13
    Checking for the sum first (and stoping if the sum is not 45) is much faster than checking for duplicates. Can people who skipped math clases stop downvoting this please?
    – Radu094
    May 14, 2009 at 13:19
25

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

https://norvig.com/sudoku.html

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

2
  • 10
    solving and checking are two different things, no?
    – ckarbass
    Sep 16, 2011 at 22:40
  • To anyone coming across this post: Kindly note that the question is asking for a recommendation.
    – fcdt
    Oct 21, 2020 at 8:39
10

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.

7

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

3
  • 3
    I don't now whether this is true: first row 1..9, second row 2..9,1, third 3..9,1,2 ... will lead to correct rows and columns, but not 3x3 squares. Or do I miss something here? Nov 14, 2008 at 9:25
  • 1
    @malach: You're absolutely right. Without the box constraint, it is a latin square. The set of valid, completed sudoku of a size is therefore a subset of all latin squares of that size. For example, the 4x4 grid with rows [1234][2143][3412][4321] is a latin square, but not a valid 2x2 sudoku. Nov 14, 2008 at 10:08
  • You do need to check all three (rows, columns, and boxes). Nov 15, 2008 at 3:01
5

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)        
2
  • If you have any improvements or questions feel free to comment!
    – Kami
    Apr 4, 2011 at 12:00
  • For python 3 use list(zip(**)) Oct 15, 2020 at 15:33
4

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.

Regardless of how your original board is being represented, this can be a simple and very fast way to check it for completeness and correctness. Simply take the numbers in the order that they appear on the board, and begin building this data structure. As you place numbers in the board, it becomes a O(1) operation to determine whether any values are being duplicated in a given row, column, or square. (You'll also want to check that each value is a legitimate number: if they give you a blank or a too-high number, you know that the board is not complete.) When you get to the end of the board, you'll know that all the values are correct, and there is no more checking required.

Someone also pointed out that you can use any form of Set to do this. Arrays arranged in this manner are just a particularly lightweight and performant form of a Set that works well for a small, consecutive, fixed set of numbers. If you know the size of your board, you could also choose to do bit-masking, but that's probably a little overly tedious considering that efficiency isn't that big a deal to you.

6
  • Its a bit unclear how you populate the squares (the rows and columns seem obvious enough). Are you treating it as a 9x9 matrix with each 3x3 square laid out as a single row? That can't possibly be right, can it? Aug 20, 2014 at 16:47
  • @JoranBeasley: Do you understand how StriplingWarrior envisages the squares? Aug 20, 2014 at 16:48
  • @Dilip: In sudoku, each 3x3 square can only have a value occur once. So if you assign an index to each of those 3x3 squares, then you can check whether a given square already has a number in it by finding the array at that index, and then finding the boolean that corresponds to the number you're checking. It doesn't matter how you calculate the index of each 3x3 square--top-down, left-right, whatever--as long as you're consistent. Aug 20, 2014 at 18:57
  • This is probably not appropriate for Op, but it is the answer I came here looking for.
    – Tyler
    Oct 19, 2017 at 23:11
  • 1
    @StriplingWarrior It seems like he wants the simplest, easiest to read algorithm which in my opinion would be iterating through each group (row, column, box). I was trying to find a more efficient algorithm, as more of a comp sci exercise than an actual implementation. This actually ends up being pretty readable which is an added bonus.
    – Tyler
    Oct 23, 2017 at 15:19
2

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.

1
  • This is how I've written it in the past. Apr 29, 2009 at 12:49
2

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)

0
2

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.

1

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;
2
  • 3
    It would be a great solution.. sadly the prime factors can be rearranged to trick it.. for example the sequence: 4 4 4 9 5 7 9 2 1 has sum 45 and product 9!
    – Marco M.
    Nov 14, 2008 at 10:25
  • 1
    marco, ha, I wrote a test program to check it as well, and was about to triumphantly post a counterexample, but you beat me. I should read the comments before jumping in!
    – SPWorley
    Apr 29, 2009 at 12:35
1

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
}
1

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

1
  • 5
    As Marco M. mentions on another comment: "the prime factors can be rearranged to trick it.. for example the sequence: 4 4 4 9 5 7 9 2 1 has sum 45 and product 9!"
    – Ryan
    Nov 6, 2012 at 22:28
1

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.

1
def solution(board):
    for i in board:
        if sum(i) != 45:
            return "Incorrect"

    for i in range(9):
        temp2 = []
        for x in range(9):
            temp2.append(board[i][x])

        if sum(temp2) != 45:
            return "Incorrect"

    return "Correct"

board = []
for i in range(9):
    inp = raw_input()
    temp = [int(i) for i in inp]
    board.append(temp)

print solution(board)

1
  • This needs to be temp2.append(board[x][i]) otherwise, it could get some incorrect I think, or? Oct 15, 2020 at 15:51
1

Here's a nice readable approach in Python:

from itertools import chain                                                                                            

def valid(puzzle):                                                                                                     
    def get_block(x,y):                                                                                                
        return chain(*[puzzle[i][3*x:3*x+3] for i in range(3*y, 3*y+3)])                                               
    rows = [set(row) for row in puzzle]                                                                                
    columns = [set(column) for column in zip(*puzzle)]                                                                 
    blocks = [set(get_block(x,y)) for x in range(0,3) for y in range(0,3)]                                             
    return all(map(lambda s: s == set([1,2,3,4,5,6,7,8,9]), rows + columns + blocks))         

Each 3x3 square is referred to as a block, and there are 9 of them in a 3x3 grid. It is assumed as the puzzle is input as a list of list, with each inner list being a row.

0

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;

}

3
  • If somebody would enter a value that is not valid (e.g. 0 or 10), this algorithm would still evaluate to true. Just being picky :-) Could be fixed by one more test at the end of each inner loop: flag xor 0x1FF = 0 Nov 14, 2008 at 10:19
  • To be true that would also not work for values > 31.. I think value range for the entire sudoku should be a separate step.
    – Marco M.
    Nov 14, 2008 at 10:26
  • 2
    You can't say O(3(n^2)) being better or worse than O(n^2) without considering the implementation of the single operations and the architecture it runs on; it's the same complexity class. You have to check 3*n^2 data. If you do in one big loop or in three smaller ones, it's the same.
    – Marco M.
    Nov 19, 2008 at 12:03
0

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.

0
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
        units[unit].add(n)
        if columns[count].contains(n): #is n in column already?
            return columns, units, 1
        columns[count].add(n)
        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))

2
  • if I am not mistaken O(n^2) == O(3(n^2))?
    – Kami
    Apr 21, 2011 at 22:00
  • @Kami You are not mistaken. I don't even remember writing this answer. If I had my time again I'd take a totally different approach. Funny how much you can learn in 2 and a bit years :P Apr 22, 2011 at 2:34
0

Here is paper by math professor J.F. Crook: A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles

This paper was published in April 2009 and it got lots of publicity as definite Sudoku solution (check google for "J.F.Crook Sudoku" ).

Besides algorithm, there is also a mathematical proof that algorithm works (professor admitted that he does not find Sudoku very interesting, so he threw some math in paper to make it more fun).

0

I'd write an interface that has functions that receive the sudoku field and returns true/false if it's a solution. Then implement the constraints as single validation classes per constraint.

To verify just iterate through all constraint classes and when all pass the sudoku is correct. To speedup put the ones that most likely fail to the front and stop in the first result that points to invalid field.

Pretty generic pattern. ;-)

You can of course enhance this to provide hints which field is presumably wrong and so on.

First constraint, just check if all fields are filled out. (Simple loop) Second check if all numbers are in each block (nested loops) Third check for complete rows and columns (almost same procedure as above but different access scheme)

0

Here is mine in C. Only pass each square once.

int checkSudoku(int board[]) {
  int i;
  int check[13] = { 0 };

  for (i = 0; i < 81; i++) {
    if (i % 9 == 0) {
      check[9] = 0;
      if (i % 27 == 0) {
        check[10] = 0;
        check[11] = 0;
        check[12] = 0;
      }
    }

    if (check[i % 9] & (1 << board[i])) {
      return 0;
    }
    check[i % 9] |= (1 << board[i]);

    if (check[9] & (1 << board[i])) {
      return 0;
    }
    check[9] |= (1 << board[i]);

    if (i % 9 < 3) {
      if (check[10] & (1 << board[i])) {
        return 0;
      }
      check[10] |= (1 << board[i]);
    } else if (i % 9 < 6) {
      if (check[11] & (1 << board[i])) {
        return 0;
      }
      check[11] |= (1 << board[i]);
    } else {
      if (check[12] & (1 << board[i])) {
        return 0;
      }
      check[12] |= (1 << board[i]);
    }
  }
}
0

Here is what I just did for this:

boolean checkers=true;
String checking="";
    if(a.length/3==1){}
    else{
       for(int l=1; l<a.length/3; l++){
            for(int n=0;n<3*l;n++){
                for(int lm=1; lm<a[n].length/3; lm++){
                    for(int m=0;m<3*l;m++){
                    System.out.print("    "+a[n][m]);
                    if(a[n][m]<=0){
                    System.out.print("        (Values must be positive!)        ");
                    }
                    if(n==0){
                        if(m!=0){
                        checking+=", "+a[n][m];
                    }
                    else{
                        checking+=a[n][m];
                    }
                }
                else{
                    checking+=", "+a[n][m];
                }
            }
                    }
            System.out.print("        "+checking);
            System.out.println();
                }
       }
            for (int i=1;i<=a.length*a[1].length;i++){
        if(checking.contains(Integer.toString(i))){

        }
        else{
            checkers=false;
        }
            }
        }
    checkers=checkCol(a);
    if(checking.contains("-")&&!checking.contains("--")){
        checkers=false;
    }
    System.out.println();
    if(checkers==true){
        System.out.println("This is correct! YAY!");
    }
    else{
        System.out.println("Sorry, it's not right. :-(");
    }
}
private static boolean checkCol(int[][]a){
    boolean checkers=true;
    int[][]col=new int[][]{{0,0,0},{0,0,0},{0,0,0}};
    for(int i=0; i<a.length; i++){
        for(int j=0; j<a[i].length; j++){
            if(a[i][j]>9||a[i][j]<1){
                checkers=false;
                break;
            }
            else{
                col[a[i].length-j][i]=a[i][j];
            }
        }
    }
    String alia="";
    for(int i=0; i<col.length; i++){
        for(int j=1; j<=col[i].length; j++){
            alia=a[i].toString();
            if(alia.contains(""+j)){
                alia=col[i].toString();
                if(alia.contains(""+j)){}
                else{
                    checkers=false;
                }   
            }
            else{
                checkers=false;
            }
        }
    }
    return checkers;
}
1
  • There was one bug, but I forgot it. :-(
    – swapneils
    May 28, 2013 at 14:17
0

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.

0

Here's a very concise version in Swift, that only uses an array of Ints to track the groups of 9 numbers, and only iterates over the sudoku once.

import UIKit

func check(_ sudoku:[[Int]]) -> Bool {

    var groups = Array(repeating: 0, count: 27)

    for x in 0...8 {
        for y in 0...8 {
            groups[x] += 1 << sudoku[x][y] // Column (group 0 - 8)
            groups[y + 9] += 1 << sudoku[x][y] // Row (group 9 - 17)
            groups[(x + y * 9) / 9 + 18] += 1 << sudoku[x][y] // Box (group 18 - 27)
        }
    }

    return groups.filter{ $0 != 1022 }.count == 0
}

let 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]
]

if check(sudoku) {
    print("Pass")
} else {
    print("Fail")
}
0

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.