Algoritmo creativo de Sudoku
Sudokus generados por computadora
Realmente no es fácil encontrar todas las combinaciones que cumplan las condiciones (principalmente porque hay muchas combinaciones y la impresión es muy lenta). Pero el objetivo de los números pares es simplemente obtener una nueva combinación cada vez y bloquear aleatoriamente algunos números dentro de la cuadrícula. Por lo tanto, sólo se requiere una ligera modificación en el algoritmo para resolver el juego de Sudoku.
Entonces el algoritmo es el siguiente:
1. Complete aleatoriamente de 1 a 9 números en la primera fila o columna.
2 Llame al algoritmo de Sudoku para. obtenga resultado
3. Enmascare aleatoriamente de 1 a 8 números en cada línea. Si necesitas una dificultad mayor, también puedes cambiar 1-8 por 2-8 o 3-8, etc.
El siguiente es el código para el proyecto de consola:
// sudoku.cpp: Define el punto de entrada para la aplicación de consola.
// por superarhow(superarhow@hotmail.com)
#include "stdafx.h"
#include "conio.h"
#define SUCCESS 1
#define _FAILED 0
/* MAPTYPE 9*9 caracteres, cada carácter comienza del 0 al 9, 0 significa completar */
typedef char MAPTYPE[9][9];
/* Datos de fila, también utilizados como datos de "posibilidad". Por ejemplo, LINETYPE a; cuando a[0] es verdadero, significa que
la posición actual se puede completar con 1, cuando a[1] es verdadero, significa que se puede completar 2, y así sucesivamente*/
typedef char LINETYPE[9];
typedef void (*ONMAPOKCALLBACK)(MAPTYPE map);
/* Imprimir mapa*/
void dump_map(MAPTYPE dest)
{
for ( int j = 0; j lt; 9; j )
{
for ( int i = 0; i lt; 9; i )
{
printf("d ", destino[i][j]) ;
}
printf("\n");
}
printf("\n"); >
}
printf("\n");
}
int fill_line(MAPTYPE dest, int line, devolución de llamada ONMAPOKCALLBACK);
/ * Rellena la siguiente cuadrícula.
La posibilidad de esta fila ha sido calculada antes de la llamada, ahora se considera la posibilidad de la columna y la posibilidad de las nueve grillas*/
/* nums_possible: array (0-8) representa el número ( 1-9) posibilidad*/
int fill_pos(MAPTYPE dest, int LINETYPE nums_possible, int line, int pos, devolución de llamada ONMAPOKCALLBACK)
{
if ( pos gt; = 9 )
{
return fill_line(dest, línea 1, devolución de llamada);
}
if (dest [pos][línea] != 0) return fill_pos(dest, nums_possible, line, pos 1, callback);
for (int i = 0; i lt; 9; i)
{
if ( ! nums_possible[i] ) continue
/* Compruebe si hay duplicados en esta columna*/
int vetical_failed = 0;
for ( int j = 0; j lt; 9; j )
if ( dest[pos][j] == i 1 )
{
vetical_failed = 1;
romper
}
si (vetical_failed ) continúa
/* Comprobar nueves duplicados */
int nine_failed = 0;
int m = pos / 3
int n = line / 3; p>
m *= 3;
n *= 3;
para ( int y = n; y lt; n 3; y )
{
for ( int x = m; x lt; m 3; x )
{
if ( destino[x][y] = = i 1 )
{
nueve_failed = 1;
descanso
}
}
if ( nine_failed ) break
}
if ( nine_failed ) continuar
/* todo bien, prueba con la siguiente posición */< / p>
destino[pos][línea] = i 1;
nums_possible[i] = 0;
if ( fill_pos(dest, nums_possible, línea, pos 1 , callback) )
{
/* Esta línea es normal, prueba con la siguiente línea*/
if ( fill_line(dest, line 1, callback) )
return SUCCESS;
/* La siguiente línea falla, vuelva a intentar las posibilidades restantes en esta posición*/
}
nums_possible[i] = 1;
p>destino[pos][línea] = 0
}
return _FAILED
}
/* Complete la siguiente línea*/
int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback)
{
if (line gt; = 9)
{
/* Copiar mapa*/
callback(dest);
Devolver ÉXITO
}< / p>
LINETYPE nums;
LINETYPE saveline
/* Calcular probabilidad (para la línea actual) */
for ( int i = 0 ; i lt; 9; i) nums[i] = 1; /* Todo lo posible*/
for ( int i = 0; i lt; 9; i )
{
char n = destino[i][línea]
/* Guardar línea*/
saveline[i] = destino[i][línea] ;
if ( n != 0 ) nums[n - 1] = 0; /* aparece*/
}
if ( !fill_pos(dest , números, línea, 0, devolución de llamada) )
{
/* Restaurar línea*/
for ( int i = 0; i lt; 9; i) destino[i][línea] = saveline[i];
devolver _FAILED
}
Devolver ÉXITO
}
MAPTYPE g_result;
void on _map_ok(MAPTYPE mapa)
{
memcpy(g_result, map, sizeof(MAPTYPE) );
}
#include "windows.
int _tmain(int argc, _TCHAR* argv[])
{
MAPTYPE destino;
memset(dest, 0, sizeof(MAPTYPE));
srand( GetTickCount()
/ * Complete aleatoriamente la primera línea*/
char ch[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9} for ( int i = 0; i lt; 9; i )
{
int p = rand()
char t = ch[p];
ch[p] = ch[i];
ch[i] = t
}
>
for ( int i = 0; i lt; 9; i ) destino[i][0] = ch[i];
if ( fill_line(dest, 0, on_map_ok) )
{
/* Recorta algunos trozos * /
for ( int i = 0; i lt; 9; i )
{
/* Ajustar el rango de valores de n cambiará la dificultad 6 3 para que sea más difícil*/
int n = (rand() 6) 3;
for ( int j = 0; j lt; 9; j ) ch[j] = j; /* ch: índice a borrar*/
for ( int j = 0; j lt ; 9 ; j )
{
int p = rand()
char t = ch[p]; ch[ p] = ch[i];
ch[i] = t;
}
for ( int j = 0; j lt; n ; j ) g_result[ch[j]][i] = 0;
}
dump_map(g_resultado); > getch ();
return 0;
}
Después de leer esto, ¿entiendes el algoritmo del Sudoku?