import java.util.*;

class sudoku{

int[] starti;
int[] endi;
int[] startj;
int[] endj;

int[] vecnrclues;
int[] nexts;
boolean[] marks;

int[][] clues;
int[][] solution;
int[][] data;
int[][] ceboxfrompos;

boolean[][][] posibs;

static int NOTSOLVED = 0;
static int MULTIPLE = 1;
static int SINGLE = 2;
static int NONE = 3;
static int FIRST = 4;
static int SECOND = 5;



int hadinc;
int[][] stack_nexts;
int[][][] stack_data;
boolean[][][][] stack_posibs;
static int MAXSTACK = 55;


int status;
int status_solved;
int maxadinc;

boolean mod_pos;
boolean found_recu;

///////////////////////////////////////////////////////////////

void put_clue_friendly(int posi, int posj,int val)
{
if(val<0||val>9)System.out.println("between 0 and 9");
clues[posi-1][posj-1]=val-1;
}

void put_clue(int posi, int posj,int val)
{
if(val<-1||val>8)System.out.println("between -1 and 8");
clues[posi][posj]=val;
}

boolean has_clue(int posi,int posj)
{
return clues[posi][posj]!=-1;
}

int val_clue(int posi,int posj)
{
return clues[posi][posj];
}

int get_clue_friendly(int posi,int posj)
{
return clues[posi-1][posj-1]+1;
}

int val_solution(int posi,int posj)
{
return solution[posi][posj];
}

int get_solution_friendly(int posi,int posj)
{
return solution[posi-1][posj-1]+1;
}

int get_status()
{
return status;
}

boolean get_recu()
{
return found_recu;
}


void clear_clues()
{
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
clues[i][j]=-1;
}

void clea_data()
{
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
data[i][j]=-1;
}

void clea_solution()
{
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
solution[i][j]=-1;
}


void initmembers()
{
allocmems();
initvars();
}
void initvars()
{
make_zoneboxes();
make_ceboxfrompos();
}

void allocmems()
{
alloc_matrices();
alloc_vects();
alloc_stacks();
}

void alloc_vects()
{

starti=new int[9];
endi=new int[9];
startj=new int[9];
endj=new int[9];

vecnrclues=new int[9];
nexts=new int[12];
marks=new boolean[81];
}

/*
int[] stack_status;         //int[MAXSTACK]
int[][] stack_nexts;        //int[MAXSTACK][12];
int[][][] stack_data;       //int[MAXSTACK][9][9];
boolean[][][][] stack_posibs;  //bol[MAXSTACK][9][9][9];
*/

void alloc_stacks()
{
int i,j,k;

stack_nexts=new int[MAXSTACK][];
stack_data=new int[MAXSTACK][][];
stack_posibs=new boolean[MAXSTACK][][][];


for(i=0;i<MAXSTACK;i++)
{
stack_nexts[i]=new int[12];
stack_data[i]=new int[9][];
stack_posibs[i]=new boolean[9][][];
for(j=0;j<9;j++)
{
stack_data[i][j]=new int[9];
stack_posibs[i][j]=new boolean[9][];
for(k=0;k<9;k++)
stack_posibs[i][j][k]=new boolean[9];
}
}
}


void alloc_matrices()
{
int i,j;

clues=new int[9][];
solution=new int[9][];
data=new int[9][];
ceboxfrompos=new int[9][];

posibs=new boolean[9][][];

for(i=0;i<9;i++)
{
clues[i]=new int[9];
solution[i]=new int[9];
data[i]=new int[9];
ceboxfrompos[i]=new int[9];

posibs[i]=new boolean[9][];
for(j=0;j<9;j++)
{
posibs[i][j]=new boolean[9];
}

}

}

void copy_data_from_clues()
{
int i,j;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
data[i][j]=clues[i][j];
}
}

void salv_sol()
{
int i,j;
if(hadinc>maxadinc)maxadinc=hadinc;

for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
solution[i][j]=data[i][j];
}
}

