Java Sudoku Generator (solution la plus simple)

Question

Dans ma dernière question vu ici: Sudoku - Region testing J'ai demandé comment vérifier les régions 3x3 et quelqu'un a été en mesure de me donner une réponse satisfaisante (même si cela impliquait beaucoup de bricolage pour le faire fonctionner comment je Je voulais, car ils ne mentionnaient pas ce que la classe table_t était.)

J'ai terminé le projet et j'ai pu créer un générateur de sudoku, mais on a l'impression que c'est artificiel. Et j'ai l'impression d'avoir trop compliqué les choses en adoptant une approche très brutale pour générer les puzzles. Essentiellement, mon but est de créer une grille 9x9 avec des régions 9-3x3. Chaque rangée/col/région doit utiliser les numéros 1-9 seulement une fois.

La façon dont je suis allé résoudre ce problème était en utilisant un tableau bidimensionnel pour placer des nombres au hasard, 3 lignes à la fois. Une fois les 3 rangées terminées, les 3 rangées sont vérifiées, et 3 régions et chaque colonne verticale jusqu'à la 3ème position. Comme il itérait à travers elle ferait la même chose jusqu'à ce que le tableau a été rempli, mais en raison du fait que je remplissais avec rand, et en vérifiant chaque ligne/colonne/région plusieurs fois, il se sentait très inefficace.

Existe-t-il un moyen "plus facile" de faire cela avec tout type de construction de données mis à part un tableau 2d? Existe-t-il un moyen plus simple de vérifier chaque région 3x3 qui coïncide avec la vérification du vert ou de l'horizontal? Du point de vue du calcul, je ne vois pas trop de façons de le faire plus efficacement sans gonfler la taille du code de façon spectaculaire.

Answer 1

J'ai construit un jeu de sudoku il y a un certain temps et j'ai utilisé l'algorithme de liens de danse de Donald Knuth pour générer les puzzles. J'ai trouvé ces sites très utiles dans l'apprentissage et la mise en œuvre de l'algorithme

http://en.wikipedia.org/wiki/Dancing_Links

http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/

http://garethrees.org/2007/06/10/zendoku-generation/

Answer 2

Je pense que vous pouvez utiliser un tableau 1D, de la même façon un tableau 1D peut modéliser un arbre binaire. Par exemple, pour regarder la valeur sous un nombre, ajoutez 9 à l'index.

Je viens de faire ça, mais est-ce que quelque chose comme ça pourrait fonctionner? Edit: Cela fait un moment que j'ai utilisé des tableaux en Java, désolé si je foirais n'importe quelle syntaxe. S'il vous plaît considérez le pseudo code :)

Voici le code comme décrit ci-dessous dans mon commentaire.

