Ajuda com jogo estilo Sudoku!

Olá pessoal, preciso de ajuda com um código meu. Estou tentando gerar uma matriz 9x9 com todos os números preenchidos (aleatoriamente) de acordo com as regras do Sudoku. Porém o programa “se executa” infinitas vezes e não gera resultado! Aí está o código:

[code]import java.util.Random;

public class Projeto4 {
public static void main (String[]args) {
int[][] M = new int [10][10];
boolean[][] P = new boolean [10][10];
int numeroSorteado;
int cont = 0;
String saida = “”;
boolean permissao = true;
Random Sorteio = new Random();

                    //Atribui número somente à primeira linha e primeira coluna, sem repetição.
		for (int c = 1; c <= 9; c++) {
			numeroSorteado = Sorteio.nextInt(9) + 1;
			M[1][c] = numeroSorteado;
			
			for (int k = 1; k < c; k++) {
				if (M[1][c] == M[1][k]) {
					numeroSorteado = Sorteio.nextInt(9) + 1;
					M[1][c] = numeroSorteado;
					k = 0;
				}
			}
		}
		
                    //Erro está neste bloco de execuções:
		for (int i = 2; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				numeroSorteado = Sorteio.nextInt(9) + 1;
				M[i][j] = numeroSorteado;
				
				for (int t = 1; t < i; t++) {
					if (M[i][j] == M[t][j]) {
						numeroSorteado = Sorteio.nextInt(9) + 1;
						M[i][j] = numeroSorteado;
						t = 0;
					}
				}
			}
		}
		
		for (int m = 2; m <= 9; m++) {
			for (int n = 2; n <= 9; n++) {
					
				do {
					permissao = true;
					numeroSorteado = Sorteio.nextInt(9) + 1;
					M[m][n] = numeroSorteado;
					
				for (int f = 1; f < m; f++) {
					if (M[m][n] == M[m][f]) {
						permissao = false;
						break;
					}
				}
				
				for (int g = 1; g < n; g++) {
					if (M[m][n] == M[g][n]) {
						permissao = false;
						break;
					}
				}
				System.out.print(M[m][n]);
				} while (permissao != true);
			}
		}
		for (int h = 1; h <= 9; h++) {
			for (int x = 1; x <= 9; x++) {
				saida += (M[h][x] + "   ");
			}
			saida += ("\n");
		}
		System.out.print (saida);
}

}
[/code]

Obrigado por ajudarem! :wink:

Você descobriu que gerar um tabuleiro de Sudoku não é possível em tempo razoável por força bruta (que é o que você está tentando fazer). Normalmente você gera alguns poucos números no tabuleiro, e então tenta resolvê-lo por algum método tradicional.

E existe algum método de gerar jogos Sudoku pseudo-aleatórios (agregando alguns número pré-determinados a uma tabela 9x9 e deixar o Java gerar os outros de modo aleatório)? Se é que você me entende. :lol:

Obrigado pela resposta.

OK. O que se costuma fazer é o seguinte: você indica um nível de dificuldade (quebra-cabeças mais difíceis têm menos posições pré-preenchidas e quebra-cabeças mais fáceis têm mais posições pré-preenchidas) e você gera algumas dessas posições. A seguir, o seu programa tenta resolver o quebra-cabeça. Se não conseguir, então tenta novamente, até você conseguir gerar um quebra-cabeças com solução.

thingol, tentei usando números pré-definidos de um jogo completo de Sudoku, mesmo assim o programa não consegue terminar a execução!

//Vamos! 777!

import java.util.Random;