public void all_posible_list(boolean[] val)
{
int i;
for(i=0;i<9;i++)
val[i]=true;
}

void all_current_posible()
{
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
all_posible_list(posibs[i][j]);
}


void make_zoneboxes()
{
int nrzone;
for(nrzone=0;nrzone<9;nrzone++)
{
int pki,pkj;

pki=nrzone/3;
pkj=nrzone%3;

starti[nrzone]=3*pki;endi[nrzone]=starti[nrzone]+3;
startj[nrzone]=3*pkj;endj[nrzone]=startj[nrzone]+3;
}
}

int fceboxpos(int posi,int posj)
{
int zi,zj;
zi=posi/3;
zj=posj/3;
return zi*3+zj;
}

void make_ceboxfrompos()
{
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
ceboxfrompos[i][j]=fceboxpos(i,j);
}


public sudoku()
{
initmembers();
clear_clues();
clea_solution();
status=MULTIPLE;
}

///////////////////////////////////////////////////////////////

void clear_posib_row(int nrzone,int val)
{
int j;
for(j=0;j<9;j++)
posibs[nrzone][j][val]=false;
}

void clear_posib_col(int nrzone,int val)
{
int i;
for(i=0;i<9;i++)
posibs[i][nrzone][val]=false;
}


void clear_posib_box(int nrzone,int val)
{
int i,j;
int lstarti,lendi,lstartj,lendj;

lstarti=starti[nrzone];lendi=endi[nrzone];
lstartj=startj[nrzone];lendj=endj[nrzone];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
posibs[i][j][val]=false;
}


void clear_posib(int tipzone,int nrzone,int val)
{
switch(tipzone)
{
case 0:clear_posib_row(nrzone,val);return;
case 1:clear_posib_col(nrzone,val);return;
case 2:clear_posib_box(nrzone,val);return;
}
}

void clear_posib_around(int posi,int posj,int val)
{
clear_posib(0,posi,val);
clear_posib(1,posj,val);
clear_posib(2,ceboxfrompos[posi][posj],val);
}

void lookforclues()
{
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(is_clue(i,j))
clear_posib_around(i,j,data[i][j]);
}



void lookfornakedsingles()
{
int i,j,k;

for(i=0;i<9;i++)
for(j=0;j<9;j++)
for(k=0;k<9;k++)

if(!is_clue(i,j)&&is_naked_single(i,j,k))
make_clue(i,j,k);
}

boolean is_naked_single(int posi,int posj,int val)
{int i;
for(i=0;i<9;i++)
if(i==val)
{if(!posibs[posi][posj][i])return false;}
else
{if(posibs[posi][posj][i])return false;}
return true;
}

///////////////////////////////////////////////////////////////

void lookforhiddensingles()
{
int z,i,k;

for(z=0;z<3;z++)
for(i=0;i<9;i++)
for(k=0;k<9;k++)

if(is_hidden_single_in_zone(z,i,k))
make_clue_in_zone(z,i,k);
}



boolean is_hidden_single_in_zone(int tipzone,int nrzone,int val)
{
int count;
count=nr_locs_in_zone(tipzone,nrzone,val);
return count==1;
}

int nr_locs_in_zone(int tipzone,int nrzone,int val)
{
switch(tipzone)
{
case 0:return nr_locs_in_row(nrzone,val);
case 1:return nr_locs_in_col(nrzone,val);
case 2:return nr_locs_in_box(nrzone,val);
default:System.out.println("tipzone error");return -1;
}
}

int nr_locs_in_row(int nrzone,int val)
{
int cou=0;
int j;
for(j=0;j<9;j++)
if(!is_clue(nrzone,j))
if(posibs[nrzone][j][val])cou++;
return cou;
}

int nr_locs_in_col(int nrzone,int val)
{
int cou=0;
int i;
for(i=0;i<9;i++)
if(!is_clue(i,nrzone))
if(posibs[i][nrzone][val])cou++;
return cou;
}

