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 réponses
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.
Peter Norvig a un excellent article sur la résolution des puzzles sudoku (avec python),
c'est Peut-être trop pour ce que vous voulez faire, mais c'est une excellente lecture de toute façon
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
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.
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.
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)
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.
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)
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.
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;
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
}
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.
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.
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;
}
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.
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))
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).
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)
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]);
}
}
}
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;
}
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.
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)
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")
}