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

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

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

#include <QTime>

const short N = 9;

typedef int TCandidat[N];
typedef int Matrix9x9[N][N];

class SudokuMatrixGenerator
{
public:
    SudokuMatrixGenerator();
    Matrix9x9& getGenerateSudokuMatrix();

private:
    void Cand_Init(TCandidat a);
    int Cand_to_Number(TCandidat a);
    int Cand_Count(TCandidat a);

    void Init_9_9(int matrix[N][N]);
    int Unic_RCM(int matrix[N][N], int a, int b, int val);

    void Step1(int matrix[N][N]);
    void Step2(int matrix[N][N]);

    void clearAllVar();

private:
    TCandidat mesh[N][N];
    TCandidat temp_cand;

    Matrix9x9 start;
    Matrix9x9 board;

    int tempi;
    int tempj;
    int Rall_number;
    int cont;
    int old_opened;
};

SudokuMatrixGenerator::SudokuMatrixGenerator()
{
 qsrand(QTime(0,0,0).secsTo(QTime::currentTime()));
}

Matrix9x9& SudokuMatrixGenerator::getGenerateSudokuMatrix()
{
    clearAllVar();
    Step1(board);
    return board;
}

void SudokuMatrixGenerator::clearAllVar()
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            for(int z = 0; z < N; z++)
            {
                mesh[i][j][z] = 0;
            }

    for(int i = 0; i < N; i++)
    {
        temp_cand[i] = 0;
    }

    Init_9_9(start);
    Init_9_9(board);
    tempi       = 0;
    tempj       = 0;
    Rall_number = 0;
    cont        = 0;
    old_opened  = -1;
}

void SudokuMatrixGenerator::Cand_Init(TCandidat a)
{
    for(int i = 0; i < N; i++)
    {
        a[i] = 1;
    }
}

int SudokuMatrixGenerator::Cand_Count(TCandidat a)
{
    int c = 0;
    for(int i = 0; i < N; i++)
    {
        if(a[i] == 1)
        {
            c++;
        }
    }
    return c;
}

void SudokuMatrixGenerator::Init_9_9(int matrix[N][N])
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
        {
            matrix[i][j] = 0;
        }
}

int SudokuMatrixGenerator::Unic_RCM(int matrix[N][N], int a, int b, int val)
{
    int i, j, flag = 0;
    // unic in a row
    for(j = 0; j < N; j++)
    {
        if(matrix[a][j] == val)
        {
            flag++;
        }
    }

    if(flag == 0) //unikalno v stroke, proverjaem stolbets
    {
        for(i = 0; i < N; i++)
        {
            if(matrix[i][b] == val)
            {
                flag++;
            }
        }

    }
    if(flag == 0) //unikalno i v stroke, i v stolbtse, proverim sector
    {
        for(i = (a / 3) * 3; i < (a / 3) * 3 + 3; i++)
            for(j = (b / 3) * 3 ;j < (b / 3) * 3 + 3; j++)
            {
                if(matrix[i][j] == val)
                {
                    flag++;
                }
            }
    }
    if(flag == 0)
    {
        return 1; // chislo unikalno
    }else
    {
        return 0; // chislo ne unikalno
    }
}

int SudokuMatrixGenerator::Cand_to_Number(TCandidat a)
{
    int i,c=0;
    for(i=0;i<N;i++)
        if(a[i]==1)
        {
            c=i+1;
            break;
        }
    return c;
}

void SudokuMatrixGenerator::Step1(int board[N][N])
{
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            board[i][j]=start[i][j];
    // find a place for a value
    do
    {
        tempi=qrand()%N;
        tempj=qrand()%N;
    }
    while(board[tempi][tempj]!=0);
    // cout<<"\nposition:"<<tempi<<" "<<tempj;
    //find a value
    int val_count=0, temp_val;
    Cand_Init(temp_cand);
    while(val_count<N)
    {
        do
        {
            temp_val=qrand()%N;
        }
        while(temp_cand[temp_val]==0);// eto znachenie ushe vibiralos
        val_count++;
        temp_cand[temp_val]=0;
        if(Unic_RCM(board, tempi,tempj, temp_val+1)==1)
        {
            board[tempi][tempj]=temp_val+1;
            start[tempi][tempj]=temp_val+1;
            break;
        }
    }

    if(Rall_number<=50)
    {
        //cout<<endl<<"Rall_number="<<Rall_number;
        if(val_count==8)
            Step1(board); //rekursija
        else
            Step2(board); // popitka reshenija
    }
    else
    {
        if(cont<30)
        {
            Rall_number=0;
            //cout<<endl<<"cont="<<cont;//getch();
            for(int i=0;i<15;i++)
            {
                tempi=qrand()%N;
                tempj=qrand()%N;
                start[tempi][tempj]=0;
            }
            cont++;
            Step1(board);
        }
        //cout<<endl<<"Rall_number="<<Rall_number<<"!!! Stop!!!";
    }
}

