Un algorithme cool pour vérifier un champ Sudoku?

quelqu'un connaît-il un algorithme simple pour vérifier si une configuration Sudoku est valide? L'algorithme le plus simple que j'ai trouvé est (pour une carte de taille n) en pseudo-code

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

mais je suis sûr qu'il doit y avoir une meilleure solution (au sens plus élégant). L'efficacité est tout à fait sans importance.

Meilleures Salutations,

Michael

24
demandé sur user18670 2008-11-14 11:56:22
la source

24 ответов

Vous devez vérifier toutes les contraintes de Sudoku :

  • cochez la somme de chaque ligne
  • vérifier la somme de chaque colonne
  • cochez la somme de chaque case
  • vérifier les numéros en double sur chaque ligne
  • vérifier les numéros en double sur chaque colonne
  • cochez la case correspondant à chaque numéro

ce n'est pas 6.. en utilisant une approche de force brute. Une sorte d'optimisation mathématique peut être utilisé si vous connaissez la taille de la carte (i.e. 3x3 ou 9x9)

Modifier: explication de la contrainte de Somme: la vérification de la somme en premier (et le stoping si la somme n'est pas 45) est beaucoup plus rapide (et plus simple) que la vérification des doublons.Il fournit un moyen facile de rejeter une mauvaise solution.

22
répondu Radu094 2010-08-08 00:15:49
la source

Peter Norvig a un excellent article sur la résolution des puzzles sudoku (avec python),

http://norvig.com/sudoku.html

c'est Peut-être trop pour ce que vous voulez faire, mais c'est une excellente lecture de toute façon

24
répondu daniel 2008-11-14 13:33:33
la source

juste une pensée: ne devez-vous pas aussi vérifier les nombres dans chaque carré de 3x3?

j'essaie de comprendre s'il est possible d'avoir les conditions des lignes et des colonnes satisfaites sans avoir un sudoku correct

7
répondu Luk 2008-11-14 12:07:01
la source

cochez chaque ligne, colonne et Case de manière à ce qu'elle contienne les numéros 1-9 chacun, sans duplicata. La plupart des réponses ici en parlent déjà.

Mais comment le faire efficacement? Réponse: Utilisez une boucle comme

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

chaque nombre définira un peu du résultat. Si tous les 9 nombres sont uniques, le plus bas 9 bits. Donc le test" check for duplicates " est juste une vérification que tous les 9 bits sont définis, ce qui est le même que le résultat de test==511. Vous devez faire 27 de ces vérifier.. un pour chaque ligne, colonne et boîte.

6
répondu SPWorley 2009-04-29 16:22:39
la source

Créer un tableau de booléens pour chaque ligne, colonne et carré. L'index du tableau représente le valeur qui a été placé dans cette rangée, colonne, ou carré. En d'autres termes, si vous ajoutez un 5 à la deuxième ligne, première colonne, vous placerez les lignes[2][5] à true, avec les colonnes[1][5] et les carrés[4][5], pour indiquer que la ligne, la colonne et le carré ont maintenant un 5 valeur.

peu importe la façon dont votre carte d'origine est représenté, cela peut être un simple et très moyen rapide de vérifier l'exhaustivité et l'exactitude. Il suffit de prendre les chiffres dans l'ordre où ils apparaissent sur le tableau, et de commencer à construire cette structure de données. Comme vous placez des nombres dans la carte, il devient une opération O(1) pour déterminer si des valeurs sont dupliquées dans une rangée, colonne, ou carré donné. (Vous voudrez aussi de vérifier que chaque valeur est légitime: si ils vous donnent un blanc ou un trop grand nombre, vous savez que le conseil n'est pas complète.) Quand vous arrivez à la fin de la carte, vous saurez que toutes les valeurs sont correctes, et il n'y a plus de vérification nécessaire.

Quelqu'un a aussi fait remarquer que vous pouvez utiliser n'importe quelle forme de Set pour faire cela. Les tableaux disposés de cette façon sont juste une forme particulièrement légère et performante d'un ensemble qui fonctionne bien pour un petit, consécutif, Fixe Ensemble de nombres. Si vous connaissez la taille de votre carte, vous pouvez également choisir de faire des bits de masquage, mais c'est probablement un peu trop fastidieux considérant que l'efficacité n'est pas un gros problème pour vous.

4
répondu StriplingWarrior 2009-10-13 22:42:19
la source

C'est ma solution en Python, je suis content de voir que c'est la plus courte à ce jour :)

le 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  

Et l'exécution:

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)        
4
répondu Kami 2011-04-04 16:21:33
la source

