Understanding this C function

Question

I'm trying to understand how this function works, I have studied several algorithms to generate sudoku puzzles and found out this one.

Tested the function and it does generates a valid 9x9 Latin Square (Sudoku) Grid. My problem is that I can't understand how the function works, i do know the struct is formed by to ints, p and b , p will hold the number for the cell in the table, But after that I don't understand why it creates more arrays (tab 1 and tab2) and how it checks for a latin square =/ etc , summarizing , I'm completely lost.

I'm not asking for a line by line explanation, the general concept behind this function. would help me a lot !

Thanks again <3

int sudoku(struct sudoku tabla[9][9],int x,int y)
{
int tab[9] = {1,1,1,1,1,1,1,1,1};
        int i,j;
  for(i=0;i<y;++i)
  {
        tab[tabla[x][i].p-1]=0; 

  for(i=0;i<x;++i)
  { 
        tab[tabla[i][y].p-1]=0;
  }
  for(i=(3*(x/3));i<(3*(x/3)+3);++i)
  { 
        for(j=(3*(y/3));j<y;++j)
        {
         tab[tabla[i][j].p-1]=0; 
        }
  }
    int n=0;
   for(i=0;i<9;++i)
   {
    n=n+tab[i];
   }

    int *tab2; 
    tab2=(int*)malloc(sizeof(int)*n);

    j=0; 
    for(i=0;i<9;++i)
    { if(tab[i]==1)
      {
       tab2[j]=i+1;
            j++;
      }
    }
    int ny, nx;
    if(x==8)
    {
        ny=y+1; 
        nx=0;   
    }
    else
    {
        ny=y; 
        nx=x+1;
    }

    while(n>0)
    {
        int los=rand()%n;
        tabla[x][y].p=tab2[los];

        tab2[los]=tab2[n-1]; 

        n--;

        if(x==8 && y==8)
        {
            return 1;
        }

        if (sudoku(tabla,nx,ny)==1)
        {
           return 1;
        } 

    }
    return 0;
}

EDIT Great, I now understand the structure, thanks lijie's answer. What I still don't understand is the part that tries out the values in random order). I don't understand how it checks if the random value placement is valid without calling the part of the code that checks if the movement is legal, also, after placing the random numbers is it necessary to check if the grid is valid again? –

Answer 1

Basically, the an invocation of the function fills in the positions at and "after" (x, y) in the table tabla, and the function assumes that the positions "prior" to (x, y) are filled, and returns whether a legal "filling in" of the values is possible.

The board is linearized via increasing x, then y.

The first part of the function finds out the values that are legal at (x, y), and the second part tries out the values in a random order, and attempts fills out the rest of the board via a recursive call.

There isn't actually a point in having tab2 because tab can be reused for that purpose, and the function leaks memory (since it is never freed, but aside from these, it works).

Does this make sense to you?

EDIT

The only tricky area in the part that checks for legal number is the third loop (checking the 3x3 box). The condition for j is j < y because those values where j == y are already checked by the second loop.

EDIT2

I nitpick, but the part that counts n and fills tab2 with the legal values should really be

int n = 0;
for (i = 0; i < 9; ++i) if (tab[i]) tab[n++] = i+1;

hence omitting the need for tab2 (the later code can just use tab and n instead of tab2). The memory leak is thusly eliminated.

EDIT

Note that the randomness is only applied to valid values (the order of trying the values is randomized, not the values themselves).

The code follows a standard exhaustive search pattern: try each possible candidate value, immediately returning if the search succeeds, and backtracking with failure if all the candidate values fail.