problèmes de duplication tout en créant un puzzle de sudoku

Question

J'essaie de créer mon propre 9x9 normal sudoku puzzle.

Je divise le problème en deux parties -

1. la création d'un sudoku entièrement rempli, et
2. suppression des numéros inutiles de la grille

En ce moment, je suis coincé avec le premier partie.

---

C'est l'algorithme que j'utilise en bref:

a) d'abord tout ce que je choisis un certain nombre (par exemple 1), générer une position de cellule au hasard, et placez-là si

• la cellule n'est pas déjà occupée, et
• si la ligne n'a pas déjà le nombre et
• si la colonne n'a pas encore le nombre et
• si la boîte 3x3 n'a pas encore le nombre

b) maintenant je vérifie une situation dans laquelle une ligne ou une colonne ou une boîte, un seul endroit est vide et je remplir ce

c) Je vérifie que s'il y a un nombre qui n'est pas présent dans une boîte mais qui est présent dans les cases de la même ligne et de la même colonne (je parle ici de 3x3 cases), la place est fixe remplis-le. D) Je répète les étapes ci-dessus jusqu'à ce que chaque chiffre apparaisse neuf fois sur la grille.

---

Le problème Je suis face est que, plus souvent, je reçois une situation intermédiaire comme ceci:

0 1 0 | 0 0 3 | 0[4/2]0 
0 [2] 0 | 0 [4] 1 | 3 0 0 
3 0 [4]|[2] 0 0 | 0 0 1 
---------+---------+--------- 
2 0 3 | 0 5 4 | 0 1 0 
0 0 1 | 3 0 2 |[4] 0 0 
0 4 0 | 0 1 0 |[2] 3 0 
---------+---------+--------- 
1 0 2 | 0 3 0 | 0 0 [4] 
4 3 0 | 1 0 0 | 0 0 [2] 
5 0 0 | 4 2 0 | 1 0 3 

Voir le lieu avec [4/2] écrit? c'est la place de 2 ainsi que 4 à cause des cases marquées [].

Que puis-je faire pour éviter dans cette situation (parce que cette situation est une impasse - je ne peux pas aller plus loin)

Answer 1

Il y a une autre façon de générer des puzzles de sudoku: Commencez avec une bonne grille connue - n'importe qui le fera - puis aléatoirement "mélangez" en appliquant des opérations qui ne détruisent pas les invariants.Les opérations valides comprennent:

• permutation des rangées dans un bloc
• colonnes pour échanger dans un bloc
• pour échanger des rangées entières de blocs (par exemple, les premiers trois, moyens 3, 3 dernières lignes)
• Permutation des colonnes entières des blocs
• pour échanger toutes les instances d'un nombre avec un autre
• reflétant la planche
• rotatifs conseil

Avec ces opérations, vous pouvez générer une très large gamme de cartes possibles. Cependant, vous devez faire attention à la façon dont vous appliquez les opérations. Tout comme le shuffle naïf, il est facile d'écrire un algorithme qui rend certaines cartes plus probables que d'autres. Une technique similaire au shuffle Knuth peut aider ici. Edit: Il a été souligné dans les commentaires que ces opérations ne sont pas suffisantes pour créer toutes les grilles possibles.

Answer 2

Si vous avez atteint un état contradictoire où une cellule si les deux 2 et 4 certains de vos autres 2 et 4 doit être placé à tort. Vous devez revenir en arrière et essayer différentes solutions.

Vous semblez avoir un problème d'algorithme? Quelques bonnes choses here.

Answer 3

Vous aurez toujours cette situation. Vous besoin une recherche de retour arrière récursive pour le résoudre. Fondamentalement, la seule façon de déterminer si un chiffre particulier est vraiment valide pour une cellule est de continuer la recherche et de voir ce qui se passe.

Les recherches de retour arrière sont normalement effectuées à l'aide d'appels récursifs. Chaque appel parcourra les options (éventuellement) encore valides pour une cellule, récursive pour évaluer toutes les options pour la cellule suivante. Lorsque vous ne pouvez pas continuer, le retour en arrière signifie le retour de l'appel en cours - en effaçant tout chiffre que vous avez testé pour cette cellule en premier, bien sûr.

Lorsque vous trouvez une solution valide, sauvegardez-la et faites marche arrière pour continuer (c.-à-d. Trouver des solutions de rechange) ou interrompez tous les appels récursifs pour terminer. Le succès d'une recherche de retour arrière récursive est un cas spécial où lancer une exception pour le succès est une bonne idée pour IMO - est exceptionnel pour qu'un appel particulier réussisse, et le code sera plus clair.

Si vous générez une carte aléatoire, parcourez les options dans un appel récursif particulier (pour une cellule particulière) dans un ordre aléatoire. Le même algorithme de base s'applique également pour une carte partiellement complétée (c'est-à-dire pour résoudre un sodoku existant) - lors de l'évaluation d'une cellule ayant déjà un chiffre, c'est la seule option pour cette cellule.

est ici la recherche de retours en arrière à partir d'un solveur j'ai écrit une fois - beaucoup est extrait, mais nous espérons que fait juste le principe plus clair ...

size_t Board::Rec_Search (size_t p_Pos) 
{ 
    size_t l_Count = 0; 

    if (p_Pos == 81) // Found a solution 
    { 
    l_Count++; 

    std::cout << "------------------------" << std::endl; 
    Draw(); 
    std::cout << "------------------------" << std::endl; 
    } 
    else 
    { 
    if (m_Board [p_Pos] == 0) // Need to search here 
    { 
     size_t l_Valid_Set = Valid_Set (p_Pos); 

     if (l_Valid_Set != 0) // Can only continue if there are possible digits 
     { 
     size_t l_Bit = 1; // Scan position for valid set 

     for (size_t i = 1; i <= 9; i++) 
     { 
      if (l_Valid_Set & l_Bit) 
      { 
      Set_Digit (p_Pos, i); 
      l_Count += Rec_Search (p_Pos + 1); 
      } 

      l_Bit <<= 1; 
     } 

     Clr_Digit (p_Pos); // Ensure cleared properly for backtracking 
     } 
    } 
    else // Already filled in - skip 
    { 
     l_Count += Rec_Search (p_Pos + 1); 
    } 
    } 

    return l_Count; 
}