Algoritmo para gerar um sudoku NxN válido.


Na faculdade, na aula de programação a professora nos pediu para gerarmos um sudoku válido. Depois de tantas tentativas sem sucesso, encontrei este algoritmo polinomial em Java(que pode ser facilmente traduzido para C++) na Wikipedia:

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 = rand()%10;//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;
Anúncios

4 comentários sobre “Algoritmo para gerar um sudoku NxN válido.

  1. Eu testei aqui e aparente funcionou , apesar de eu ter que modificar alguma coisa no código :

    package sudokutest;
    import java.util.Random;

    /**
    *
    * @author paulo
    */
    public class SudokuTest
    {

    /**
    * @param args the command line arguments
    */
    public static void main(String[] args)
    {
    Random random = new Random();

    final int n = 3;//aqui vai o número de elementos do seu sudoku(3 vai ser um sudoku 3×3
    final int[][] field = new int[n*n][n*n];//matriz onde será armazenado o sudoku
    int x = random.nextInt(1000);//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);
    }

    }

  2. Aff , apesar de ser válido , após os testes , o algoritmo mantém um padrão previsível de solução . Se for uma pessoa atenta , descobriria a solução do quebra-cabeças facilmente . Infelizmente esse algoritmo aqui precisa de algumas melhorias , pois a semente gera apenas alguns tipos semelhantes de solução . A diversificação é somente aparente , pois o padrão é identico , somente mesclando as posições dos números .

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s