créer des ensembles de cellules, où chaque ensemble contient 9 cellules, et créer des ensembles pour les colonnes verticales, les rangées horizontales et les carrés 3x3.

Ensuite, pour chaque cellule, il suffit d'identifier les ensembles de partie de et de les analyser.

2
répondu Lasse Vågsæther Karlsen 2008-11-14 13:53:17
la source

vous pouvez extraire toutes les valeurs d'un ensemble (Ligne, Colonne, Boîte) dans une liste, la Trier, puis la comparer à '(1, 2, 3, 4, 5, 6, 7, 8, 9)

2
répondu Svante 2008-11-14 14:10:32
la source

j'ai fait ça une fois pour un projet de classe. J'ai utilisé un total de 27 jeux pour représenter chaque ligne, colonne et boîte. Je vérifierais les nombres que je les ai ajoutés à chaque ensemble (chaque placement d'un nombre provoque le nombre d'être ajouté à 3 ensembles, une rangée, une colonne, et une boîte) pour s'assurer que l'Utilisateur a seulement entré les chiffres 1-9. Le seul moyen de remplir un ensemble est de le remplir correctement avec des chiffres uniques. Si les 27 jeux ont été remplis, le puzzle a été résolu. Configurer les mappages de l'interface utilisateur pour les 27 sets était un peu fastidieux, mais a fait le reste de la logique un jeu d'enfant à mettre en œuvre.

2
répondu Bill the Lizard 2008-11-15 05:59:36
la source

si la somme et la multiplication d'une ligne / col égale au nombre droit 45/362880

2
répondu 2009-10-13 21:56:56
la source

Il serait très intéressant de vérifier si:

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

cela suffit les règles du sudoku. Parce que cela permettrait un algorithme de O(N^2), sommant et multipliant les cellules correctes.

en regardant n = 9, les sommes devraient être 45, les produits 362880.

Vous ferais quelque chose comme:

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;
1
répondu Ralph M. Rickenbach 2008-11-14 13:05:20
la source

il y a quelque temps, j'ai écrit un vérificateur sudoku qui vérifie le nombre de duplicata sur chaque ligne, Le nombre de duplicata sur chaque colonne et le nombre de duplicata sur chaque boîte. J'aimerais si quelqu'un pouvait trouver un avec quelques lignes de code Linq.

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
répondu Hao Wooi Lim 2009-04-29 15:45:07
la source
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];
        }
    }
}

Je ne sais pas exactement algorithhim pour vérifier les boîtes 3x3, mais vous devriez cocher toutes les lignes dans le champ et col avec "/*array name goes here*/[i].contains(1)&&/*array name goes here*/[i].contains(2) " (continue jusqu'à ce que vous atteigniez la longueur d'une rangée) à l'intérieur un autre boucle.

1
répondu user2425429 2013-06-26 19:39:53
la source

Voici une bonne approche lisible en 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))         

chaque carré de 3x3 est appelé un bloc, et il y en a 9 dans une grille de 3x3. Il est supposé que le puzzle est entrée comme une liste de liste, chaque liste interne étant une ligne.

1
répondu bjrnt 2017-02-23 09:46:57
la source

