Antecedentes: Las
siguientes son las reglas de Sudoku para un jugador.
- En las 9 subarrays 3×3 los elementos deben ser 1-9, sin repetición.
- En todas las filas debe haber elementos entre 1-9, sin repetición.
- En todas las columnas debe haber elementos entre 1-9, sin repetición.
La tarea es generar una cuadrícula de Sudoku de 9 x 9 que sea válida, es decir, un jugador puede completar la cuadrícula siguiendo el conjunto de reglas anterior.
Una simple solución ingenua puede ser.
- Tome al azar cualquier número del 1 al 9.
- Compruebe si es seguro ponerlo en la celda (fila, columna y cuadro)
- Si es seguro, colóquelo e incremente a la siguiente ubicación y vaya al paso 1.
- Si no es seguro, entonces, sin incrementar, vaya al paso 1.
- Una vez que la array esté completamente llena, retire k no. de elementos al azar para completar el juego.
Solución mejorada: Podemos mejorar la solución, si entendemos un patrón en este juego. Podemos observar que todas las arrays de 3 x 3, que están diagonalmente presentes, son independientes de otras arrays de 3 x 3 adyacentes inicialmente, ya que otras están vacías.
3 8 5 0 0 0 0 0 0 9 2 1 0 0 0 0 0 0 6 4 7 0 0 0 0 0 0 0 0 0 1 2 3 0 0 0 0 0 0 7 8 4 0 0 0 0 0 0 6 9 5 0 0 0 0 0 0 0 0 0 8 7 3 0 0 0 0 0 0 9 6 2 0 0 0 0 0 0 1 4 5
(Podemos observar que en la array anterior, las arrays diagonales son independientes de otras arrays vacías inicialmente). Entonces, si los llenamos primero, solo tendremos que marcar la casilla y, por lo tanto, no se requiere la verificación de columna / fila.
En segundo lugar, mientras rellenamos el resto de los elementos no diagonales, no tendremos que usar un generador aleatorio, pero podemos rellenar recursivamente marcando del 1 al 9.
Following is the improved logic for the problem. 1. Fill all the diagonal 3x3 matrices. 2. Fill recursively rest of the non-diagonal matrices. For every cell to be filled, we try all numbers until we find a safe number to be placed. 3. Once matrix is fully filled, remove K elements randomly to complete game.
C++
/* C++ program for Sudoku generator */
#include <bits/stdc++.h>
using namespace std;
class Sudoku {
public:
int** mat;
int N;
// number of columns/rows.
int SRN;
// square root of N
int K;
// No. Of missing digits
// Constructor
Sudoku(int N, int K)
{
this->N = N;
this->K = K;
// Compute square root of N
double SRNd = sqrt(N);
SRN = (int)SRNd;
mat = new int*[N];
// Create a row for every pointer
for (int i = 0; i < N; i++)
{
// Note : Rows may not be contiguous
mat[i] = new int[N];
// Initialize all entries as false to indicate
// that there are no edges initially
memset(mat[i], 0, N * sizeof(int));
}
}
// Sudoku Generator
void fillValues()
{
// Fill the diagonal of SRN x SRN matrices
fillDiagonal();
// Fill remaining blocks
fillRemaining(0, SRN);
// Remove Randomly K digits to make game
removeKDigits();
}
// Fill the diagonal SRN number of SRN x SRN matrices
void fillDiagonal()
{
for (int i = 0; i < N; i = i + SRN)
{
// for diagonal box, start coordinates->i==j
fillBox(i, i);
}
}
// Returns false if given 3 x 3 block contains num.
bool unUsedInBox(int rowStart, int colStart, int num)
{
for (int i = 0; i < SRN; i++) {
for (int j = 0; j < SRN; j++) {
if (mat[rowStart + i][colStart + j]
== num) {
return false;
}
}
}
return true;
}
// Fill a 3 x 3 matrix.
void fillBox(int row, int col)
{
int num;
for (int i = 0; i < SRN; i++) {
for (int j = 0; j < SRN; j++) {
do {
num = randomGenerator(N);
} while (!unUsedInBox(row, col, num));
mat[row + i][col + j] = num;
}
}
}
// Random generator
int randomGenerator(int num)
{
return (int)floor(
(float)(rand() / double(RAND_MAX) * num + 1));
}
// Check if safe to put in cell
bool CheckIfSafe(int i, int j, int num)
{
return (
unUsedInRow(i, num) && unUsedInCol(j, num)
&& unUsedInBox(i - i % SRN, j - j % SRN, num));
}
// check in the row for existence
bool unUsedInRow(int i, int num)
{
for (int j = 0; j < N; j++) {
if (mat[i][j] == num) {
return false;
}
}
return true;
}
// check in the row for existence
bool unUsedInCol(int j, int num)
{
for (int i = 0; i < N; i++) {
if (mat[i][j] == num) {
return false;
}
}
return true;
}
// A recursive function to fill remaining
// matrix
bool fillRemaining(int i, int j)
{
// System.out.println(i+" "+j);
if (j >= N && i < N - 1) {
i = i + 1;
j = 0;
}
if (i >= N && j >= N) {
return true;
}
if (i < SRN) {
if (j < SRN) {
j = SRN;
}
}
else if (i < N - SRN) {
if (j == (int)(i / SRN) * SRN) {
j = j + SRN;
}
}
else {
if (j == N - SRN) {
i = i + 1;
j = 0;
if (i >= N) {
return true;
}
}
}
for (int num = 1; num <= N; num++) {
if (CheckIfSafe(i, j, num)) {
mat[i][j] = num;
if (fillRemaining(i, j + 1)) {
return true;
}
mat[i][j] = 0;
}
}
return false;
}
// Remove the K no. of digits to
// complete game
void removeKDigits()
{
int count = K;
while (count != 0) {
int cellId = randomGenerator(N * N) - 1;
// System.out.println(cellId);
// extract coordinates i and j
int i = (cellId / N);
int j = cellId % 9;
if (j != 0) {
j = j - 1;
}
// System.out.println(i+" "+j);
if (mat[i][j] != 0) {
count--;
mat[i][j] = 0;
}
}
}
// Print sudoku
void printSudoku()
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << to_string(mat[i][j]) + " ";
}
cout << endl;
}
cout << endl;
}
};
// Driver code
int main()
{
int N = 9;
int K = 20;
Sudoku* sudoku = new Sudoku(N, K);
sudoku->fillValues();
sudoku->printSudoku();
return 0;
}
// This code is contributed by Aarti_Rathi
Java
/* Java program for Sudoku generator */
import java.lang.*;
public class Sudoku
{
int[] mat[];
int N; // number of columns/rows.
int SRN; // square root of N
int K; // No. Of missing digits
// Constructor
Sudoku(int N, int K)
{
this.N = N;
this.K = K;
// Compute square root of N
Double SRNd = Math.sqrt(N);
SRN = SRNd.intValue();
mat = new int[N][N];
}
// Sudoku Generator
public void fillValues()
{
// Fill the diagonal of SRN x SRN matrices
fillDiagonal();
// Fill remaining blocks
fillRemaining(0, SRN);
// Remove Randomly K digits to make game
removeKDigits();
}
// Fill the diagonal SRN number of SRN x SRN matrices
void fillDiagonal()
{
for (int i = 0; i<N; i=i+SRN)
// for diagonal box, start coordinates->i==j
fillBox(i, i);
}
// Returns false if given 3 x 3 block contains num.
boolean unUsedInBox(int rowStart, int colStart, int num)
{
for (int i = 0; i<SRN; i++)
for (int j = 0; j<SRN; j++)
if (mat[rowStart+i][colStart+j]==num)
return false;
return true;
}
// Fill a 3 x 3 matrix.
void fillBox(int row,int col)
{
int num;
for (int i=0; i<SRN; i++)
{
for (int j=0; j<SRN; j++)
{
do
{
num = randomGenerator(N);
}
while (!unUsedInBox(row, col, num));
mat[row+i][col+j] = num;
}
}
}
// Random generator
int randomGenerator(int num)
{
return (int) Math.floor((Math.random()*num+1));
}
// Check if safe to put in cell
boolean CheckIfSafe(int i,int j,int num)
{
return (unUsedInRow(i, num) &&
unUsedInCol(j, num) &&
unUsedInBox(i-i%SRN, j-j%SRN, num));
}
// check in the row for existence
boolean unUsedInRow(int i,int num)
{
for (int j = 0; j<N; j++)
if (mat[i][j] == num)
return false;
return true;
}
// check in the row for existence
boolean unUsedInCol(int j,int num)
{
for (int i = 0; i<N; i++)
if (mat[i][j] == num)
return false;
return true;
}
// A recursive function to fill remaining
// matrix
boolean fillRemaining(int i, int j)
{
// System.out.println(i+" "+j);
if (j>=N && i<N-1)
{
i = i + 1;
j = 0;
}
if (i>=N && j>=N)
return true;
if (i < SRN)
{
if (j < SRN)
j = SRN;
}
else if (i < N-SRN)
{
if (j==(int)(i/SRN)*SRN)
j = j + SRN;
}
else
{
if (j == N-SRN)
{
i = i + 1;
j = 0;
if (i>=N)
return true;
}
}
for (int num = 1; num<=N; num++)
{
if (CheckIfSafe(i, j, num))
{
mat[i][j] = num;
if (fillRemaining(i, j+1))
return true;
mat[i][j] = 0;
}
}
return false;
}
// Remove the K no. of digits to
// complete game
public void removeKDigits()
{
int count = K;
while (count != 0)
{
int cellId = randomGenerator(N*N)-1;
// System.out.println(cellId);
// extract coordinates i and j
int i = (cellId/N);
int j = cellId%9;
if (j != 0)
j = j - 1;
// System.out.println(i+" "+j);
if (mat[i][j] != 0)
{
count--;
mat[i][j] = 0;
}
}
}
// Print sudoku
public void printSudoku()
{
for (int i = 0; i<N; i++)
{
for (int j = 0; j<N; j++)
System.out.print(mat[i][j] + " ");
System.out.println();
}
System.out.println();
}
// Driver code
public static void main(String[] args)
{
int N = 9, K = 20;
Sudoku sudoku = new Sudoku(N, K);
sudoku.fillValues();
sudoku.printSudoku();
}
}
C#
/* C# program for Sudoku generator */
using System;
public class Sudoku
{
int[,] mat;
int N; // number of columns/rows.
int SRN; // square root of N
int K; // No. Of missing digits
// Constructor
public Sudoku(int N, int K)
{
this.N = N;
this.K = K;
// Compute square root of N
double SRNd = Math.Sqrt(N);
SRN = (int)SRNd;
mat = new int[N,N];
}
// Sudoku Generator
public void fillValues()
{
// Fill the diagonal of SRN x SRN matrices
fillDiagonal();
// Fill remaining blocks
fillRemaining(0, SRN);
// Remove Randomly K digits to make game
removeKDigits();
}
// Fill the diagonal SRN number of SRN x SRN matrices
void fillDiagonal()
{
for (int i = 0; i<N; i=i+SRN)
// for diagonal box, start coordinates->i==j
fillBox(i, i);
}
// Returns false if given 3 x 3 block contains num.
bool unUsedInBox(int rowStart, int colStart, int num)
{
for (int i = 0; i<SRN; i++)
for (int j = 0; j<SRN; j++)
if (mat[rowStart+i,colStart+j]==num)
return false;
return true;
}
// Fill a 3 x 3 matrix.
void fillBox(int row,int col)
{
int num;
for (int i=0; i<SRN; i++)
{
for (int j=0; j<SRN; j++)
{
do
{
num = randomGenerator(N);
}
while (!unUsedInBox(row, col, num));
mat[row+i,col+j] = num;
}
}
}
// Random generator
int randomGenerator(int num)
{
Random rand = new Random();
return (int) Math.Floor((double)(rand.NextDouble()*num+1));
}
// Check if safe to put in cell
bool CheckIfSafe(int i,int j,int num)
{
return (unUsedInRow(i, num) &&
unUsedInCol(j, num) &&
unUsedInBox(i-i%SRN, j-j%SRN, num));
}
// check in the row for existence
bool unUsedInRow(int i,int num)
{
for (int j = 0; j<N; j++)
if (mat[i,j] == num)
return false;
return true;
}
// check in the row for existence
bool unUsedInCol(int j,int num)
{
for (int i = 0; i<N; i++)
if (mat[i,j] == num)
return false;
return true;
}
// A recursive function to fill remaining
// matrix
bool fillRemaining(int i, int j)
{
// System.out.println(i+" "+j);
if (j>=N && i<N-1)
{
i = i + 1;
j = 0;
}
if (i>=N && j>=N)
return true;
if (i < SRN)
{
if (j < SRN)
j = SRN;
}
else if (i < N-SRN)
{
if (j==(int)(i/SRN)*SRN)
j = j + SRN;
}
else
{
if (j == N-SRN)
{
i = i + 1;
j = 0;
if (i>=N)
return true;
}
}
for (int num = 1; num<=N; num++)
{
if (CheckIfSafe(i, j, num))
{
mat[i,j] = num;
if (fillRemaining(i, j+1))
return true;
mat[i,j] = 0;
}
}
return false;
}
// Remove the K no. of digits to
// complete game
public void removeKDigits()
{
int count = K;
while (count != 0)
{
int cellId = randomGenerator(N*N)-1;
// System.out.println(cellId);
// extract coordinates i and j
int i = (cellId/N);
int j = cellId%9;
if (j != 0)
j = j - 1;
// System.out.println(i+" "+j);
if (mat[i,j] != 0)
{
count--;
mat[i,j] = 0;
}
}
}
// Print sudoku
public void printSudoku()
{
for (int i = 0; i<N; i++)
{
for (int j = 0; j<N; j++)
Console.Write(mat[i,j] + " ");
Console.WriteLine();
}
Console.WriteLine();
}
// Driver code
public static void Main(string[] args)
{
int N = 9, K = 20;
Sudoku sudoku = new Sudoku(N, K);
sudoku.fillValues();
sudoku.printSudoku();
}
}
// This code is contributed by rrrtnx.
Salida: [ 0 significa no llenado]
2 3 0 4 1 5 0 6 8 0 8 0 2 3 6 5 1 9 1 6 0 9 8 7 2 3 4 3 1 7 0 9 4 0 2 5 4 5 8 1 2 0 6 9 7 9 2 6 0 5 8 3 0 1 0 0 0 5 0 0 1 0 2 0 0 0 8 4 2 9 0 3 5 9 2 3 7 1 4 8 6
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Este artículo es una contribución de Aarti_Rathi y Ankur Trisal (ankur.trisal@gmail.com) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA