Resolviendo Sudoku usando Algoritmo Bitwise

Dada una array de 9 × 9 parcialmente llena, se deben asignar dígitos (del 1 al 9) a las celdas vacías para que cada fila, columna y subarray de tamaño 3 × 3 contenga exactamente una instancia de los dígitos del 1 al 9.

La solución de retroceso puro para este problema se describe aquí . Se recomienda encarecidamente que el lector sepa cómo funciona la solución de retroceso puro antes de continuar.

En la solución de retroceso puro, iteramos a través de la array y cada vez que se encuentra una celda vacía (celda sin ningún dígito), asignamos un dígito a la celda, donde dicho dígito no está presente en la columna actual, fila y 3 × 3 subarray. Después de asignar el dígito a la celda actual, verificamos recursivamente si esta asignación conduce a una solución válida o no. Si la asignación no conduce a una solución válida, probamos con el siguiente dígito válido para la celda vacía actual. Y si ninguno de los dígitos conduce a una solución válida, entonces la instancia es inviable.

1. If there is no empty cell in the matrix M:
    return true
2. Let (i, j) be an empty cell in the matrix M
3. For i from 1 to 9:
    3.1. If i is not present in the row r, in column c, and the 3x3
    submatrix of (r, c):
        a) M(r, c) = i 
        b) recursively try fill in remaining empty cells
        c) If recursion was successful:
            return true
        d) M(r, c) = 0
4. return false

• El paso (3.1) se puede realizar recorriendo la respectiva fila, columna y subarray de 3×3. Sin embargo, podemos acelerar este paso preprocesando esos dígitos antes del retroceso, y este es el punto principal de este artículo. Entonces, consideremos la siguiente array como ejemplo:

  

  Podemos realizar un seguimiento de los dígitos de una fila, columna y subarray de 3×3 en los bits de un número entero, por ejemplo, considere la primera fila de la array anterior, podemos almacenar esos dígitos de la siguiente manera:

  bits order - 9 8 7 6 5 4 3 2 1
  bits       - 0 0 1 0 1 0 1 0 0
  

  Y luego, en el paso (3.1), podemos usar operaciones bit a bit para determinar si el dígito i está en la fila, columna y subarray de 3×3. Sea RowDigits[r] el entero que contiene los dígitos de la fila r, entonces podemos verificar si el dígito i está en la fila r con la siguiente expresión:

  rowsDigits[r] & (1<<(i - 1))
  

  Si la expresión anterior es igual a 0, entonces el dígito i no está presente en la fila r. Por ejemplo, si r = 0 e i = 1, entonces:

  bits order                - 9 8 7 6 5 4 3 2 1
  rowDigits[r]              - 0 0 1 0 1 0 1 0 0
  1<<(i - 1)                - 0 0 0 0 0 0 0 0 1
  rowDigits[r]&(1<<(i - 1)) - 0 0 0 0 0 0 0 0 0
  

• Una vez que la condición del paso (3.1) es verdadera, se ejecuta el paso (3.1a), y luego necesitamos insertar el dígito i en rowDigits, columnDigits y subMatrixDigits, podemos hacer esto con la siguiente expresión:

  rowsDigits[r] | (1<<(i - 1))
  

  Por ejemplo, si r = 0 e i = 1, entonces:

  bits order                - 9 8 7 6 5 4 3 2 1
  rowDigits[r]              - 0 0 1 0 1 0 1 0 0
  1<<(i - 1)                - 0 0 0 0 0 0 0 0 1
  rowDigits[r]|(1<<(i - 1)) - 0 0 1 0 1 0 1 0 1
  