int nr_locs_in_box(int nrzone,int val)
{
int cou=0;
int i,j;
int lstarti,lendi,lstartj,lendj;

lstarti=starti[nrzone];lendi=endi[nrzone];
lstartj=startj[nrzone];lendj=endj[nrzone];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
if(!is_clue(i,j))
if(posibs[i][j][val])cou++;
return cou;
}

void make_clue_in_zone(int tipzone,int nrzone,int val)
{
switch(tipzone)
{
case 0:make_clue_in_row(nrzone,val);break;
case 1:make_clue_in_col(nrzone,val);break;
case 2:make_clue_in_box(nrzone,val);break;
}
}

void make_clue_in_row(int nrzone,int val)
{
int j;
for(j=0;j<9;j++)
if(!is_clue(nrzone,j))
if(posibs[nrzone][j][val]){make_clue(nrzone,j,val);return;}
}

void make_clue_in_col(int nrzone,int val)
{
int i;
for(i=0;i<9;i++)
if(!is_clue(i,nrzone))
if(posibs[i][nrzone][val]){make_clue(i,nrzone,val);return;}
}

void make_clue_in_box(int nrzone,int val)
{
int i,j;
int lstarti,lendi,lstartj,lendj;

lstarti=starti[nrzone];lendi=endi[nrzone];
lstartj=startj[nrzone];lendj=endj[nrzone];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
if(!is_clue(i,j))
if(posibs[i][j][val]){make_clue(i,j,val);return;}
}


///////////////////////////////////////////////////////////////
boolean is_clue(int posi,int posj)
{
return data[posi][posj]!=-1;
}

void make_clue(int posi,int posj,int val)
{
data[posi][posj]=val;mod_pos=true;
clear_posib_around(posi,posj,val);
}

void just_make_clue(int posi,int posj,int val)
{
data[posi][posj]=val;
}

///////////////////////////////////////////////////////////////
boolean row_box(int posi,int box)
{
return starti[box]<=posi&&posi<endi[box];
}

boolean col_box(int posj,int box)
{
return startj[box]<=posj&&posj<endj[box];
}
///////////////////////////////////////////////////////////////

boolean isfrom_col_onlyin_box(int col,int box,int val)
{
boolean found=false;
int i;
if(!col_box(col,box))return false;
for(i=0;i<9;i++)
if(!is_clue(i,col))
if(posibs[i][col][val])
if(row_box(i,box))found=true;
else return false;
return found;
}

boolean isfrom_row_onlyin_box(int row,int box,int val)
{
boolean found=false;
int j;
if(!row_box(row,box))return false;
for(j=0;j<9;j++)
if(!is_clue(row,j))
if(posibs[row][j][val])
if(col_box(j,box))found=true;
else return false;
return found;
}

void clear_box_not_col(int box,int col,int val)
{
int i,j;
int lstarti,lendi,lstartj,lendj;

lstarti=starti[box];lendi=endi[box];
lstartj=startj[box];lendj=endj[box];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
if(j!=col)
if(!is_clue(i,j))
if(posibs[i][j][val]){posibs[i][j][val]=false;mod_pos=true;}
}

void clear_box_not_row(int box,int row,int val)
{
int i,j;
int lstarti,lendi,lstartj,lendj;

lstarti=starti[box];lendi=endi[box];
lstartj=startj[box];lendj=endj[box];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
if(i!=row)
if(!is_clue(i,j))
if(posibs[i][j][val]){posibs[i][j][val]=false;mod_pos=true;}
}

///////////////////////////////////////////////////////////////
boolean isfrom_box_onlyin_row(int box,int row,int val)
{
boolean found=false;
int i,j;
int lstarti,lendi,lstartj,lendj;

if(!row_box(row,box))return false;

lstarti=starti[box];lendi=endi[box];
lstartj=startj[box];lendj=endj[box];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)

