SUDOKU

Un tablero de sudoku es un tablero de 9x9 casillas de forma que en cada horizontal y en cada vertical hay los numeros del 1 al 9 y en cada uno de los 9 cuadrados 3x3 que no tienen casillas en común hay los numeros del 1 al 9.


El número de soluciones válidas para el sudoku estándar con tablero de 9×9 ha sido calculado por Bertram Felgenhauer en 2005 y es 6670903752021072936960.

Ese número es 9! × 722 × 27 × 27,704,267,971, cuyo último factor es primo. El resultado fue obtenido usando una mezcla de lógica y computación de "fuerza bruta". El cálculo del resultado fue simplificado considerablemente por el análisis efectuado por Frazer Jarvis confirmado independientemente por Ed Russell. Russell y Jarvis tambié demuestran que si las simetrías son tomadas en cuenta hay 5472730538 soluciones. Para el tablero de 16*16 el resultado no es conocido.
Pero esto se refiere al número de tableros. Cuando tenemos en cuenta el número de datos y la posición de estos, de forma que se obtenga solución única, este número se multiplica de forma aun desconocida.


Seguro que todos sabéis lo que es un Sudoku y que muchos de vosotros habéis resuelto (o al menos intentado) uno en alguna ocasión. Y es muy posible que algunos seáis unos auténticos “enganchados” de este interesante juego (el padre de Mamen entre ellos).

No todos los sudokus tienen la misma dificultad, eso también lo sabemos. Generalmente ésta depende de la cantidad de números que aparecen en el sudoku antes de comenzarlo y de la colocación de los mismos. Lo que sí es una norma es que todo sudoku bien planteado debe tener solución única. Teniendo en cuenta esta restricción, y partiendo de uno que tenga solución, ¿cuál es la cantidad mínima de números que deben aparecer inicialmente en el sudoku para que pueda estar bien planteado?

Sudoku con 17 casillas rellenas
Sudoku con 17 casillas rellenas, el mínimo necesario para que pueda tener solución única (aunque éste tiene más de una)

