Sudoku

Que es sudoku?

• Es un juego matemático donde el objetivo del es rellenar una cuadrícula que puede variar desde 4X4 hasta 9X9

Como completar un sudoku?

• Para ganar, el jugador debe rellenar los cuadrados con numeros, de manera que no se repitan en la fila ni en la columna en la que este.
• Los numeros que pueden rellenar los cuadrados varian depende el sudoku.
• EJ: Si es de 4X4 solo se pueden ingresar los numero del 1 al 4.

Sudoku terminado

Sudoku

Pasos

Asignar un color a cada numero

Partir de la posicion inicial del Sudoku

Colorear

• Seleccione un numero
• Las casillas que esten en la misma fila colocar puntos del color previamente asignado al numero
• Repetir el paso 2, solo que esta vez en las columna donde se encuentre el numero
• Repetir con cada numero

Como quedaria coloreado

Asignar numeros a las casillas vacias

• Observar que casillas tienen 3 colores
• A las casillas que tienen 3 colores, revisar que color le falta para que tenga los 4 colores
• El color que le falta es el numero que puede ir en la casilla
• Rellenar la casilla con el numero
• Hacer el proceso de coloracion nuevamente

Relleno de casilla con 3 colores.

Volvemos a revisar cada elemento y coloreamos.

Metodo con algoritmo de coloracion

• Dibujar una gráfica de un grafo colocando vertices
• Colorear los vértices que representan las pistas de diferente color por cada número.
• Seleccionar un vértice coloreado, conectarlo con edges del mismo color y vértices que no pueden ser del mismo color.

Metodo con algoritmo de coloracion

• 4. Ordenar los vértices por grado de mayor a menor y tomar los de mayor grado
• 5. Si hay vértices que pueden ser coloreados solo por un color, entonces se colorearlo, regresar al paso 3. Si no hay tales vértices,pasar al siguiente paso.

Metodo con algoritmo de coloracion

• 6. De los vértices seleccionados, tomar aquel que es adyacente al mayor número de vértices no coloreados y colorearlo con el color de menor valor que no está siendo usado por sus vecinos. Si no existe tal vértice, se seleccionar uno aleatoriamente. Regresar al paso 3

Metodo con algoritmo de coloracion

• Terminar el sudoku

Maneras de representar el suduko con grafo.

Untitled Slide