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

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.

Answer 2

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

Answer 3

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).

Answer 4

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))

Answer 5

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]);
    }
  }
}

Answer 6

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")
}