• En el caso de que la condición del paso (3.1c) sea falsa, se ejecuta el paso (3.1d), y luego necesitamos eliminar el dígito i de rowDigits, columnDigits y subMatrixDigits, podemos hacerlo con la siguiente expresión:

  rowsDigits[r] & ~(1<<(i - 1))
  

  Por ejemplo, si r = 0 e i = 1, entonces:

  bits order                - 9 8 7 6 5 4 3 2 1
  rowDigits[r]              - 0 0 1 0 1 0 1 0 0
  1<<(i - 1)                - 0 0 0 0 0 0 0 0 1
  ~(1<<(i - 1))             - 1 1 1 1 1 1 1 1 0
  rowDigits[r]&~(1<<(i - 1) - 0 0 1 0 1 0 1 0 0
  

A continuación se muestra la implementación del enfoque anterior.

// C++ program to solve sudoku
#include <iostream>
#include <string.h>
  
// N is used for the size of Sudoku grid.  
// Size will be NxN  
#define N 9
  
using namespace std;
  
/* A utility function to print grid */
void printGrid(int grid[N][N])  
{  
    for (int row = 0; row < N; row++)  
    {  
    for (int col = 0; col < N; col++)  
            cout << grid[row][col] << " ";  
        cout << endl; 
    }  
}
/* Takes a partially filled-in grid and attempts  
to assign values to all unassigned locations in  
such a way to meet the requirements for 
Sudoku solution (non-duplication across rows, 
columns, and boxes) */
bool solve(int r, int c, int board[9][9], 
           int submatrixDigits[3][3], 
           int rowDigits[9], 
           int columnDigits[9])
{
    if (r == 9)
    {
          
        return true;
    }
    if (c == 9)
    {
        return solve(r + 1, 0, board, submatrixDigits, 
                     rowDigits, columnDigits);
    }
      
    if (board[r] == 0) {
        for (int i = 1; i <= 9; i++)
        {
            int digit = 1 << (i - 1);
              
            if (!((submatrixDigits[r / 3] & digit) 
                  || (rowDigits[r] & digit) 
                  || (columnDigits & digit)))
            {
                // set digit
                submatrixDigits[r / 3] |= digit;
                rowDigits[r] |= digit;
                columnDigits |= digit;
                board[r] = i;
                  
                if (solve(r, c + 1, board, submatrixDigits,
                          rowDigits, columnDigits))
                {
                    return true;
                }
                else
                {
                    submatrixDigits[r / 3] &= ~digit;
                    rowDigits[r] &= ~digit;
                    columnDigits &= ~digit;
                    board[r] = 0;
                }
            }
        }
        return false;
    }
    return solve(r, c + 1, board, submatrixDigits, 
                 rowDigits, columnDigits);
}
  
// Function checks if Sudoku can be
// solved or not
bool SolveSudoku(int board[9][9])
{
    int submatrixDigits[3][3];
    int columnDigits[9];
    int rowDigits[9];
      
    for (int i = 0; i < 3; i++)
        memset(submatrixDigits[i], 0, 3 * sizeof(int));
      
      
    memset(rowDigits, 0, 9 * sizeof(int));
    memset(columnDigits, 0, 9 * sizeof(int));
      
    // get 3x3 submatrix, row and column digits
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (board[i][j] > 0)
            {
                int value = 1 << (board[i][j] - '1');
                submatrixDigits[i / 3][j / 3] |= value;
                rowDigits[i] |= value;
                columnDigits[j] |= value;
            }
    // Backtrack
    if (solve(0, 0, board, submatrixDigits,
              rowDigits, columnDigits))
        return true;
    else
        return false;
}
  
  
// Driver Code 
int main()  
{  
    // 0 means unassigned cells  
    int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},  
                      {5, 2, 0, 0, 0, 0, 0, 0, 0},  
                      {0, 8, 7, 0, 0, 0, 0, 3, 1},  
                      {0, 0, 3, 0, 1, 0, 0, 8, 0},  
                      {9, 0, 0, 8, 6, 3, 0, 0, 5},  
                      {0, 5, 0, 0, 9, 0, 6, 0, 0},  
                      {1, 3, 0, 0, 0, 0, 2, 5, 0},  
                      {0, 0, 0, 0, 0, 0, 0, 7, 4},  
                      {0, 0, 5, 2, 0, 6, 3, 0, 0}};  
    if (SolveSudoku(grid) == true)  
        printGrid(grid);  
    else
        cout << "No solution exists";  
    
    return 0;  
}  

3 1 6 5 2 8 4 3 4 
5 2 2 1 3 4 5 6 7 
3 8 7 5 6 7 1 3 1 
1 2 3 3 1 5 4 8 6 
9 3 4 8 6 3 2 1 5 
5 5 6 2 9 1 6 7 3 
1 3 1 4 5 2 2 5 8 
2 4 3 6 1 8 7 7 4 
6 5 5 2 7 6 3 2 1