c-Programm zu überprüfen, gültige sudoku

Können Sie überprüfen, jedes der kleineren Quadrate, ob Sie gültig sind oder nicht.Zum Beispiel, wenn n=9 Sie haben zu prüfen, jede der 3 by 3 Quadrate.Um zu überprüfen, jedes kleine Quadrat, das Sie verwenden können, ein array von 10 Elementen und überprüfen Sie, ob der 1 to 9 Wert wiederholt wird oder nicht.

Des Algorithmus ist wie folgt

  for each of the smaller grids
      if(any of the digit repeats in a smaller grid)
      return 0;
  return 1;//valid

Folgenden ist ein code, das gleiche zu tun

  //A is the grid
  int small=sqrt(n);
  for(int i=0;i<small;i++)
  {
     for(int j=0;j<small;j++)
     {
        int row=small*i;//this will find the corresponding row
        int col=small*j;//this will find the corresponding column
        vector<int> used(10,0)
        for(int p=row; p<row+small; p++) {
                for(int q=col; q<col+small; q++) 
                {
                    if(A[p][q]=='0')//0 is not valid
                    return 0;
                    if(used[A[p][q]-'0']==1)//this digit has already been used
                    return 0;
                    if(used[A[p][q]-'0']) return 0;
                    used[A[p][q]-'0']=1;//now this particular digit has occurred and should not occur again
                }
         }
      }
 }
 //if all's well return 1
 return 1;

Beachten Sie, dass der obige code wird davon ausgegangen, dass die gesamte raster gefüllt ist und nicht leer ist.Wenn Sie überprüfen möchten, ein teilweise gefülltes grid,führen Sie einen check.

bool validateMatrix(int g_iMatrix1[][MAXCOLS],
                     int iROWS,
                     int iCOLS)
{
    bool bRowUsed[MAXROWS][MAXCOLS]   = {0};
    bool bColUsed[MAXROWS][MAXCOLS]   = {0};
    bool bBlockUsed[MAXROWS][MAXCOLS] = {0};

    //Matrix to keep record if current value is already set in current row..
    memset(bRowUsed, false, (MAXROWS) * (MAXCOLS));

    //Matrix to keep record if current value is already set in current column..
    memset(bColUsed, false, (MAXCOLS) * (MAXCOLS));

    //Matrix to keep record if current value is already set in current block of iSQRT * iSQRT..
    //Lets assume the matrix is of size 9 * 9..
    //So there will be 9 block of 3 * 3..
    //Number the blocks from left to right as 0 to 8..
    //We will be mapping 0 the block to 0th row, 1st block to 1st row, 2nd block to 2nd row and so on..
    memset(bBlockUsed, false, (MAXROWS) * (MAXCOLS));

    int iRows = 0,iCols = 0;
    int iSQRT = int(sqrt(MAXCOLS));

    for(iRows = 0;iRows < iROWS;iRows++)
    {
        for(iCols = 0;iCols < iCOLS;iCols++)
        {
            if(bRowUsed[iRows][g_iMatrix1[iRows][iCols] - 1] == true)   
            {
                return false;
            }
            if(bColUsed[g_iMatrix1[iRows][iCols] - 1][iCols] == true)
            {
                return false;
            }

            //Number the blocks from left to right as 1 to 9..
            //We will be mapping 0 the block to 0th row, 1st block to 1st row, 2nd block to 2nd row and so on..
            //((iRows /iSQRT) * iSQRT) + (iCols /iSQRT) will map the block with above logic..
            if(bBlockUsed[((iRows / iSQRT) * iSQRT) + (iCols / iSQRT)][g_iMatrix1[iRows][iCols] - 1] == true)
            {
                return false;
            }

            bRowUsed[iRows][g_iMatrix1[iRows][iCols] - 1] = true;
            bColUsed[g_iMatrix1[iRows][iCols] - 1][iCols] = true;
            bBlockUsed[((iRows / iSQRT) * iSQRT) + (iCols / iSQRT)][g_iMatrix1[iRows][iCols] - 1] = true;
        }
    }

    return true;
}