Reglas de Sudoku
En los juegos de Sudoku, la cuadrícula clásica de nueve jaulas que consta de 9 × 9 = 81 células, y también forma 3 × 3 = 9 cuadrículas pequeñas de nueve jaulas. Se requiere completar los números 1 ~ 9 en 81 celdas pequeñas, y los números no se pueden repetir en cada fila, columna y cada pequeña cuadrícula de nueve cagas.
Habilidades de sudoku
Mis pensamientos
Diseño e implementación de soluciones
Solo se utiliza una matriz bidimensional para almacenar el esquema de Sudoku, se usa una matriz unidimensional como pila y se usa una variable booleana como identificación de retroceso.
1. Definición variable:
Problema var = [// Esta es la cuestión de la dificultad 10.7 mencionada en el libro [8,0,0,0,0,0,0,0,0,0], [0,0,3,6,0,0,0,0,0,0], [0,7,0,0,9,0,2,0,0], [0,5,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,4,5,7,0,0,0], [0,0,0,1,0,0,0,0,3,0], [0,0,1,0,0,0,0,0,6,8], [0,0,8,5,0,0,0,0,1,0], [0,9,0,0,0,0,0,0,4,0,0,0]] var stack = [], flag = false;
2. Determinación de la efectividad del plan:
La característica de hash de los objetos JavaScript se utiliza completamente. Para facilitar la depuración, el valor de retorno de la función es 0 cuando es válido, y hay tres situaciones en las que no es válido: conflicto de filas, conflicto de columna y conflicto de red de nueve partes, que devuelven 1, 2 y 3 respectivamente. Lo usé en el juicio temprano y luego agregué el juicio relevante de veinte cuadros. Esta función ya no se usa al buscar la respuesta.
función checkValid (sudo) {let subsudo = {} // variable auxiliar utilizada para determinar si la novena cuadrícula conflictos para (let i = 0; i <9; i ++) {let row = {}, col = {} // variable auxiliar utilizada para determinar si las raíes y las columnas conflictos para (let j = 0; j <9; j ++) sudo [i] [j], cur2 = sudo [j] [i] // juicio de la fila y columna de variable autorizada al mismo tiempo si (fila [cur1]) // El elemento actual ha aparecido en la fila, y el juicio de cero está optimizado. Cuando la clave es 0, el valor es 0, no se requiere un juicio adicional. Regresar 1; // El código de error de retorno más la fila [cur1] = cur1 // El elemento actual no aparece en la fila y se almacena en la variable auxiliar si (col [cur2]) // El juicio de la columna es similar a la fila. El juicio de cero está optimizado. Cuando la clave es 0, el valor es 0, y no hay necesidad de juicio adicional. Regresar 2; else col [cur2] = cur2; Let Key = Math.Floor (I/3)+'-'+Math.floor (j/3) // Las diferentes claves se generan para diferentes cuadrículas de nueve clientes de nueve si (subsudo [key]) {// El juicio de cero ya está allí, y el juicio de cero está optimizado. Cuando la clave es 0, el valor es 0, y no hay necesidad de un juicio adicional si (subsudo [clave] [cur1]) // El juicio de una cuadrícula nueve-Client es similar al de Row Devuelve 3 más subsudo [clave] [Cur1] = Cur1} más y guarde el primer elemento en él subsudo [clave] [cur1] = cur1}}} return 0; // El programa puede ejecutar esto, lo que indica que el plan es válido} 3. Determinación relevante de veinte categorías El principio es el mismo que el juicio general, y lo más destacado radica en la posicionamiento de la pequeña cuadrícula de nueve jaulas. función check20grid (sudo, i, j) {let row = {}, col = {}, subsudo = {} // suministro variable para (vamos k = 0; k <9; k ++) {vamos cur1 = sudo [i] [k], cur2 = sudo [k] [j] if (cur1) {// El elemento actual ha aparecido en la fila, y el juicio de cero optimizado. Cuando la clave es 0, el valor es 0, y no hay necesidad de juicio adicional si (fila [cur1]) return 1; // El código de error de retorno más la fila [cur1] = cur1 // El elemento actual no aparece en la fila, y se almacena en la variable auxiliar} if (cur2) {// El juicio de la columna es similar a la fila. El juicio de pérdida cero está optimizado. El valor es 0 cuando la clave es 0. No hay necesidad de juicio adicional si (col [cur2]) return 2; else col [cur2] = cur2; } // Las coordenadas de la variable de bucle de conversión a la novena cuadrícula let key = sudo [math.floor (i/3)*3 + math.floor (k/3)] [Math.floor (j/3)*3 + Math.floor (k%3)] if (subsudo [clave]) // El juicio de la red es similar a la fila. El juicio de pérdida cero está optimizado. El valor es 0 cuando la clave es 0. No hay necesidad de retorno de juicio adicional 3 más subsudo [clave] = clave} return 0;}4. Solución transversal
El uso de elementos con valor inicial de cero en el estado de elementos es una característica pendiente, y con la asistencia de la pila, no se abre un espacio de almacenamiento adicional.
función findanswer () {para (let i = 0; i <9; i ++) {para (let j = 0; j <9;) {if (problema [i] [j] === 0 || flag) {// La posición actual es el primer procesamiento del elemento que se determinará o de regreso a la posición actual. Las dos situaciones parecen ser diferentes, pero de hecho el procesamiento es el mismo. Agregue 1 solo bandera = falso; Sea k = problema [i] [j] + 1; // Buscar para avanzar hacia el siguiente valor legal mientras (k <10) {// bucle para encontrar el siguiente problema de valor legal [i] [j] = k; // Complete if (check20grid (problema, i, j) == 0) {// El valor predeterminado es legal, y el juicio de veinte frame correspondiente es stack.push ([i, j ++]) // almacenar el punto de traza y volver a romper; } k ++; } if (k> 9) {// El valor legal no se puede encontrar en la posición actual, el problema de traza [i] [j] = 0; // regresa antes del traza de dejar rt = stack.pop (); // recuperar la información de traza en la pila if (! Rt) // sin juicio de solución, return 0 return 0; i = rt [0] // viajar j = rt [1] bandera = true; }} else {// El número de posición actual se da j ++; }}} return 1; // encontré con éxito un conjunto de soluciones}