if(!is_clue(i,j))
if(posibs[i][j][val])
if(i==row)found=true;
else return false;
return found;
}

boolean isfrom_box_onlyin_col(int box,int col,int val)
{
boolean found=false;
int i,j;
int lstarti,lendi,lstartj,lendj;

if(!col_box(col,box))return false;

lstarti=starti[box];lendi=endi[box];
lstartj=startj[box];lendj=endj[box];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)

if(!is_clue(i,j))
if(posibs[i][j][val])
if(j==col)found=true;
else return false;
return found;
}

void clear_row_not_box(int row,int box,int val)
{
int j;

for(j=0;j<9;j++)
if(!col_box(j,box))
if(!is_clue(row,j))
if(posibs[row][j][val]){posibs[row][j][val]=false;mod_pos=true;}
}

void clear_col_not_box(int col,int box,int val)
{
int i;

for(i=0;i<9;i++)
if(!row_box(i,box))
if(!is_clue(i,col))
if(posibs[i][col][val]){posibs[i][col][val]=false;mod_pos=true;}
}

///////////////////////////////////////////////////////////////
void lookforinteractions()
{
int box;
int lin;
int val;

for(box=0;box<9;box++)
for(lin=0;lin<9;lin++)
for(val=0;val<9;val++)
{
if(isfrom_box_onlyin_row(box,lin,val))clear_row_not_box(lin,box,val);
if(isfrom_box_onlyin_col(box,lin,val))clear_col_not_box(lin,box,val);
if(isfrom_col_onlyin_box(lin,box,val))clear_box_not_col(box,lin,val);
if(isfrom_row_onlyin_box(lin,box,val))clear_box_not_row(box,lin,val);
}
}

///////////////////////////////////////////////////////////////
void lookforhiddenpairs()
{
int z,i,k,l;

for(z=0;z<3;z++)
for(i=0;i<9;i++)
for(k=0;k<9;k++)
for(l=k+1;l<9;l++)

if(is_hidden_pair_in_zone(z,i,k,l))
clear_hidden_pair_in_zone(z,i,k,l);
}

boolean is_hidden_pair_in_zone(int tipzone,int nrzone,int valk,int vall)
{
int count;
count=nr_boths_in_zone(tipzone,nrzone,valk,vall);
return count==2;
}

int nr_boths_in_zone(int tipzone,int nrzone,int valk,int vall)
{
switch(tipzone)
{
case 0:return nr_boths_in_row(nrzone,valk,vall);
case 1:return nr_boths_in_col(nrzone,valk,vall);
case 2:return nr_boths_in_box(nrzone,valk,vall);
default:System.out.println("tipzone error");return -1;
}
}

int nr_boths_in_row(int nrzone,int valk,int vall)
{
int cou=0;
int j;
for(j=0;j<9;j++)
if(!is_clue(nrzone,j))
if(posibs[nrzone][j][valk])
{
if(posibs[nrzone][j][vall])cou++;
else
return -1; //only 1st
}
else
if(posibs[nrzone][j][vall])return -1; //only 2nd
return cou;
}

int nr_boths_in_col(int nrzone,int valk,int vall)
{
int cou=0;
int i;
for(i=0;i<9;i++)
if(!is_clue(i,nrzone))
if(posibs[i][nrzone][valk])
{
if(posibs[i][nrzone][vall])cou++;
else
return -1; //only 1st
}
else
if(posibs[i][nrzone][vall])return -1; //only 2nd
return cou;
}

int nr_boths_in_box(int nrzone,int valk,int vall)
{
int cou=0;
int i,j;
int lstarti,lendi,lstartj,lendj;

lstarti=starti[nrzone];lendi=endi[nrzone];
lstartj=startj[nrzone];lendj=endj[nrzone];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
if(!is_clue(i,j))
if(posibs[i][j][valk])
{
if(posibs[i][j][vall])cou++;
else
return -1; //only 1st
}
else
if(posibs[i][j][vall])return -1; //only 2nd
return cou;
}