public class Projeto5 {
	public static void main (String[]args) {
		int[][] M = new int [10][10];
		boolean[][] P = new boolean [10][10];
		int numeroSorteado;
		int cont = 0;
		String saida = "";
		boolean permissao = true;
		Random Sorteio = new Random(); 
		
        M[1][1] = 5; M[1][2] = 3; M[1][5] = 7;
        M[2][1] = 6; M[2][4] = 1; M[2][5] = 9; M[2][6] = 5;
        M[3][2] = 9; M[3][3] = 8; M[3][8] = 6;
        M[4][1] = 8; M[4][5] = 6; M[4][9] = 3;
        M[5][1] = 4; M[5][4] = 8; M[5][6] = 3; M[5][9] = 1;
        M[6][1] = 7; M[6][5] = 2; M[6][9] = 6;
        M[7][2] = 6; M[7][7] = 2; M[7][8] = 8;
        M[8][4] = 4; M[4][5] = 1; M[4][6] = 9; M[8][9] = 5;
        M[9][5] = 8; M[9][8] = 7; M[9][9] = 9;
        
        
		
			for (int c = 1; c <= 9; c++) {
				if (c != 1 && c != 2 && c != 5) {
					
				numeroSorteado = Sorteio.nextInt(9) + 1;
				M[1][c] = numeroSorteado;
				
				for (int k = 1; k < c; k++) {
					if (M[1][c] == M[1][k]) {
						numeroSorteado = Sorteio.nextInt(9) + 1;
						M[1][c] = numeroSorteado;
						k = 0;
					}
				}
				}
			}
			
			for (int i = 2; i <= 9; i++) {
				if (i != 1 && i != 2 && i != 4 && i != 5 && i != 6) {
					numeroSorteado = Sorteio.nextInt(9) + 1;
					M[i][1] = numeroSorteado;
					
					for (int t = 1; t < i; t++) {
						if (M[i][1] == M[t][1]) {
							numeroSorteado = Sorteio.nextInt(9) + 1;
							M[i][1] = numeroSorteado;
							t = 0;
						}
					}
				}
			}
			
			for (int m = 2; m <= 9; m++) {
				for (int n = 2; n <= 9; n++) {
					if (M[m][n] != 0) {
						
						do {
							permissao = true;
							numeroSorteado = Sorteio.nextInt(9) + 1;
							M[m][n] = numeroSorteado;
						
						for (int f = 1; f < m; f++) {
							if (M[m][n] == M[m][f]) {
								permissao = false;
								break;
							}
						}
					
						for (int g = 1; g < n; g++) {
							if (M[m][n] == M[g][n]) {
								permissao = false;
								break;
							}
						}
						} while (permissao != true);
					}
				}
			}
			
			for (int h = 1; h <= 9; h++) {
				for (int x = 1; x <= 9; x++) {
					saida += (M[h][x] + "   ");
				}
				saida += ("\n");
			}
			System.out.print (saida);
	}
}

Obrigado!

É que os algoritmos para achar soluções para um jogo de sudoku não são por força bruta, conforme você está tentando fazer. Dê uma procuradinha na Internet por esses programas, que você vai achar vários em Java.

thingol já tentei dar uma olhada em uns códigos pela net mas achei muito complexo! Queria algo mais simples, estilo esse meu. Será que é impossível bolar um jeito de resolver Sudokus usando apenas o que sei (vide código acima)? :cry:

Se fosse fácil…

Dica: qual é o número de combinações possíveis dos dígitos de 1 a 9 dentro de um daqueles quadradinhos internos do quebra-cabeça? É 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1, que é 362880, um número não tão grande assim. Só que seu problema é bem mais complicado ( 362280 ^9 = 1,0911068841557131648034489935589e+50, que é um número bem absurdo - o número de átomos no universo é 1e+80 mais ou menos.)

O número de combinações desses dígitos que dão quebra-cabeças de sudoku resolvidos é 6670903752021072936960, ou seja, 6,67090375202107293696e+21. Portanto a probabilidade de você, ao acaso, achar um quebra-cabeças de sudoku resolvido é

6,67090375202107293696e+21 / 1,0911068841557131648034489935589e+50 = 6,1138865943302583966718470206025e-29

Como você sabe que um mol de átomos é 6.02E+23, então é mais provável você achar um único átomo em 23 toneladas de hidrogênio que você conseguir achar um quebra-cabeças de sudoku desse jeito.