public class Sudoku 
{ 
    public int[] puzzle = new int[81]; 
    private void makePuzzle(int[] puzzle, int i) 
    { 
     for (int x = 1; x< 10 ; x++) 
     { 
      puzzle[i]=x; 
      if(checkConstraints(puzzle)) 
      { 
       if (i==80)//terminal condition 
       { 
        System.out.println(this);//print out the completed puzzle 
         puzzle[i]=0; 
        return; 
       } 
       else 
        makePuzzle(puzzle,i+1);//find a number for the next square       
      } 
      puzzle[i]=0;//this try didn't work, delete the evidence 
     }  
    } 
    private boolean checkConstraints(int[] puzzle) 
    { 
     int test; 
    //test that rows have unique values  
     for (int column=0; column<9; column++) 
     { 
      for (int row=0; row<9; row++) 
      { 
       test=puzzle[row+column*9]; 
       for (int j=0;j<9;j++) 
       { 
        if(test!=0&& row!=j&&test==puzzle[j+column*9]) 
         return false; 
       } 
      } 
     } 
     //test that columns have unique values 
     for (int column=0; column<9; column++) 
     { 
      for(int row=0; row<9; row++) 
      { 
       test=puzzle[column+row*9]; 
       for (int j=0;j<9;j++) 
       { 
        if(test!=0&&row!=j&&test==puzzle[column+j*9]) 
         return false; 
       } 
      } 
     } 
     //implement region test here 
     int[][] regions = new int[9][9]; 
     int[] regionIndex ={0,3,6,27,30,33,54,57,60}; 
     for (int region=0; region<9;region++) //for each region 
     { 

      int j =0; 
      for (int k=regionIndex[region];k<regionIndex[region]+27; k=(k%3==2?k+7:k+1)) 
       { 
        regions[region][j]=puzzle[k]; 
        j++; 
       } 
     } 
     for (int i=0;i<9;i++)//region counter 
     { 
      for (int j=0;j<9;j++) 
      { 
       for (int k=0;k<9;k++) 
       { 
        if (regions[i][j]!=0&&j!=k&&regions[i][j]==regions[i][k]) 
        return false; 
       } 

      } 
     } 
    return true; 

    } 
    public String toString() 
    { 
     String string= ""; 
     for (int i=0; i <9;i++) 
     { 
      for (int j = 0; j<9;j++) 
      { 
       string = string+puzzle[i*9+j]; 
      } 
      string =string +"\n"; 
     } 
     return string; 
    } 
    public static void main(String[] args) 
    { 
     Sudoku sudoku=new Sudoku(); 
     sudoku.makePuzzle(sudoku.puzzle, 0); 
    } 

} 

Answer 3

Essayez ce code:

package com; 
public class Suduku{ 
    public static void main(String[] args){ 
     int k=0; 
     int fillCount =1; 
     int subGrid=1; 
     int N=3; 
     int[][] a=new int[N*N][N*N]; 
    for (int i=0;i<N*N;i++){ 
     if(k==N){ 
      k=1; 
      subGrid++; 
      fillCount=subGrid; 
     }else{ 
      k++; 
      if(i!=0) 
      fillCount=fillCount+N; 
     } 
     for(int j=0;j<N*N;j++){ 
      if(fillCount==N*N){ 
       a[i][j]=fillCount; 
       fillCount=1; 
       System.out.print(" "+a[i][j]); 
      }else{ 
       a[i][j]=fillCount++; 
       System.out.print(" "+a[i][j]); 
      } 
     } 
     System.out.println(); 
    } 
} 
} 

Answer 4

import java.util.Random; 
import java.util.Scanner; 

public class sudoku { 