void clear_hidden_pair_in_zone(int tipzone,int nrzone,int valk,int vall)
{
switch(tipzone)
{
case 0:clear_hidden_pair_in_row(nrzone,valk,vall);return;
case 1:clear_hidden_pair_in_col(nrzone,valk,vall);return;
case 2:clear_hidden_pair_in_box(nrzone,valk,vall);return;
default:System.out.println("tipzone error");
}
}

void clear_hidden_pair_in_row(int nrzone,int valk,int vall)
{
int j;
for(j=0;j<9;j++)
if(!is_clue(nrzone,j))

if(posibs[nrzone][j][valk]&&posibs[nrzone][j][vall])
clear_all_but2(nrzone,j,valk,vall);
}

void clear_hidden_pair_in_col(int nrzone,int valk,int vall)
{
int i;
for(i=0;i<9;i++)
if(!is_clue(i,nrzone))

if(posibs[i][nrzone][valk]&&posibs[i][nrzone][vall])
clear_all_but2(i,nrzone,valk,vall);
}

void clear_hidden_pair_in_box(int nrzone,int valk,int vall)
{
int i,j;
int lstarti,lendi,lstartj,lendj;
lstarti=starti[nrzone];lendi=endi[nrzone];
lstartj=startj[nrzone];lendj=endj[nrzone];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
if(!is_clue(i,j))

if(posibs[i][j][valk]&&posibs[i][j][vall])
clear_all_but2(i,j,valk,vall);
}

void clear_all_but2(int posi,int posj,int valk,int vall)
{
int i;
for(i=0;i<9;i++)
if(i!=valk&&i!=vall)
if(posibs[posi][posj][i])
{posibs[posi][posj][i]=false;mod_pos=true;}}


///////////////////////////////////////////////////////////////

boolean is_clear_all_but2(int posi,int posj,int valk,int vall)
{
int i;
for(i=0;i<9;i++)
if(i==valk||i==vall)
{
if(!posibs[posi][posj][i])
return false;
}
else
if(posibs[posi][posj][i])
return false;
return true;
}

int nr_doubles_in_zone(int tipzone,int nrzone,int valk,int vall)
{
switch(tipzone)
{
case 0:return nr_doubles_in_row(nrzone,valk,vall);
case 1:return nr_doubles_in_col(nrzone,valk,vall);
case 2:return nr_doubles_in_box(nrzone,valk,vall);
default:System.out.println("tipzone error");return -1;
}
}

int nr_doubles_in_row(int nrzone,int valk,int vall)
{
int cou=0;

int j;
for(j=0;j<9;j++)
if(!is_clue(nrzone,j))

if(is_clear_all_but2(nrzone,j,valk,vall))
cou++;
return cou;
}

int nr_doubles_in_col(int nrzone,int valk,int vall)
{
int cou=0;

int i;
for(i=0;i<9;i++)
if(!is_clue(i,nrzone))

if(is_clear_all_but2(i,nrzone,valk,vall))
cou++;
return cou;
}

int nr_doubles_in_box(int nrzone,int valk,int vall)
{
int cou=0;
int i,j;
int lstarti,lendi,lstartj,lendj;

lstarti=starti[nrzone];lendi=endi[nrzone];
lstartj=startj[nrzone];lendj=endj[nrzone];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
if(!is_clue(i,j))
if(is_clear_all_but2(i,j,valk,vall))
cou++;
return cou;
}

boolean is_naked_pair_in_zone(int tipzone,int nrzone,int valk,int vall)
{
int count;
count=nr_doubles_in_zone(tipzone,nrzone,valk,vall);
return count==2;
}

void lookfornakedpairs()
{
int z,i,k,l;

for(z=0;z<3;z++)
for(i=0;i<9;i++)
for(k=0;k<9;k++)
for(l=k+1;l<9;l++)

if(is_naked_pair_in_zone(z,i,k,l))
clear_naked_pair_in_zone(z,i,k,l);
}