OK?

Entendi a origem do problema agora!
Vou transformar ele em um “checador” de jogos Sudoku então.

Muito obrigado mesmo pela ajuda!

Olha colega ! tente este em PHP que gera uma grade válida em tempo récorde.

Faça como o Thingol falou , use uma algoritmo para preencher algumas casas e depois ache um algoritmo de resolução para preencher as casas restantes .

Por exemplo , eu preencho o sudoku aleatoriamente dessa forma , utilizando ArrayList preenchidas com números de 1 a 9 e sorteadas aleatoriamente :

1 4 3 7 8 9 5 6 2 3 6 9 1 5 8 4 2 9

Depois eu pego a array semi-preenchida e utilizo algum algoritmo de resolução .
Se o algoritmo não conseguir resolver , eu faço nova tentativa já usando outra array semi-preenchida .

Esse aqui gera um pseudo-código que sempre repete um mesmo padrão , não é totalmente aleatória a geração de números .
Se for uma pessoa mais observadora , verá que este sudoku só gera 9 padrões diferentes de sudoku .
Estou criando um gerador que gera um número absurdo de tabuleiros e será usado em um jogo para Android que estou desenvolvendo .

Olha o código do pseudo-gerador :

[code]/*

  • To change this license header, choose License Headers in Project Properties.
  • To change this template file, choose Tools | Templates
  • and open the template in the editor.
    */
    package sudokutest;

import java.util.Random;

/**
*

  • @author paulo
    */
    public class SudokuTest
    {

    /**

    • @param args the command line arguments
      */
      public static void main(String[] args)
      {
      for (int number = 0; number < 100; number++)
      {
      Random random = new Random();

       final int n = 3;//aqui vai o numero de elementos do seu sudoku(3 vai ser um sudoku 3x3
       final int[][] field = new int[n * n][n * n];//matriz onde será armazenado o sudoku
       int x = random.nextInt(100);//semente aleatória para não gerar o mesmo sudoku
       for (int i = 0; i < n; i++, x++)
       {
           for (int j = 0; j < n; j++, x += n)
           {
               for (int k = 0; k < n * n; k++, x++)
               {
                   field[n * i + j][k] = (x % (n * n)) + 1;
               }
           }
       }
      
       String board = "";
       for (int i = 0; i < field.length; i++)
       {
           for (int j = 0; j < field[i].length; j++)
           {
               board += " "
                       + ((field[i][j] < 0) ? -1 * field[i][j] : field[i][j]) + " ";
           }
           board += "\n";
       }
       System.out.println("" + board);
      

      }
      }

}
[/code]

Criei uma classe que resolve o jogo.

import java.util.ArrayList;
import java.util.List;


public class Puzzle {
	