disons int sudoku[0..8,0..8] est le champ sudoku.

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;

}

0
répondu Marco M. 2008-11-14 13:30:06
la source

supposons que votre carte va de 1-n.

nous allons créer un tableau de vérification, le remplir et le vérifier.

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. 

je pense que cela va faire l'affaire, même si je suis sûr que j'ai fait quelques erreurs stupides. Je pourrais même avoir manqué le bateau entièrement.

0
répondu Bryan 2008-11-14 14:14:16
la source
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

sans vérifier minutieusement, hors de ma tête, cela devrait fonctionner (avec un peu de débogage) tout en bouclant seulement deux fois. O(n^2) au lieu de O(3(n^2))

0
répondu Josh Smeaton 2008-11-14 15:10:18
la source

Voici le papier par les mathématiques, le professeur J. F. Escroc: Un Crayon et du Papier Algorithme pour Résoudre les Puzzles de Sudoku

ce papier a été publié en avril 2009 et il a obtenu beaucoup de publicité en tant que solution Sudoku définie (consultez google pour "J. F. Crook Sudoku" ).

en plus de l'algorithme, il y a aussi une preuve mathématique que l'algorithme fonctionne (professeur admis qu'il ne trouve pas Sudoku très intéressant, donc il a jeté quelques mathématiques dans papier pour le rendre plus fun).

0
répondu zendar 2009-04-29 16:16:02
la source

j'écrirais une interface qui a des fonctions qui reçoivent le champ sudoku et renvoie true / false si c'est une solution. Puis implémenter les contraintes sous forme de classes de validation uniques par contrainte.

pour vérifier juste itérer à travers toutes les classes de contraintes et quand tout passe le sudoku est correct. Pour accélérer mettre ceux qui échouent le plus probablement à l'avant et arrêter dans le premier résultat qui pointe à champ invalide.

motif assez générique. ; -)

vous peut bien sûr améliorer ceci pour fournir des conseils qui le champ est probablement faux et ainsi de suite.

première contrainte, vérifiez si tous les champs sont remplis. (Boucle Simple) Deuxième vérifier si tous les chiffres sont dans chaque bloc (boucles imbriquées) Troisième vérification pour les lignes et les colonnes complètes (presque même procédure que ci-dessus, mais régime d'accès différent)

0
répondu Patrick Cornelissen 2009-04-29 16:29:09
la source

voici le mien en C. seulement passer chaque carré une fois.

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
répondu jpiasetz 2012-06-15 21:39:18
la source

Voici ce que je viens de faire pour cela:

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;
}
0
répondu user2425429 2013-05-28 03:20:29
la source

vous pouvez vérifier si sudoku est résolu, de deux façons similaires:

  • Vérifier si le numéro est unique dans chaque ligne, colonne et bloc.

une solution naïve serait d'itérer chaque creux et de vérifier si le nombre est unique dans la rangée, bloc de colonne que le nombre occupe.

mais il y a un meilleur moyen.

  • Sudoku est résolu si chaque ligne, colonne et bloc contient une permutation des nombres (1 auge 9)

Cela nécessite seulement de vérifier chaque ligne, colonne et bloc, au lieu de le faire pour chaque nombre. Une implémentation simple serait d'avoir un bitfield de nombres 1 à 9 et de les supprimer lorsque vous itérez les colonnes, les lignes et les blocs. Si vous essayez de supprimer un nombre manquant ou si le champ n'est pas vide quand vous terminez alors sudoku n'est pas correctement résolu.

0
répondu this 2014-04-15 14:57:49
la source
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)

0
répondu John Constantine 2016-10-14 21:52:00
la source

Voici une version très concise de Swift, qui n'utilise qu'un tableau D'Ints pour suivre les groupes de 9 nombres, et qui n'itère qu'une seule fois sur le sudoku.

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{  != 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
répondu Nick Locking 2017-09-13 03:09:46
la source

Autres questions sur