void clear_naked_pair_in_zone(int tipzone,int nrzone,int valk,int vall)
{
switch(tipzone)
{
case 0:clear_naked_pair_in_row(nrzone,valk,vall);return;
case 1:clear_naked_pair_in_col(nrzone,valk,vall);return;
case 2:clear_naked_pair_in_box(nrzone,valk,vall);return;
default:System.out.println("tipzone error");
}
}


void clear_naked_pair_in_row(int nrzone,int valk,int vall)
{
int j;
for(j=0;j<9;j++)
if(!is_clue(nrzone,j))
if(!is_clear_all_but2(nrzone,j,valk,vall))
clear_2(nrzone,j,valk,vall);
}

void clear_naked_pair_in_col(int nrzone,int valk,int vall)
{
int i;
for(i=0;i<9;i++)
if(!is_clue(i,nrzone))
if(!is_clear_all_but2(i,nrzone,valk,vall))
clear_2(i,nrzone,valk,vall);
}

void clear_naked_pair_in_box(int nrzone,int valk,int vall)
{
int i,j;
int lstarti,lendi,lstartj,lendj;
lstarti=starti[nrzone];lendi=endi[nrzone];
lstartj=startj[nrzone];lendj=endj[nrzone];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
if(!is_clue(i,j))
if(!is_clear_all_but2(i,j,valk,vall))
clear_2(i,j,valk,vall);
}

void clear_2(int posi,int posj,int valk,int vall)
{
int i;
for(i=0;i<9;i++)
if(i==valk||i==vall)
if(posibs[posi][posj][i])
{posibs[posi][posj][i]=false;mod_pos=true;}
}


///////////////////////////////////////////////////////////////
void solv_nerecursiv()
{

if(invalid_clues()){status=NONE;return;}

lookforclues();
if(no_candida()){status=NONE;return;}

mod_pos=true;
while(mod_pos){
mod_pos=false;
lookforhiddensingles();
lookfornakedsingles();
lookforhiddenpairs();
lookfornakedpairs();
lookforinteractions();
}

if(no_candida()){status=NONE;return;}
status=NOTSOLVED;
}

///////////////////////////////////////////////////////////////

int nrcl(int posi,int posj)
{
int i;
int cou=0;
for(i=0;i<9;i++)
if(posibs[posi][posj][i])cou++;
return cou;
}


///////////////////////////////////////////////////////////////

boolean invalid_clues()
{
int z,i;

for(z=0;z<3;z++)
for(i=0;i<9;i++)
if(is_double_clues_in_zone(z,i))return true;
return false;
}

boolean is_double_clues_in_zone(int tipzone,int nrzone)
{
make_vecnrclues_zero();
switch(tipzone)
{
case 0:numara_clues_in_row(nrzone);break;
case 1:numara_clues_in_col(nrzone);break;
case 2:numara_clues_in_box(nrzone);break;
default:System.out.println("tipzone error");
}
return is_some2();
}

void numara_clues_in_row(int nrzone)
{
int j;
for(j=0;j<9;j++)
if(is_clue(nrzone,j))
vecnrclues[data[nrzone][j]]++;
}

void numara_clues_in_col(int nrzone)
{
int i;
for(i=0;i<9;i++)
if(is_clue(i,nrzone))
vecnrclues[data[i][nrzone]]++;
}

void numara_clues_in_box(int nrzone)
{
int i,j;
int lstarti,lendi,lstartj,lendj;

lstarti=starti[nrzone];lendi=endi[nrzone];
lstartj=startj[nrzone];lendj=endj[nrzone];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
if(is_clue(i,j))
vecnrclues[data[i][j]]++;
}

void make_vecnrclues_zero()
{
int i;
for(i=0;i<9;i++)
vecnrclues[i]=0;
}