	public static void resolverPuzzle(int puzzle[][]){
		int valor = 0;
		List<String> alteracoes = new ArrayList<String>();
		
		for (int x=0;x<9;x++){
			for (int y=0;y<9;y++){
				if(puzzle[x][y] == 0){
					
					if(valor == 0){
						valor = 1;
					}
					int valorAnterior = valor;
					
					//Verifica se o valor não está na linha
					for(int i=0;i<9;i++){
						if(puzzle[x][i] == valor){
							valor = valor + 1;
							i=0;
						}
					}
					
					//Verifica se o valor não está na coluna
					for(int i=0;i<9;i++){
						if(puzzle[i][y] == valor){
							valor = valor + 1;
							i=0;
						}
					}
					
					//Verifica se o valor não está em uma área 3x3
					if(x < 3){
						if(y < 3){
							for(int i=0;i<3;i++){
								for(int j=0;j<3;j++){
									if(puzzle[i][j] == valor){
										valor = valor + 1;
										i = 0;
										j = 0;
										break;
									}
								}
							}
						}else if(y < 6){
							for(int i=0;i<3;i++){
								for(int j=3;j<6;j++){
									if(puzzle[i][j] == valor){
										valor = valor + 1;
										i = 0;
										j = 3;
										break;
									}
								}
							}
						}else if(y < 9){
							for(int i=0;i<3;i++){
								for(int j=6;j<9;j++){
									if(puzzle[i][j] == valor){
										valor = valor + 1;
										i = 0;
										j = 6;
										break;
									}
								}
							}
						}
					}else if(x < 6){
						if(y < 3){
							for(int i=3;i<6;i++){
								for(int j=0;j<3;j++){
									if(puzzle[i][j] == valor){
										valor = valor + 1;
										i = 3;
										j = 0;
										break;
									}
								}
							}
							
						}else if(y < 6){
							for(int i=3;i<6;i++){
								for(int j=3;j<6;j++){
									if(puzzle[i][j] == valor){
										valor = valor + 1;
										i = 3;
										j = 3;
										break;
									}
								}
							}
							
						}else if(y < 9){
							for(int i=3;i<6;i++){
								for(int j=6;j<9;j++){
									if(puzzle[i][j] == valor){
										valor = valor + 1;
										i = 3;
										j = 6;
										break;
									}
								}
							}
						}
					}else if(x < 9){
						if(y < 3){
							for(int i=6;i<9;i++){
								for(int j=0;j<3;j++){
									if(puzzle[i][j] == valor){
										valor = valor + 1;
										i = 6;
										j = 0;
										break;
									}
								}
							}
						}else if(y < 6){
							for(int i=6;i<9;i++){
								for(int j=3;j<6;j++){
									if(puzzle[i][j] == valor){
										valor = valor + 1;
										i = 6;
										j = 3;
										break;
									}
								}
							}
						}else if(y < 9){
							for(int i=6;i<9;i++){
								for(int j=6;j<9;j++){
									if(puzzle[i][j] == valor){
										valor = valor + 1;
										i = 6;
										j = 6;
										break;
									}
								}
							}
						}
					}
					
					//Se não encontrar um valor válido então muda os valores anteriores
					if(valor > 9){
						x = Integer.parseInt(alteracoes.get(alteracoes.size()-1).substring(0,1));
						y = Integer.parseInt(alteracoes.get(alteracoes.size()-1).substring(1,2));
						alteracoes.remove(alteracoes.size()-1);
						valor = puzzle[x][y] + 1;
						puzzle[x][y] = 0;
						
						//Condição necessária para quando precisar voltar uma linha da matriz
						if(y == 0){
							x = x - 1;
							y = 9;
						}else{
							y = y - 1;
						}
					}else if(valor != valorAnterior){
						//Condição necessária para quando precisar voltar uma linha da matriz
						if(y == 0){
							x = x - 1;
							y = 9;
						}else{
							y = y - 1;
						}
					}else{
						
					//Se encontrar um valor válido, adiciona o campo alterado em uma lista de log e vai para o próximo número
						alteracoes.add(Integer.toString(x)+Integer.toString(y));
						puzzle[x][y] = valor;
						valor = 0;

					//Imprimir resultado na Tela
						String texto = "";
						for(int i=0;i<9;i++){
							for(int j=0;j<9;j++){
								texto = texto + Integer.toString(puzzle[i][j]);
								
								if(j == 2){
									texto = texto + "|";		
								}else if(j == 5){
									texto = texto + "|";
								}else if(j == 8){
									texto = texto + "\n";
								}
							}
							System.out.println(texto);
							System.out.println("\n");
						}
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		int puzzle[][]={
			{5,3,0,0,7,0,0,0,0},
			{6,0,0,1,9,5,0,0,0},
			{0,9,8,0,0,0,0,6,0},
			
			{8,0,0,0,6,0,0,0,3},
			{4,0,0,8,0,3,0,0,1},
			{7,0,0,0,2,0,0,0,6},
			
			{0,6,0,0,0,0,2,8,0},
			{0,0,0,4,1,9,0,0,5},
		    {0,0,0,0,8,0,0,7,9}
		};
		
		resolverPuzzle(puzzle);

	}
	
}

Show !