void SudokuMatrixGenerator::Step2(int board[N][N])
{
    int i,j,k1,k2;
    // cout<<endl<<"position:"<<tempi<<" "<<tempj;
    //cout<<endl<<"val -= "<<board[tempi][tempj]<<endl;

    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
            Cand_Init(mesh[i][j]);

    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
            if (board[i][j]!=0)// v jachejku vpisano chislo
            {
                //zapreschaem v stolbtse
                for(k1=0;k1<N;k1++)
                    mesh[k1][j][board[i][j]-1]=0;

                //zapreschaem v stroke
                for(k2=0;k2<N;k2++)
                    mesh[i][k2][board[i][j]-1]=0;
                // sektor
                for(k1=(i/3)*3;k1<(i/3)*3+3;k1++)
                    for(k2=(j/3)*3;k2<(j/3)*3+3;k2++)
                        mesh[k1][k2][board[i][j]-1]=0;
                //sozdaem masku jachejki (i,j)
                for(k1=0;k1<N;k1++)
                    mesh[i][j][k1]=0;
                mesh[i][j][board[i][j]-1]=1;

            }
    //jachejki, gde vse chisla zaprescheni
    int flag=0, t=0;
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
            if (Cand_Count(mesh[i][j])==0) flag++;
    if (flag!=0) //net reshenija
    {
        //cout<<endl<<"Net reshenija! Otkat poslednego izmenenija!"<<endl;
        start[tempi][tempj]=0;
        Rall_number++;
        Step1(board);
    }
    else
    {
        for(i=0;i<N;i++)
            for(j=0;j<N;j++)
                if (Cand_Count(mesh[i][j])==1)
                {
                    //podstavliajem tsifru na dosku
                    board[i][j]=Cand_to_Number(mesh[i][j]);
                    t++;
                }
        int number;
        //prosmatrivaem stroki
        for(i=0;i<N;i++)
            for(number=0;number<N;number++)
            {
                flag=0;
                for(j=0;j<N;j++)
                    if(mesh[i][j][number]==1) flag++;
                if(flag==1)//nashli tolko odno vozmozhnoje mesto
                    for(j=0;j<N;j++)
                        if(mesh[i][j][number]==1) {board[i][j]=number+1; t++;}
            }
        //prosmatrivaem stolbtsi
        for(j=0;j<N;j++)
            for(number=0;number<N;number++)
            {
                flag=0;
                for(i=0;i<N;i++)
                    if(mesh[i][j][number]==1) flag++;
                if(flag==1)
                    for(i=0;i<N;i++)
                        if (mesh[i][j][number]==1) {board[i][j]=number+1; t++;}
            }
        // prosmatrivaem sectora
        for(int a=0;a<N;a=a+3)
            for(int b=0;b<N;b=b+3) //eto perebiraem vse sectora
            {
                for(number=0;number<N;number++)
                {
                    flag=0;
                    for(i=(a/3)*3;i<(a/3)*3+3;i++)
                        for(j=(b/3)*3;j<(b/3)*3+3;j++)
                            if(mesh[i][j][number]==1) flag++;
                    if(flag==1)
                        for(i=(a/3)*3;i<(a/3)*3+3;i++)
                            for(j=(b/3)*3;j<(b/3)*3+3;j++)
                                if(mesh[i][j][number]==1) {board[i][j]=number+1; t++;}
                }
            }
        //schitaem skolko mest zapolneno v matritse
        flag=0;
        for(i=0;i<N;i++)
            for(j=0;j<N;j++)
                if (board[i][j]==0)
                    flag++;
        //cout<<endl<<"Not opened cells:"<<flag;
        //cout<<"\nt="<<t<<endl;
        if((flag>0)&&(flag<81)&&(old_opened!=flag))
        {
            old_opened=flag;
            //cout<<"\nGOTO Step2";
            Step2(board);
        }
        else
            if((flag>0)&&(flag<81)&&(old_opened==flag))
            {
                old_opened=flag;
                //cout<<"\nGOTO Step1";
                Step1(board);
            }
    }
}