Dans ma dernière question vue ici: Test de la région de Sudoku J'ai demandé comment vérifier les régions 3x3 et quelqu'un a pu me donner une réponse satisfaisante (bien que cela impliquait beaucoup de bricolage pour le faire fonctionner comment je voulais, puisqu'ils n'ont pas mentionné 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 cela ressemble à ce qu'il soit artificiel. Et j'ai l'impression d'avoir des choses surchargées en faisant une approche très brute pour générer les énigmes.
Essentiellement, mon objectif est de créer une grille de 9x9 avec des régions de 9 à 3x3. Chaque ligne / col / région doit utiliser les chiffres 1 à 9 une seule fois.
La manière dont je suis allé de résoudre ce problème consistait à utiliser un réseau à 2 dimensions pour placer des nombres au hasard, 3 rangées à la fois. Une fois que les 3 rangées ont été faites, il vérifierait les 3 rangées, et 3 régions et chaque col vertical jusqu'à la 3ème position. Comme il itérité à travers cela ferait de la même manière que la matrice soit remplie, mais que je me remplissais avec Rand, et que je vérifiais chaque rangée / colonne / région plusieurs fois, il s'est senti très inefficace.
Y a-t-il un moyen "plus facile" de faire cela avec tout type de construction de données à part un tableau 2D? Existe-t-il un moyen plus facile de vérifier chaque région 3x3 qui pourrait coïncider avec la vérification de Vert ou horizontale mieux? D'un point de vue de calcul, je ne peux pas voir trop de façons de le faire plus efficacement sans gonfler la taille du code de façon spectaculaire.
4 Réponses :
J'ai construit un jeu de Sudoku il y a un moment et j'ai utilisé l'algorithme de liens de danse par Donald Knuth pour générer les énigmes. J'ai trouvé ces sites très utiles dans l'apprentissage et la mise en œuvre de l'algorithme
http://en.wikipedia.org/wiki/dancele_links
Salut Tassinari, pouvez-vous donner le coup d'œil furtif du générateur de puzzle que vous avez? J'ai du mal à créer mon algorithique pour le puzzle de Sudoku Gebnerator :( merci à Advanc
Le deuxième lien n'est pas accessible. s'il vous plaît télécharger du contenu ailleurs
Je pense que vous pouvez utiliser un tableau 1D, de la même manière qu'un tableau 1D peut modéliser un arbre binaire. Par exemple, pour examiner la valeur ci-dessous un numéro, ajoutez-le à l'index.
Je viens de faire cela, mais pourrait-il ressembler à ce travail? P>
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&®ions[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);
}
}
Je viens de penser à cela ... lorsque le tableau est initialisé, il sera rempli de zéros, ce type de vis à vis. Peut-être qu'il serait préférable d'utiliser 1 ... 10 pour les valeurs de sudoku possibles, au lieu de 0 ... 9. Lorsque vous avez fini de générer, vous pouvez simplement décrémenter chaque valeur.
Juste pensé à autre chose ... Je ne sais évidemment rien à propos de Sudoku :) Apparemment 0 n'est pas une valeur valide dans un puzzle Sudoku! Qui savait? J'ai nettoyé cependant le code ci-dessus et cela semblait fonctionner après avoir réparé toutes les erreurs évidentes :) Vous devez juste avoir besoin d'écrire correctement les contraintes.
OK, j'ai eu ce travail, alors voici un code. Cela fonctionne, mais il teste uniquement les colonnes et les lignes. Vous devrez déterminer la région Tester vous-même :) Si vous décidez de le convertir en une matrice 2D pour ce test, vérifiez la méthode Tostring (). Une fois que vous avez ajouté cela, cela générera toutes les grilles Sudoku valides. Je modifierai la réponse originale pour inclure le nouveau code.
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();
}
}
}
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;*/
}
}
}
Essayez ce code.Ce code génère une question de Sudoku.L'utilisateur doit résoudre le puzzle et entrer chaque élément manuellement, la réponse sera comparée au résultat requis et affiche si votre réponse est correcte ou non.