boolean is_some2()
{
int i;
for(i=0;i<9;i++)
if(vecnrclues[i]>1)return true;
return false;
}

///////////////////////////////////////////////////////////////
boolean cell_no_posibs(int i,int j)
{
int k;
if(is_clue(i,j))return false;

for(k=0;k<9;k++)
if(posibs[i][j][k])return false;
return true;
}

boolean no_candida()
{
int z,i,j,k;

for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(cell_no_posibs(i,j))return true;

for(z=0;z<3;z++)
for(i=0;i<9;i++)
for(k=0;k<9;k++)
if(no_candida_in_zone(z,i,k))return true;
return false;
}

boolean no_candida_in_zone(int tipzone,int nrzone,int val)
{
switch(tipzone)
{
case 0:return no_candida_in_row(nrzone,val);
case 1:return no_candida_in_col(nrzone,val);
case 2:return no_candida_in_box(nrzone,val);
default:System.out.println("tipzone error");return true;
}
}

boolean no_candida_in_row(int nrzone,int val)
{
int j;
for(j=0;j<9;j++)
if(is_clue(nrzone,j))
if(data[nrzone][j]==val)return false;
else;
else
if(posibs[nrzone][j][val])return false;
return true;
}

boolean no_candida_in_col(int nrzone,int val)
{
int i;
for(i=0;i<9;i++)
if(is_clue(i,nrzone))
if(data[i][nrzone]==val)return false;
else;
else
if(posibs[i][nrzone][val])return false;
return true;
}

boolean no_candida_in_box(int nrzone,int val)
{
int i,j;
int lstarti,lendi,lstartj,lendj;

lstarti=starti[nrzone];lendi=endi[nrzone];
lstartj=startj[nrzone];lendj=endj[nrzone];

for(i=lstarti;i<lendi;i++)
for(j=lstartj;j<lendj;j++)
if(is_clue(i,j))
if(data[i][j]==val)return false;
else;
else
if(posibs[i][j][val])return false;
return true;
}

///////////////////////////////////////////////////////////////
boolean all_clues()
{
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(!is_clue(i,j))return false;
return true;
}

///////////////////////////////////////////////////////////////
void solv()
{
clea_data();
copy_data_from_clues();
all_current_posible();
reset_stack();
status=NOTSOLVED;
status_solved=NOTSOLVED;
found_recu=false;
maxadinc=-1;

solv_recursiv();
if(status_solved==FIRST)status=SINGLE;
if(status_solved==SECOND)status=MULTIPLE;
if(status_solved==NOTSOLVED)status=NONE;
}

void final_pre()
{
salv_sol();
if(status_solved==FIRST)status_solved=SECOND;
else status_solved=FIRST;
//print_stack_data();
}

void calc_next_move()
{
int i,j,k;

int poie;
int curmax;

nexts[0]=-1;nexts[1]=-1;nexts[2]=11;

for(i=0;i<9;i++)
for(j=0;j<9;j++)

if(!is_clue(i,j))
{
curmax=nrcl(i,j);
if(curmax<nexts[2])
{
nexts[0]=i;nexts[1]=j;nexts[2]=curmax;
poie=3;
for(k=0;k<9;k++)
if(posibs[i][j][k]){nexts[poie]=k;poie++;}}}}


void solv_recursiv()
{
int k;
solv_nerecursiv();
if(status==NONE)return;
if(all_clues()){final_pre();return;}
found_recu=true;

calc_next_move();

for(k=0;k<nexts[2];k++)
{
push_variables();
just_make_clue(nexts[0],nexts[1],nexts[3+k]);
solv_recursiv();
pop_variables();
if(status_solved==SECOND)return;
}
}

///////////////////////////////////////////////////////////////
void reset_stack()
{
hadinc=0;
}

void push_variables()
{
//push_status();
push_nexts();
push_data();
push_posibs();
hadinc++;
if(hadinc==MAXSTACK)System.out.println("stack overflow");
}