Este problema, que podríamos denominar el problema del sudoku mínimo o el problema del mínimo número de casillas rellenas, era hasta ahora un problema abierto sobre el cual ya hacía tiempo que se estaba trabajando (en Microsiervos hablaron sobre ello en este post hace más de 5 años). Pero ya no lo es, ya que el pasado domingo 1 de enero de 2012 pasó a convertirse en un problema resuelto. Se ha demostrado que el número mínimo de casillas que debe traer rellenas un sudoku para que pueda tener solución única es 17. Esto significa que todo sudoku (que tenga solución) con 16 casillas rellenas o menos seguro que tendrá más de una solución.
Los artífices de esta demostración son Gary McGuire, Bastian Tugemann y Gilles Civario, de la School of Mathematical Sc (University College Dublin, Ireland, que han colgado en arXiv su trabajo There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem. En este artículo, de solamente 36 páginas, se demuestra que no hay sudokus con 16 casillas rellenas de principio que tengan solución única mediante el estudio de todos los posibles resultados. Es decir, McGuire y su equipo han estudiado todos los posibles sudokus con 16 números colocados de principio y han visto que ninguno de ellos tiene solución única. Para no tener que comprobarlo en todos los casos posibles, unos 6,7 \cdot 10^{21}, estudiaron posibles simplificaciones atendiendo, por ejemplo, a ciertos tipos de simetrías. Obtuvieron así que tenían que estudiar unos 5500 millones de sudokus esencialmente distintos, una ardua tarea que realizaron mediante software. Vamos, fuerza bruta pero con ayudas.

Teniendo en cuenta que si un sudoku con n casillas dadas de principio tiene solución única, entonces también la tiene uno con n+1 casillas dadas, obtenemos que ningún sudoku con menos de 16 números dados de antemano tendrá solución única. Añadiendo esto a lo anterior demostramos que el número mínimo necesario para que un sudoku pueda tener única solución es 17.

Según el equipo responsable de la demostración, este resultado puede ayudar a resolver algunos problemas de teoría de grafos y puede tener aplicaciones en bioinformática y en testeo de software.

EL SOFTWARE

Empecé a tratar de desarrollar un solucionador de Sudoku en Excel usando VBA. Después de algunas interacciones con Excel, me mudé a Visual Basic usando VS2005. Después de hacer una versión del programa para tratar el Sudokus 9x9 (clásico), también adapté el código para resolver Samurai Sudoku (5 cuadrículas superpuestas de 9x9). Quería proporcionar una fuente y una demo, ya que no hay demasiados solucionadores con todas las funciones que pueda encontrar en Visual Basic para aprender.

Los solucionadores basados en lógica y la interfaz de usuario probablemente tomaron la mayor parte del trabajo; el verdadero solucionador de fuerza bruta fue en realidad bastante rápido para codificar.

INTRODUCCION

Este artículo no profundiza en las reglas del Sudoku ni en el detalle de cómo resolver los rompecabezas de Sudoku. Simplemente usa un motor de búsqueda si quieres fondo en esto. Sin embargo, el principio básico es que los números del 1 al 9 se colocan en las filas, columnas y sub-cuadrículas para que cada fila, columna y sub-cuadrícula solo contengan cada dígito una vez. Sin embargo, algunos términos se usan a continuación para explicar el código.

TERMINOLOGIA 

Celda - celda individual donde se pueden colocar los dígitos 1-9.

Pistas / datos: en la primera imagen de arriba, las celdas segunda y tercera tienen pistas de 7 y 6, respectivamente.

Candidatos / marcas de lápiz: en la imagen de arriba, la primera celda contiene tres candidatos (2, 3 y 9). Al tratar de resolver un rompecabezas, es importante hacer un seguimiento de los diversos candidatos.

Fila: un grupo de 9 celdas que van horizontalmente por la pantalla.

Columna: un grupo de 9 celdas que van verticalmente hacia abajo en la pantalla.

Subgrid: un grupo de 9 celdas organizadas en una agrupación de 3x3.

Pares: en una cuadrícula clásica de 9x9, cada celda puede "ver" hasta 20 otras celdas (las otras celdas de la fila, columna y subruta). Debido a la regla de que ningún dígito se puede repetir en una fila, celda o subred, si coloca un dígito como la solución a una celda, ese dígito se puede eliminar como candidato de cada uno de sus pares. Los pares para un Sudoku Samurai son un poco diferentes, ya que algunas células tendrán un mayor número de pares debido a las cinco cuadrículas superpuestas.

Puntos de interés

El solucionador intentará resolver acertijos usando pasos lógicos, pero también recurrirá a un algoritmo de fuerza bruta para acertijos más difíciles. En consecuencia, puede resolver la mayoría de los rompecabezas de Sudoku 9x9 clásicos de manera casi instantánea, o la mayoría de los rompecabezas de Samurai en un par de segundos (dependiendo de la computadora). Hay que admitir que existen solucionadores de C ++ que pueden resolver cientos o miles de acertijos por segundo. Sin embargo, quería algo que pudiera resolver acertijos razonablemente rápido, pero también poder pasar por los acertijos y mostrar por qué se tomaron medidas particulares de resolución.

Hay un control personalizado que usa GDI + para pintar pistas y candidatos (marcas de lápiz). Usar un montón de etiquetas individuales o similares fue demasiado lento para actualizar. La interfaz de usuario aún puede ser un poco lenta para actualizarse con los rompecabezas de Samurai, pero en general no es tan malo.

A diferencia de muchos otros solucionadores que he visto, que tienden a usar una matriz bidimensional de 81 (9) para contener posibles candidatos para cada celda, este solucionador usa una matriz única de longitud 81 para contener todos los posibles candidatos. A cada candidato se le asigna un valor usando la fórmula 2 ^ (candidato-1) para obtener un valor de bit único para cada candidato (aunque he elegido codificarlo para minimizar la necesidad de este cálculo). Por lo tanto, candidato 1 = valor de bit 1, candidato 2 = valor de bit 2, candidato 3 = valor de bit 4, candidato 4 = valor de bit 8, y candidato 5 = valor de bit 16, y así sucesivamente.

Entonces, si la celda 2 tiene los posibles 1, 3 y 4 como valores posibles, debe establecer el valor de la matriz en:

_vsCandidateAvailableBits(2) = 13 (bit values 1+4+8)

en lugar de tener que hacer algo como:

Ocultar código de copia

_vsCandidateAvailableBits (2,1) = True

_vsCandidateAvailableBits (2,3) = True

_vsCandidateAvailableBits (2,4) = True

La ventaja de este enfoque es que muchos enfoques basados en la lógica para resolver el Sudoku funcionan en subconjuntos, por lo que si desea verificar si la celda 81 solo tiene candidatos 1 y 9 disponibles, es trivial hacer una simple comprobación para ver si _vsCandidateAvailableBits ( 81) = 257 (valor de bit 1 + valor de bit 256).

El solucionador mismo se codifica como una clase y utiliza una primera búsqueda en profundidad. Seguirá buscando soluciones múltiples, o puede configurarse para salir luego de que se encuentre un número determinado de soluciones.

Dim solver As New clsSudokuSolver
' will exit if more than the entered number of solutions are found. 
solver.intQuit = intSolverQuit
solver.blnClassic = True ' or can set to false if solving a samurai puzzle
solver.strGrid = strGame ' input puzzle string 
solver.vsSolvers = My.Settings._DefaultSolvers ' solving methods

Para ejecutar el solucionador, debe llamar a solver._vsUnique () que prueba una solución única.

Luego puede hacer cosas como dim blnUnique como boolean = solver._vsUnique () para verificar si un acertijo tiene una sola solución válida o no.

Solvente de fuerza bruta

El solucionador de fuerza bruta se mantiene en su propia clase. Básicamente es un bucle iterativo que busca una solución, tratando de encontrar la mejor estimación y desentrañando las suposiciones si son incorrectas.

La primera tarea es cargar en el juego de inicio (una cadena que contenga 81 caracteres (para un Sudoku de 9x9) o cinco cadenas de 81 caracteres separadas por saltos de línea (para un Sudoku Samurai). Los datos válidos son los caracteres 1-9. para iniciar pistas y una parada completa o cero caracteres para representar celdas vacías o sin llenar.

Private Function _load(ByVal strGrid As String, Optional ByVal _
                 StrCandidates As String = "") As Boolean
    '---load puzzle---'
    _vsSteps = 1
    vsTried = 0
    ReDim _vsUnsolvedCells(0)
    Dim i As Integer
    Dim intCellOffset As Integer
    Dim strClues As String = ""
    Dim g As Integer
    Dim j As Integer
    Dim intBit As Integer
    Dim blnCandidates As Boolean = False
    Dim arrCandidates() As String = Split(StrCandidates, arrDivider)
    If arrCandidates.Length >= 81 Then blnCandidates = True
    _u = -1
    _vsCandidateCount(0) = -1
    For i = 1 To _vsCandidateCount.Length - 1
        _vsCandidateAvailableBits(i) = 511
        _vsStoreCandidateBits(i) = 0
        _vsCandidateCount(i) = -1
        If blnClassic = False Then
            If Not blnIgnoreSamurai(i) Then _vsCandidateCount(i) = 9
        Else
            _vsCandidateCount(i) = 9
        End If
        _vsLastGuess(i) = 0
        _vsCandidatePtr(i) = 1
        _vsSolution(i - 1) = 0
        _vsPeers(i) = 0
    Next

    strGrid = Trim(strGrid)
    Dim midStr As String = ""
    Dim ptr As Integer
    Dim arrayPeers(0) As String
    Dim intValue As Integer
    Dim nextGuess As Integer = 0
    Dim nextCandidate As Integer = 0
    _vsUnsolvedCells(0) = New List(Of Integer)
    Dim intMaxGrid As Integer = 5
    If blnClassic Then intMaxGrid = 1
    For g = 1 To intMaxGrid
        For i = 1 To 81
            Select Case blnClassic
                Case True
                    midStr = Mid(strGrid, i, 1)
                    intCellOffset = i
                Case False
                    midStr = Mid(strGrid, i + (81 * (g - 1)), 1)
                    intCellOffset = intSamuraiOffset(i, g)
            End Select
            Select Case Asc(midStr)
                Case 46, 48
                    '---blank---
                    If (blnClassic Or Not blnIgnoreSamurai(intCellOffset)) _
                        AndAlso _vsUnsolvedCells(0).IndexOf(intCellOffset) = -1 Then
                        _u += 1
                        _vsUnsolvedCells(0).Add(intCellOffset)
                        If blnCandidates = True Then
                            '---insert known candidates---
                            _vsCandidateAvailableBits(intCellOffset) = _
                              arrCandidates(intCellOffset - 1)
                            _vsCandidateCount(intCellOffset) = _
                              intCountBits(arrCandidates(intCellOffset - 1))
                        End If
                    End If
                Case 49 To 57
                    '---numeric 1 to 9---
                    intValue = CInt(midStr)
                    intBit = intGetBit(intValue)
                    If _vsSolution(intCellOffset - 1) = 0 Then
                        _vsSolution(intCellOffset - 1) = intValue
                        _vsCandidateCount(intCellOffset) = -1
                        If blnCandidates = False Then
                            Select Case blnClassic
                                Case True
                                    arrayPeers = arrPeers(intCellOffset)
                                Case False
                                    arrayPeers = ArrSamuraiPeers(intCellOffset)
                            End Select
                            '---remove value from peers---
                            For j = 0 To UBound(arrayPeers)
                                ptr = arrayPeers(j)
                                If _vsCandidateAvailableBits(ptr) And intBit Then
                                    _vsCandidateAvailableBits(ptr) -= intBit
                                    _vsCandidateCount(ptr) -= 1
                                End If
                            Next
                        End If
                    End If
                Case Else
                    'Debug.Print("exiting due to invalid" & _ 
                    ' "character " & Asc(midStr))
                    _load = False
                    Exit Function
            End Select
            strClues += midStr
        Next
        If Not blnClassic Then strClues += vbCrLf
    Next
    _load = True
    strFormatClues = strClues
End Function

Una vez que tenemos una entrada válida, llamamos a una función que realizará un ciclo para probar todas las soluciones (aunque es posible establecer un valor (intQuit) para salir cuando se haya encontrado una cantidad deseada de soluciones). Por ejemplo, si quiere asegurarse de que un acertijo es válido (por ejemplo, solo tiene una única solución única), entonces intQuit puede establecerse en '2' (por lo que saldrá después de encontrar dos soluciones). Sin embargo, puede haber instancias (como se explica más adelante) donde encontrar soluciones múltiples puede ser útil para resolver acertijos Samurai.

La función de resolución principal se establece a continuación.

Private Function _vsbackTrack(ByVal strGrid As String, _
        ByRef StrSolution As String, Optional ByVal _
        StrCandidates As String = "") As Boolean 
    Dim intMax As Integer = 0
    Dim intSolutionMax As Integer = 0
    ReDim Solutions(0) ' array to hold solutions to the puzzle 
    Dim i As Integer 
    Dim j As Integer 
    Dim intSolutions As Integer ' counts number of puzzle solutions 
    Dim testPeers(0) As String 
    Dim tempPeers As String 
    Dim nextGuess As Integer = 0
    Dim nextCandidate As Integer = 0
    Select Case blnClassic
    ' sets up maximum length of arrays depending
    ' on whether it is a 9x9 or samurai puzzle
        Case True
            intMax = 81
            intSolutionMax = 80
        Case False
            intMax = 441
            intSolutionMax = 440
    End Select
    ReDim _vsSolution(intSolutionMax)
    ReDim _vsPeers(intMax)
    ReDim _vsCandidateCount(intMax)
    ReDim _vsCandidateAvailableBits(intMax)
    ReDim _vsCandidatePtr(intMax)
    ReDim _vsLastGuess(intMax)
    ReDim _vsStoreCandidateBits(intMax)
    ReDim _vsRemovePeers(intMax)

    If Not _load(strGrid:=strGrid, StrCandidates:=StrCandidates) Then
        ' input puzzle failed to load properly, so exit
        intCountSolutions = intSolutions
        Exit Function
    End If

    '---NOTE: Code for logic based solving methods is usually called here---'
    '---But removed for purposes of explaining the brute force solver---'
    '---END NOTE---'

    _vsUnsolvedCells(0).Sort() '---order an array list of empty/unsolved cells---'

    '---NOTE: Some specific code removed here for dealing with samurai puzzles---'
    '---This is discussed separately below---'
    '---END NOTE---'

    '---setup peer array. This is intended to save processing time by---'
    '---having the 'peers' for each empty cell pre-loaded, rather than needing---'
    '---to recalculate peers throughout the iterative puzzle solving process---'
    For i = 0 To _u
        tempPeers = ""
        Select Case blnClassic
            '---this code retrieves a hard coded list of 'peers' (other cells---'
            '---that share a row, column or subgrid with the empty cell---'
            Case True
                testPeers = arrPeers(_vsUnsolvedCells(0).Item(i))
            Case False
                testPeers = ArrSamuraiPeers(_vsUnsolvedCells(0).Item(i))
        End Select
        For j = 0 To UBound(testPeers)
            '---Check to see if each peer is unsolved or not. 
            '---If the peer is empty/unsolved, then add it to a string---'
            If _vsUnsolvedCells(0).IndexOf(CInt(testPeers(j))) > -1 Then
                If tempPeers = "" Then
                    tempPeers = testPeers(j)
                Else
                    tempPeers += "," & testPeers(j)
                End If
            End If
        Next
        _vsPeers(_vsUnsolvedCells(0).Item(i)) = tempPeers 
        '---save the list of peers for each empty cell---'
    Next
    '---end setup peer array---'

    If _u = -1 Then
        '---puzzle already solved by logic---'
        Exit Function
    End If

    While _vsSteps <= _u + 1 AndAlso _vsSteps > 0
        '---look for the next unfilled cell. The routine intFindCell looks---' 
        '---for the next empty cell containing only one candidate---'
        '---or failing that, the unfilled cell with the lowest number of---'
        '---candidates which will result in the maximum number of possible---'
        '---eliminations. There may be room for improvement/experimentation in 
        '---terms of picking the next cell to test---'
        If nextGuess = 0 Then nextGuess = intFindCell()
        If nextGuess > 0 Then
            '---we have an empty cell, so select the next candidate---' 
            '---to test in this cell---'
            nextCandidate = IntNextCandidate(nextGuess)
            If nextCandidate > 0 Then
                vsTried += 1
                MakeGuess(nextGuess, nextCandidate)
                nextGuess = 0
            Else
                If _vsSteps <= 1 Then
                    '---we've reached the end of the search
                    '---there are no more steps to try---'
                    Select Case intSolutions
                        Case 0
                            '---invalid puzzle (no solution)---'
                            _vsbackTrack = False
                            intCountSolutions = 0
                            Exit Function
                        Case 1
                            '---single solution---'
                            _vsbackTrack = True
                            intCountSolutions = 1
                            Exit Function
                        Case Else
                            '---multiple solutions---'
                            _vsbackTrack = False
                            intCountSolutions = intSolutions
                            Exit Function
                    End Select
                Else
                    '---need to go back...no remaining candidates for this cell---'
                    UndoGuess(nextGuess)
                End If
            End If
        Else
            If _vsSteps = 0 Then
                _vsbackTrack = False
                '---invalid puzzle---'
                intCountSolutions = intSolutions
                Exit Function
            Else
                '---cannot go further...so need to go back---'
                UndoGuess()
            End If
        End If

        If _vsSteps > _u + 1 Then
            '---we have filled all the unfilled cells with a solution---'
            '---so increase array size and add next solution to solution array---'
            intSolutions += 1
            ReDim Preserve Solutions(intSolutions - 1)
            Select Case blnClassic
                Case True
                    StrSolution = strWriteSolution(intGrid:=1)
                Case False
                    StrSolution = strWriteSolution()
            End Select
            Solutions(intSolutions - 1) = StrSolution

            If intSolutions = intQuit Then
                '---quit if number of solutions exceeds a given number---'
                _vsbackTrack = False
                intCountSolutions = intSolutions
                Exit Function
            End If

            '---solution found so backtrack---'
            UndoGuess()
        End If
    End While
End Function
Una parte clave del solucionador de fuerza bruta es hacer una 'mirada hacia adelante' para tratar de elegir la siguiente celda mejor sin carga para tratar de colocar un candidato disponible. La función a continuación tiene como objetivo hacer esto buscando una celda vacía con la cantidad mínima de candidatos disponibles. Si hay una celda con solo un candidato, esto se selecciona, ya que es una suposición óptima. De lo contrario, la intención es buscar una celda sin llenar con el menor número de candidatos (ya que esto reduce el espacio de búsqueda global / tiempo de resolución). Como un refinamiento adicional, si hay varias celdas sin llenar, cada una con el mismo número de candidatos, se usa un ciclo adicional para determinar cuál de estas celdas tiene el mayor número de pares (sobre la base de que cualquier conjetura tendrá la mayor probabilidad de eliminando más candidatos del rompecabezas). Puede haber otros enfoques que puedan ser probados, ya que encontrar el mejor movimiento posible más probable es que aumente la velocidad de resolución.