    /** 
    * @antony 
    */ 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     int p = 1; 
     Random r = new Random(); 
     int i1=r.nextInt(8); 
     int firstval = i1; 
     while (p == 1) { 
      int x = firstval, v = 1; 
      int a[][] = new int[9][9]; 
      int b[][] = new int[9][9]; 
      for (int i = 0; i < 9; i++) { 
       for (int j = 0; j < 9; j++) { 
        if ((x + j + v) <= 9) 
         a[i][j] = j + x + v; 
        else 
         a[i][j] = j + x + v - 9; 
        if (a[i][j] == 10) 
         a[i][j] = 1; 
        // System.out.print(a[i][j]+" "); 
       } 
       x += 3; 
       if (x >= 9) 
        x = x - 9; 
       // System.out.println(); 
       if (i == 2) { 
        v = 2; 
        x = firstval; 
       } 
       if (i == 5) { 
        v = 3; 
        x = firstval; 
       } 

      } 
      int eorh; 
      Scanner in = new Scanner(System.in); 
      System.out 
        .println("hey lets play a game of sudoku:take down the question and replace the 0's with your digits and complete the game by re entering your answer"); 
      System.out.println("enter your option 1.hard 2.easy"); 
      eorh = in.nextInt(); 
      switch (eorh) { 
      case 1: 
       b[0][0] = a[0][0]; 
       b[8][8] = a[8][8]; 
       b[0][3] = a[0][3]; 
       b[0][4] = a[0][4]; 
       b[1][2] = a[1][2]; 
       b[1][3] = a[1][3]; 
       b[1][6] = a[1][6]; 
       b[1][7] = a[1][7]; 
       b[2][0] = a[2][0]; 
       b[2][4] = a[2][4]; 
       b[2][8] = a[2][8]; 
       b[3][2] = a[3][2]; 
       b[3][8] = a[3][8]; 
       b[4][2] = a[4][2]; 
       b[4][3] = a[4][3]; 
       b[4][5] = a[4][5]; 
       b[4][6] = a[4][6]; 
       b[5][0] = a[5][0]; 
       b[5][6] = a[5][6]; 
       b[6][0] = a[6][0]; 
       b[6][4] = a[6][4]; 
       b[6][8] = a[6][8]; 
       b[7][1] = a[7][1]; 
       b[7][2] = a[7][2]; 
       b[7][5] = a[7][5]; 
       b[7][6] = a[7][6]; 
       b[8][4] = a[8][4]; 
       b[8][5] = a[8][5]; 
       b[0][0] = a[0][0]; 
       b[8][8] = a[8][8]; 

       break; 
      case 2: 
       b[0][3] = a[0][3]; 
       b[0][4] = a[0][4]; 
       b[1][2] = a[1][2]; 
       b[1][3] = a[1][3]; 
       b[1][6] = a[1][6]; 
       b[1][7] = a[1][7]; 
       b[1][8] = a[1][8]; 
       b[2][0] = a[2][0]; 
       b[2][4] = a[2][4]; 
       b[2][8] = a[2][8]; 
       b[3][2] = a[3][2]; 
       b[3][5] = a[3][5]; 
       b[3][8] = a[3][8]; 
       b[4][0] = a[4][0]; 
       b[4][2] = a[4][2]; 
       b[4][3] = a[4][3]; 
       b[4][4] = a[4][4]; 
       b[4][5] = a[4][5]; 
       b[4][6] = a[4][6]; 
       b[5][0] = a[5][0]; 
       b[5][1] = a[5][1]; 
       b[5][4] = a[5][4]; 
       b[5][6] = a[5][6]; 
       b[6][0] = a[6][0]; 
       b[6][4] = a[6][4]; 
       b[6][6] = a[6][6]; 
       b[6][8] = a[6][8]; 
       b[7][0] = a[7][0]; 
       b[7][1] = a[7][1]; 
       b[7][2] = a[7][2]; 
       b[7][5] = a[7][5]; 
       b[7][6] = a[7][6]; 
       b[8][2] = a[8][2]; 
       b[8][4] = a[8][4]; 
       b[8][5] = a[8][5]; 
       break; 
      default: 
       System.out.println("entered option is incorrect"); 
       break; 
      } 

      for (int y = 0; y < 9; y++) { 
       for (int z = 0; z < 9; z++) { 
        System.out.print(b[y][z] + " "); 
       } 
       System.out.println(""); 
      } 
      System.out.println("enter your answer"); 
      int c[][] = new int[9][9]; 
      for (int y = 0; y < 9; y++) { 
       for (int z = 0; z < 9; z++) { 
        c[y][z] = in.nextInt(); 
       } 
      } 
      for (int y = 0; y < 9; y++) { 
       for (int z = 0; z < 9; z++) 
        System.out.print(c[y][z] + " "); 
       System.out.println(); 
      } 
      int q = 0; 
      for (int y = 0; y < 9; y++) { 
       for (int z = 0; z < 9; z++) 
        if (a[y][z] == c[y][z]) 
         continue; 
        else { 
         q++; 
         break; 
        } 
      } 
      if (q == 0) 
       System.out 
         .println("the answer you have entered is correct well done"); 
      else 
       System.out.println("oh wrong answer better luck next time"); 
      System.out 
        .println("do you want to play a different game of sudoku(1/0)"); 
      p = in.nextInt(); 
      firstval=r.nextInt(8); 
      /*if (firstval > 8) 
       firstval -= 9;*/ 
     } 

    } 
}