#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

 int grid[9][9] =
 {
     {0,0,0,0,0,0,8,1,0},
     {0,4,0,8,0,6,0,0,0},
     {0,0,5,0,0,2,0,9,0},
     {8,7,0,4,0,1,9,0,0},
     {0,0,0,0,7,0,0,0,0},
     {0,0,4,5,0,9,0,8,3},
     {0,6,0,1,0,0,4,0,0},
     {0,0,0,6,0,5,0,2,0},
     {0,2,8,0,0,0,0,0,0}
 };


 int igrid[9][9] =
 {
     {0,0,0,0,0,0,8,1,0},
     {0,4,0,8,0,6,0,0,0},
     {0,0,5,0,0,2,0,9,0},
     {8,7,0,4,0,1,9,0,0},
     {0,0,0,0,7,0,0,0,0},
     {0,0,4,5,0,9,0,8,3},
     {0,6,0,1,0,0,4,0,0},
     {0,0,0,6,0,5,0,2,0},
     {0,2,8,0,0,0,0,0,0}
 };

 int cgrid[9][9] =
 {
     {1,1,1,1,1,1,1,1,1},
     {1,1,1,1,1,1,1,1,1},
     {1,1,1,1,1,1,1,1,1},
     {1,1,1,1,1,1,1,1,1},
     {1,1,1,1,1,1,1,1,1},
     {1,1,1,1,1,1,1,1,1},
     {1,1,1,1,1,1,1,1,1},
     {1,1,1,1,1,1,1,1,1},
     {1,1,1,1,1,1,1,1,1}
 };

////////////////////////////////////////////////////////////////////////////////
/// Display function
void display ()
{
    puts("+-----+-----+-----+");
    for (int i=0; i<9; i++)
    {
        printf("|");
        for (int j=0; j<9; j++)
        {
            printf( ((j+1)%3) ? "%d " : "%d|", grid[i][j]);
        }
        putchar('\n');
        if (!((i+1)%3))
            puts("+-----+-----+-----+");
    }
    puts("\n\n");
}

////////////////////////////////////////////////////////////////////////////////
/// Draw the initial grid
void draw ()
{
   TLine *l1 = new TLine;
   l1->SetLineWidth(3.);
   double m = 0.05;
   l1->DrawLine(m,m,m,1-m);
   l1->DrawLine(1-m,m,1-m,1-m);
   l1->DrawLine(0.3+m,m,0.3+m,1-m);
   l1->DrawLine(0.6+m,m,0.6+m,1-m);

   l1->DrawLine(m,m,1-m,m);
   l1->DrawLine(m,1-m,1-m,1-m);
   l1->DrawLine(m,0.3+m,1-m,0.3+m);
   l1->DrawLine(m,0.6+m,1-m,0.6+m);

   TLine *l2 = new TLine;
   l2->DrawLine(0.1+m,m,0.1+m,1-m);
   l2->DrawLine(0.2+m,m,0.2+m,1-m);
   l2->DrawLine(0.4+m,m,0.4+m,1-m);
   l2->DrawLine(0.5+m,m,0.5+m,1-m);
   l2->DrawLine(0.7+m,m,0.7+m,1-m);
   l2->DrawLine(0.8+m,m,0.8+m,1-m);

   l2->DrawLine(m,0.1+m,1-m,0.1+m);
   l2->DrawLine(m,0.2+m,1-m,0.2+m);
   l2->DrawLine(m,0.4+m,1-m,0.4+m);
   l2->DrawLine(m,0.5+m,1-m,0.5+m);
   l2->DrawLine(m,0.7+m,1-m,0.7+m);
   l2->DrawLine(m,0.8+m,1-m,0.8+m);

   double s = 0.1;
   double x = m+s/2;
   double y = 1.-s;

   for (int i=0; i<9; i++) {
      for (int j=0; j<9; j++) {
         TText *t = new TText();
         t->SetX(x);
         t->SetY(y);
         if (grid[i][j]>0) t->SetTitle(Form("%d",grid[i][j]));
         else               t->SetTitle(" ");
         t->SetName(Form("T%d%d",i,j));
         t->SetTextAlign(22);
         t->Draw();
         x = x + s ;
      }
         x = m+s/2;
         y = y -s;
   }
}

////////////////////////////////////////////////////////////////////////////////
void redraw ()
{
   TText *t;
   for (int i=0; i<9; i++) {
      for (int j=0; j<9; j++) {
         t = (TText*)gPad->GetListOfPrimitives()->FindObject(Form("T%d%d",i,j));
         if (grid[i][j] != igrid[i][j] && grid[i][j]>0) {
            cgrid[i][j] = cgrid[i][j]+1;
            t->SetTextColor(gStyle->GetColorPalette(cgrid[i][j]));
            t->SetTitle(Form("%d",grid[i][j]));
            igrid[i][j] = grid[i][j];
         }
         gPad->Update();
         gSystem->ProcessEvents();
      }
   }
}

////////////////////////////////////////////////////////////////////////////////
bool notOnLine (int k, int i)
{
    for (int j=0; j < 9; j++)
        if (grid[i][j] == k)
            return false;
    return true;
}


////////////////////////////////////////////////////////////////////////////////
bool notOnColumn (int k,int j)
{
    for (int i=0; i < 9; i++)
        if (grid[i][j] == k)
            return false;
    return true;
}


////////////////////////////////////////////////////////////////////////////////
bool notOnBlock (int k, int i, int j)
{
    int _i = i-(i%3), _j = j-(j%3);
    for (i=_i; i < _i+3; i++)
        for (j=_j; j < _j+3; j++)
            if (grid[i][j] == k)
                return false;
    return true;
}


////////////////////////////////////////////////////////////////////////////////
bool isValid (int position)
{
    if (position == 9*9) return true;

    int i = position/9, j = position%9;

    if (grid[i][j] != 0) return isValid(position+1);

    for (int k=1; k <= 9; k++) {
        if (notOnLine(k,i) && notOnColumn(k,j) && notOnBlock(k,i,j)) {
            grid[i][j] = k; redraw();
            if ( isValid (position+1) ) {return true;}
        }
    }
    grid[i][j] = 0;
    return false;
}


////////////////////////////////////////////////////////////////////////////////
void sudoku ()
{
   TCanvas *s = new TCanvas("s", "sudoku", 300,300);
   Int_t ci;      // for color index setting
   TColor *color; // for color definition with alpha
   ci = TColor::GetColor("#ccccff");
   s->SetFillColor(ci);
   gStyle->SetPalette(1);
   draw();
   isValid(0);
}