void pop_variables()
{
hadinc--;
if(hadinc<0)System.out.println("stack error");
//pop_status();
pop_nexts();
pop_data();
pop_posibs();
}


void push_nexts()
{
int i;
for(i=0;i<12;i++)
stack_nexts[hadinc][i]=nexts[i];
}

void pop_nexts()
{
int i;
for(i=0;i<12;i++)
nexts[i]=stack_nexts[hadinc][i];
}

void push_data()
{
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
stack_data[hadinc][i][j]=data[i][j];
}
void pop_data()
{
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
data[i][j]=stack_data[hadinc][i][j];
}

void push_posibs()
{
int i,j,k;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
for(k=0;k<9;k++)
stack_posibs[hadinc][i][j][k]=posibs[i][j][k];
}
void pop_posibs()
{
int i,j,k;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
for(k=0;k<9;k++)
posibs[i][j][k]=stack_posibs[hadinc][i][j][k];
}

///////////////////////////////////////////////////////////////


void put_random_clues()
{
int aleai,aleaj,valc;
double rand;

clear_clues();

while(true)
{

do{
rand=Math.random();
aleai=(int)(rand*9);
rand=Math.random();
aleaj=(int)(rand*9);
}
while(has_clue(aleai,aleaj));

rand=Math.random();
valc=(int)(rand*9);
put_clue(aleai,aleaj,valc);

solv();

switch(status){
case 2:return;
case 1:break;
case 3:put_clue(aleai,aleaj,-1);break;
default:System.out.println("strange in clues_aleator");
}
}
//System.out.println("[{0},{1}]",aleai,aleaj);

}

void make_all_marks()
{
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
marks[i*9+j]=has_clue(i,j);
}

int chose_nth(int val)
{
int k;
int cou=val;
while(true)
for(k=0;k<81;k++)

if(marks[k]){if(cou==0)return k;cou--;}
}

int nrmarks()
{
int k;
int cou=0;
for(k=0;k<81;k++)
if(marks[k])cou++;
return cou;
}

void rem_random_clues()
{
int aleai,aleaj,ales;
int poz;
int valc;
int nrmrk;
solv();
if(status!=SINGLE)return;

make_all_marks();

double rand;

while(true)
{
nrmrk=nrmarks();
if(nrmrk==0)return;
rand=Math.random();
ales=(int)(rand*nrmrk);
poz=chose_nth(ales);
aleai=poz/9;
aleaj=poz%9;

valc=val_clue(aleai,aleaj);
put_clue(aleai,aleaj,-1);
solv();

switch(status){
case 2:marks[poz]=false;break;
case 1:put_clue(aleai,aleaj,valc);marks[poz]=false;break;
case 3:System.out.println("strange in clues_aleator");
default:System.out.println("strange in clues_aleator");
}
}
}

void make_random_sudoku()
{
put_random_clues();
rem_random_clues();
}


void make_hard_sudoku()
{
do{
make_random_sudoku();
solv();
}while(!found_recu);
}

void make_easy_sudoku()
{
do{
make_random_sudoku();
solv();
}while(found_recu);
}

int nrclues()
{
int i,j;
int cou=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(has_clue(i,j))cou++;
return cou;
}


void chose_nth_nonclue(int ord)
{
int i,j;
int cou=ord;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(!has_clue(i,j))
{
if(cou==0){nexts[0]=i;nexts[1]=j;return;}
cou--;
}
}

void show_another_clue()
{
int aleai,aleaj;
int poz;
int nrrest;
double rand;


solv();
if(status!=SINGLE)return;

nrrest=81-nrclues();
if(nrrest==0)return;

rand=Math.random();
poz=(int)(rand*nrrest);

chose_nth_nonclue(poz);
aleai=nexts[0];
aleaj=nexts[1];
clues[aleai][aleaj]=solution[aleai][aleaj];


}

///////////////////////////////////////////////////////////////

}