Skip to content

Making of an Efficient Sudoku Cracker (Sudoku Solver)

September 4, 2012

Abstract        In this post I shall try to propose an approach of solving Sudoku puzzles. In order to find the solution to a given Sudoku puzzle we have many a few algorithms available following the Heuristics or Genetic Algorithmic approaches. Some works have also been done using Retrievable GA in attempt to achieve better efficiency with respect to the amount of time required. But here I shall try to focus on the implementation of a few of the strategies that belong to a very large family of the same. Although the execution of even all of the strategies does not guarantee the solution but still a very wide range of puzzles involving all or most the levels can be solved using this approach and that too in a time effective manner.

Introduction         The Sudoku puzzles are originated from Japan. It was first introduced there by Nikoli in the paper “Monthly Nikolist” in 1984. The Japanese characters “Su” and “Doku” means “number” and “single” respectively which collectively contribute to the logic behind a Sudoku puzzle. A Sudoku puzzle can be considered as an N×N matrix (N has to be a perfect square number), that is again subdivided into N number of √N×√N of matrix segments. Now there are 3 necessary and sufficient constraints that are imposed on a Sudoku: 1. There must be digits 1 through N without repetition in each of the N rows. 2. There must be digits 1 through N without repetition in each of the N columns. 3. There must be digits 1 through N without repetition in each of the N number of √N×√N squares.

  Figure 1: A given Sudoku Puzzle Having 32% filled

Figure 2: Solution to the Sudoku given in figure 1

In the above two figures two such puzzle are shown, one is the given puzzle itself and the other being its solution. Its has been observed by many of the research persons that in order to solve such a puzzle using Brute-Force technique by a typical PC may take 35-40 minutes irrespective of the level of the puzzle. It might be said “good” provided that the puzzle is extremely hard and an average human being can’t solve it that much quicker, otherwise in most of the cases the human being will be able to solve the puzzle quite before than the computer does. So there is no means of using a computer and yet not minimizing the time. But the kinds of approaches we will discuss below are good enough to achieve the solution within fraction of a second if implemented properly in the computer specified. So in the next section we discuss about such strategies.

Proposed Strategies          In order to solve a random Sudoku puzzle a set of strategies are needed to be performed on it in a specified sequence. The sequence is predefined as it will be stated very soon. One must not change this sequence as it is chosen in such a way that the leading strategies performed are for weaker puzzles and as we progress the trailing strategies are for more hard puzzles. It doesn’t mean that choosing the strategies for hard puzzles will be sufficient to obtain the solution, rather until and unless the leading strategies don’t reveal the doors and provide the basis for the trailing ones the trailing ones can’t really hit the deck. So changing the predefined sequence won’t help us to achieve the goal. The proposed strategies and the sequence of their application is given in the figure below:

Figure 3: Strategies and their order

Strategies within the green blocks are the most basic strategies, those within yellow blocks are the medium strategies and last two that are within red blocks are the advanced ones. The first two strategies are known to be Placing Strategies and the rest of the strategies as Eliminating Strategies as we shall discuss very soon why they are called so.

If a strategy runs successfully then we will have to rollback to the first strategy and thereafter perform the following strategies sequentially. Each of the strategies mentioned above is discussed separately below and while discussing onwards we make the following assumptions: 1. We consider N to be 9 which is the most popular form of a Sudoku puzzle. 2. For each of the blank cells there will be a candidate list that will store the numbers that are the contenders for that cell. The numbers those are already in  the in the row to which the cell belongs don’t get the entry in the candidate list  and the same thing is done to the numbers at the column and the square which contain the cell.  

1.Open Possibilities   This strategy is concerned about “A particular number can be placed in a particular cell if the other 8 numbers can’t be placed in that very cell”. Technically if the cardinality of the candidate set is 1 then that the only value in the candidate set must be the actual value for that particular cell.

Figure 4: Open Possibilities

Consider the puzzle in figure 4. If we try to construct the candidate list for the cell annotated with a red question mark (‘?’) we will come to see that for being in the same row 3 and 5 are the non-candidates. Similarly 2,5,6,8 and 9 are the same for being in the same column. And finally for belonging to the same square 1 is also a non-candidate. So if we go on to exclude these values we have only 7 left to place in the candidate list. Hence the candidate set is a singleton one which in turn is a sufficient condition to place 7 in that very cell. Quite clearly if an open possibility is detected it can guarantee the place of a particular number in a given cell and hence one of the two Placing Strategies.

2. Hidden Singles  This strategy is concerned about “A particular number can be placed in a particular cell if it can’t be placed in the 8 other cells of the either of three units that it belongs to (A unit can be a either a row or a column or a square)”.Technically if a particular unit having 8 such cells neither of those having the key value (value that we are looking to place somewhere in the unit) in their candidate lists and only one cell has that value in its candidate list irrespective of the remaining candidates, then that particular cell is the one where we can surely place the key.

Figure 5: Hidden Singles

Consider the puzzle in figure 5. If we try to place 3 in the cell annotated with a red question mark (‘?’), i.e. we take the key value as 3, then we can easily observe that the square in which this cell belongs does not permit us to place a 3 in 5 of its cells that are already filled. In addition to this two empty cells don’t permit us to place 3 within them since it will violate the row constraints. So there is only one place left where we can place the 3, and we must do it since a 3 has to be there in each and every unit. So it might have been the case that the likes of 2 and 9 were also the candidates for that cell apart from 3, still it is 3 that is going to be placed there. Again similar to the previously discussed strategy this one is also capable of placing a number to its proper cell, thus it is yet another example of Placing Strategies.

3. Naked Candidates          Naked candidates are the ones which are found in good numbers in any leveled Sudoku puzzle. It is a very effective strategy to open up the board. This strategy can’t place a particular number on a given cell; rather it tries to eliminate the numbers from the candidate list of a given cell which in turn may provide the basis for the previous strategies to get executed. That is why it is one of the many Eliminating Strategies that we have. The naked candidates are found in a following manner: “In a particular unit if there are x number of such cells among which atleast one having x number of entries in its candidate list, this set works as the dominant set, and the rest of the cells have their candidate list sets as the subset of the above dominant set”. If such a condition is encountered then we say that naked candidates have been detected. If x=2 then the numbers of the dominant set is called the naked pair, and similarly naked triple, naked quad for x = 3, 4 and so on. Now in order to perform elimination we remove the naked candidates from the candidate lists of all the cells (except the x number of cells that were involved in the detection process) that belong to the same unit for which the naked candidates have been detected. 

Figure 6: Naked Pairs

Let us consider the above problem instance of Figure 6. Here the highlighted row in light yellow is taken to be the unit under consideration. We can see that there are 2 cells which have {6, 7} as their candidate set. So from this it is assured that the places for 6 and 7 are bound to these two cells, i.e. if one of the cell will go on to contain 6 the other will have 7 in it and the vice versa. So if these two are placed in their places no other cell in the unit can have either 6 or 7 as their candidates. So we can safely eliminate them from the candidate sets of the remaining cells (belonging to the unit under consideration) wherever else they have occurred, and we will do exactly that to the numbers those are shown in the red color. Now if you can observe a little bit more you can see that from cell having the candidates {1, 7, 8} we can further eliminate 1 as well which will let the Open Possibilities module to fire again. In the following two figures Figure 7 and Figure 8 I have shown the examples of Naked Triples and Naked Quads, i.e. the value of x becomes 3 and 4 respectively. In the figures we have used the same color legends as the previous, i.e. sets having the numbers in green are involved in forming the naked triples/quads, and the red colored numbers within some other sets are the ones to be eliminated.

Figure 7: Naked Triples

Consider the examples in Figure 7 that shows the naked triples. The yellow row segment is the unit under consideration. The naked triple is formed by the 3 sets having elements colored as green. Here {5, 8, 9} is the dominant set and the other two sets {5, 8} and {5, 9} being its subsets. So using the similar logic that we used while stating the naked pairs, the positions of 5, 8 and 9 are now bound to these 3 cells involving the naked triple and hence 5, 8 and 9 are eliminated from the candidate lists wherever else they have occurred in the unit.

Figure 8: Naked Quads

Naked quads on the other hand are very rarely met, but can be very useful if spotted. Likewise we have traced such a thing in the Figure 8’s problem instance. The unit under consideration being the yellow square, and the dominant set being {1, 5, 6, 8} we can see 3 of its subsets namely {1, 5}, {1, 6} and {1, 5, 6, 8} go on to form a naked quad. Hence the sets within this yellow square having these numbers apart from these 4 sets is not going to contain these values any further, as we have shown the numbers in red going to be eliminated.

4. Pointing Pairs              This is also a good candidate eliminator and in hard puzzles very often we see that this technique coming handy for us. The principle behind pointing pairs is: “If a particular number is needed to be placed in a square and the number within that square can only be placed into the cells that are either aligned in a row, or a column; then we can remove the occurrences of that number from the candidate lists of the cells outside the square but within that particular row or column”.

Figure 9: Pointing Pairs

Consider the above segment shown in Figure 9. Let us take the value to be placed as 2. We can see that there are only 2 positions within the middle square (highlighted with green) where we can place 2s. And these two positions are in the same row. Since there is no other position where we can place a 2 within the square, so we can say that the pointing pairs have been detected. So the occurrences of 2s outside the square within that particular row can be safely removed as we have highlighted them with red.

5. Box-Line Reduction          This strategy deals with the careful comparison of rows and columns against the squares. It is all about: “If a number needs to be placed in a row or a column, and the occurrences of that number as candidates within that particular row or column are all within a certain square, then all the candidates within that square that are not within the row or column can be removed”.

Figure 10: Box Line Reduction

Consider the example shown above in Figure 10. It suggests one thing which is very clear. The row that has been highlighted with yellow must need a 9 in it. Also it can be observed that the cells within that row having 9 as their candidates are all within the same square. So since the one of the green 9s must get the place over there, so there can’t be another 9 within the same square outside this row, that are the red 9s. And that’s the reason why we can now safely remove the red 9s in order to shortlist the candidates of the cells.

6. X-wing          This is one of the most advanced candidate eliminator strategies that we have. In order to declare that an X-wing has been found there are two necessary conditions that must occur together. These are: 1. There are only two possible cells for a value in each of different rows. 2. These candidates also lie in the same columns. If so then all other candidates for this value in both of the columns can be eliminated.

Figure 11: X-Wing

Look at the example shown in figure 11. Here the topmost and the bottommost rows are the two such rows each having exactly two possible cells which are the candidates to contain a 6. In addition to this the positions of 6s are also aligned in the same column. So the columns highlighted with yellow must contain a 6 each somewhere within them. Now it is certain that one of the two 6s in green of each column must occur. So the other 6s in the same column (i.e. the 6s highlighted with red) can’t occur at the same time, and this true for both of the two columns. Hence we can safely remove the red 6s. X-wing can also be looked upon as the jobs of rows and columns reversed. One can rotate this puzzle as if finding the transpose of a matrix we then meet this kind of scenario.

7. Y-wing         This is one of the very best candidate eliminating strategies. Now to describe what exactly a Y-Wing is, I would like to refer you to figures 12 and 13.  

Figure 12: Y- Wing (A)

Figure 13: Y-Wing (B)

Have a close look at Figure 12. Here A, B and C are the candidates of different cells. If we encounter such a situation as shown in Figure 12, we can then say as below: Let us the cell having the candidates A and B. If this cell goes on to contain the value A, then the cell having the candidates A and C must contain C which implies the cell where we have put a red colored C can’t contain the value C. Now if the cell having the candidates A and B contain a B, then the cell having its candidates B and C must contain a C, and that in turn implies that the cell where we have put a red colored C can’t contain a C for being in the same row. So from the above discussion it is quite clear that whatever happens, in such situations C can’t be placed in the cell where we have put a red colored C. Now look at Figure 13. For similar reasons of maintaining the constraints of the puzzle you can easily verify that irrespective of what is placed in the cell having the candidates A and B, the cells where we have put red colored Cs can’t ever contain a C. So from all such positions the candidate C can be safely removed.

C implementation*  [*The readers who are not interested in the implementation can omit this section without any loss of continuity.]              Before saying about the implementation in C, first I would like to introduce to you a couple of arrays that will be used very frequently throughout the program. The puzzle is stored in a 2D manner row-wise into the two dimensional array sdk, and the candidates for all the cells in the puzzle are stored in a 3D array named candidate. Now the list within each cell has the form as follows: The number of candidates for that cell will be stored in the first location of the list followed by candidates in a sorted order. Hereon we will show the implementations of individual strategies have been made: 1. Open Possibilities 

void check_singles(int sdk[9][9],int candidate[9][9][10])
{
  int i,j,flag;
  do
  {
   flag=0;
   for(i=0;i<9;i++)
    for(j=0;j<9;j++)
     if(!sdk[i][j]&&candidate[i][j][0]==1)
     {
      sdk[i][j]=candidate[i][j][1];
      candidate[i][j][0]=0;
      update_candidates(candidate,i,j,candidate[i][j][1]);
      flag=1;
     }
  }while(flag);
}
void update_candidates(int candidate[9][9][10],int i,int j,int x)
{
  int k,l;
  for(k=0;k<9;k++)
  {
   _delete(candidate[k][j],x);
   _delete(candidate[i][k],x);
  }
  for(k=(i/3)*3;k<(i/3)*3+3;k++)
   for(l=(j/3)*3;l<(j/3)*3+3;l++)
    _delete(candidate[k][l],x);
}
int _delete(int A[],int key)
{
  int i,j,flag=0;
  for(i=1;A[i]!=key&&i<=A[0];i++);
  if(i==A[0]&&A[i]==key)
  {
    A[0]--;
    return 1;
  }
  for(j=i+1;j<=A[0];j++,flag=1)
   A[j-1]=A[j];
  A[0]-=flag;
  return flag;
}

2. Hidden Singles

int check_hidden_singles(int sdk[9][9],int candidate[9][9][10])
{
  int i,j,k,l,x,nc,flag,work=0;
  do
  {
   flag=0;
   for(x=1;x<=9;x++)
   {
    for(i=0;i<9;i++)
     for(j=0;j<9;j++)
     {
      if(sdk[i][j])
       continue;
      nc=0;
      if(!is_at_row(sdk,i,x)&&!is_at_column(sdk,j,x)&&!is_at_square(sdk,i,j,x))
      {
       for(k=(i/3)*3;k<(i/3)*3+3;k++)
	for(l=(j/3)*3;l<(j/3)*3+3;l++)
	 if(sdk[k][l]||is_at_row(sdk,k,x)||is_at_column(sdk,l,x)||is_at_square(sdk,k,l,x))
	   nc++;
      }
      if(nc==8)
      {
       sdk[i][j]==x;
       candidate[i][j][0]=0;
       update_candidates(candidate,i,j,x);
       flag=1;
       work=1;
      }
      nc=0;
      if(!is_at_row(sdk,i,x)&&!is_at_column(sdk,j,x)&&!is_at_square(sdk,i,j,x))
      {
       for(k=0;k<9;k++)
	 if(sdk[i][k]||is_at_row(sdk,i,x)||is_at_column(sdk,k,x)||is_at_square(sdk,i,k,x))
	   nc++;
      }
      if(nc==8)
      {
       sdk[i][j]=x;
       candidate[i][j][0]=0;
       update_candidates(candidate,i,j,x);
       flag=1;
       work=1;
      }
      nc=0;
      if(!is_at_row(sdk,i,x)&&!is_at_column(sdk,j,x)&&!is_at_square(sdk,i,j,x))
      {
       for(k=0;k<9;k++)
	 if(sdk[k][j]||is_at_row(sdk,k,x)||is_at_column(sdk,j,x)||is_at_square(sdk,k,j,x))
	   nc++;
      }
      if(nc==8)
      {
       sdk[i][j]=x;
       candidate[i][j][0]=0;
       update_candidates(candidate,i,j,x);
       flag=1;
       work=1;
      }
     }
   }
  }while(flag);
  if(work)
   return 1;
  else
   return 0;
}
int is_at_row(int sdk[9][9],int i,int x)
{
  int k;
  for(k=0;k<9;k++)
   if(sdk[i][k]==x)
    return 1;
  return 0;
}
int is_at_column(int sdk[9][9],int j,int x)
{
  int k;
  for(k=0;k<9;k++)
   if(sdk[k][j]==x)
    return 1;
  return 0;
}
int is_at_square(int sdk[9][9],int i,int j,int x)
{
  int k,l;
  for(k=(i/3)*3;k<(i/3)*3+3;k++)
   for(l=(j/3)*3;l<(j/3)*3+3;l++)
    if(sdk[k][l]==x)
     return 1;
  return 0;
}

3. Naked Candidates

int check_naked_candidates(int sdk[9][9],int candidate[9][9][10])
{
  int i,j,k,l,work=0,match_in_unit,nc,arr[10],arr1[10];
  for(i=0;i<9;i++)
   {
    for(j=0;j<9;j++)
    {
     match_in_unit=nc=0;
     if(sdk[i][j])
      continue;
     for(k=0;k<9;k++)
     {
      if(is_subset(candidate[i][j],candidate[i][k]))
       match_in_unit++;
      else
       arr[nc++]=k;
     }
     if(match_in_unit==candidate[i][j][0])
     {
      for(k=1;k<=candidate[i][j][0];k++)
       for(l=0;l<nc;l++)
       {
	if(_delete(candidate[i][arr[l]],candidate[i][j][k]))
	 work=1;
       }
     }
     if(work)
      return 1;
     match_in_unit=nc=0;
     for(k=0;k<9;k++)
     {
      if(is_subset(candidate[i][j],candidate[k][j]))
       match_in_unit++;
      else
       arr[nc++]=k;
     }
     if(match_in_unit==candidate[i][j][0])
     {
      for(k=1;k<=candidate[i][j][0];k++)
       for(l=0;l<nc;l++)
	if(_delete(candidate[arr[l]][j],candidate[i][j][k]))
	 work=1;
     }
     if(work)
      return 1;
     match_in_unit=nc=0;
     for(k=(i/3)*3;k<(i/3)*3+3;k++)
      for(l=(j/3)*3;l<(j/3)*3+3;l++)
      {
       if(is_subset(candidate[i][j],candidate[k][l]))
	match_in_unit++;
       else
       {
	arr[nc]=k;
	arr1[nc++]=l;
       }
      }
     if(match_in_unit==candidate[i][j][0])
     {
      for(k=1;k<=candidate[i][j][0];k++)
       for(l=0;l<nc;l++)
	if(_delete(candidate[arr[l]][arr1[l]],candidate[i][j][k]))
	 work=1;
     }
    }
   }
  if(work)
   return 1;
  return 0;
}
int is_subset(int A[],int B[])
{
  int i,j;
  if(A[0]<B[0]||B[0]==0)
   return 0;
  for(i=1;i<=B[0];i++)
  {
   for(j=1;j<=A[0];j++)
    if(A[j]==B[i])
     break;
   if(j>A[0])
    return 0;
  }
  return 1;
}

4. Pointing Pairs

int check_pointing_pairs(int sdk[9][9],int candidate[9][9][10])
{
  int i,j,k,l,x,work=0,match_in_unit,arr[10];
  for(x=1;x<=9;x++)
  {
   for(i=0;i<9;i++)
   {
    match_in_unit=0;
     for(j=0;j<9;j++)
     {
       if(sdk[i][j])
	continue;
       for(k=1;k<=candidate[i][j][0];k++)
	if(candidate[i][j][k]==x)
	 break;
       if(k<=candidate[i][j][0])
	arr[match_in_unit++]=j;
     }
     if(match_in_unit<=2)
      continue;
     for(k=0;k<match_in_unit;k++)
      if(!is_candidate_in_square(candidate,i,arr[k],x,1))
      {
       for(l=0;l<match_in_unit;l++)
       {
	if(arr[l]/3!=arr[k]/3)
	{
	 if(_delete(candidate[i][arr[l]],x))
	  work=1;
	}
       }
      }
     if(work)
      return 1;
   }
  }
  for(x=1;x<=9;x++)
  {
   for(i=0;i<9;i++)
   {
    match_in_unit=0;
     for(j=0;j<9;j++)
     {
       if(sdk[j][i])
	continue;
       for(k=1;k<=candidate[j][i][0];k++)
	if(candidate[j][i][k]==x)
	 break;
       if(k<=candidate[j][i][0])
	arr[match_in_unit++]=j;
     }
     if(match_in_unit<=2)
      continue;
     for(k=0;k<match_in_unit;k++)
      if(!is_candidate_in_square(candidate,arr[k],i,x,2))
      {
       for(l=0;l<match_in_unit;l++)
       {
	if(arr[l]/3!=arr[k]/3)
	{
	 if(_delete(candidate[arr[l]][i],x))
	  work=1;
	}
       }
      }
     if(work)
      return 1;
   }
  }
  return 0;
}
int is_candidate_in_square(int candidate[9][9][10],int i,int j,int x,int par)
{
  int k,l,m;
  for(k=(i/3)*3;k<(i/3)*3+3;k++)
   for(l=(j/3)*3;l<(j/3)*3+3;l++)
   {
    if(k==i&&par==1)
     continue;
    if(l==j&&par==2)
     continue;
    for(m=1;m<=candidate[k][l][0];m++)
     if(candidate[k][l][m]==x)
      return 1;
   }
   return 0;
}

5. Box-Line Reduction

int box_line_reduction(int candidate[9][9][10])
{
  int i,j,k;
  for(i=0;i<9;i++)
  {
   for(j=0;j<9;j++)
   {
    for(k=1;k<=candidate[i][j][0];k++)
    {
     if(!is_candidate_outside_square_row(candidate,i,j,candidate[i][j][k]))
     {
      if(remove_candidate_from_square(candidate,i,j,candidate[i][j][k],1))
       return 1;
     }
    }
   }
  }
  for(i=0;i<9;i++)
  {
   for(j=0;j<9;j++)
   {
    for(k=1;k<=candidate[i][j][0];k++)
    {
     if(!is_candidate_outside_square_column(candidate,i,j,candidate[i][j][k]))
     {
      if(remove_candidate_from_square(candidate,i,j,candidate[i][j][k],2))
       return 1;
     }
    }
   }
  }
  return 0;
}
int is_candidate_outside_square_row(int candidate[9][9][10],int i,int j,int x)
{
  int k,l;
  for(k=0;k<9;k++)
  {
   if(k<((j/3)*3)||k>=((j/3)*3+3))
   {
    for(l=1;l<=candidate[i][k][0];l++)
     if(candidate[i][k][l]==x)
      return 1;
   }
  }
  return 0;
}
int is_candidate_outside_square_column(int candidate[9][9][10],int i,int j,int x)
{
  int k,l;
  for(k=0;k<9;k++)
  {
   if(k<((i/3)*3)||k>=((i/3)*3+3))
   {

    for(l=1;l<=candidate[k][j][0];l++)
    {

     if(candidate[k][j][l]==x)
      return 1;
    }
   }
  }
  return 0;
}
int remove_candidate_from_square(int candidate[9][9][10],int i,int j,int x,int var)
{
  int k,l,work=0;
  for(k=(i/3)*3;k<(i/3)*3+3;k++)
  {
   for(l=(j/3)*3;l<(j/3)*3+3;l++)
   {
    if((var==1&&k!=i)||(var==2&&l!=j))
     if(_delete(candidate[k][l],x))
      work=1;
   }
  }
  return work;
}

6. X-Wing

int xwing(int candidate[9][9][10])
{
  int x,i,j,k,count,work=0,wing[10][10];
  for(x=1;x<=9;x++)
  {
   count=0;
   for(i=0;i<9;i++)
   {
    if(how_many_occurences_in_row(candidate,x,i,count,wing)==2)
     count++;
   }
   
   for(i=0;i<count;i++)
    for(j=i+1;j<count;j++)
    {
     if(is_identical(wing[i],wing[j]))
     {
      for(k=0;k<9;k++)
      {
       if(k!=wing[i][2]&&k!=wing[j][2])
       {
	if(_delete(candidate[k][wing[i][0]],x))
	 work=1;
	if(_delete(candidate[k][wing[i][1]],x))
	 work=1;
       }
      }
     }
    }
  }
  for(x=1;x<=9;x++)
  {
   count=0;
   for(i=0;i<9;i++)
   {
    if(how_many_occurences_in_col(candidate,x,i,count,wing)==2)
     count++;
   }
   for(i=0;i<count;i++)
    for(j=i+1;j<count;j++)
    {
     if(is_identical(wing[i],wing[j]))
     {
  
      for(k=0;k<9;k++)
      {
       if(k!=wing[i][2]&&k!=wing[j][2])
       {
	if(_delete(candidate[wing[i][0]][k],x))
	 work=1;
	if(_delete(candidate[wing[i][1]][k],x))
	 work=1;
       }
      }
     }
    }
  }
  return work;
}
int how_many_occurences_in_row(int candidate[9][9][10],int x,int i,int c,int wing[10][10])
{
  int j,k,count=0;
  for(j=0;j<9;j++)
   for(k=1;k<=candidate[i][j][0];k++)
    if(candidate[i][j][k]==x)
    {
     wing[c][count]=j;
     count++;
     break;
    }
  wing[c][count]=i;
  return count;
}
int how_many_occurences_in_col(int candidate[9][9][10],int x,int i,int c,int wing[10][10])
{
  int j,k,count=0;
  for(j=0;j<9;j++)
   for(k=1;k<=candidate[j][i][0];k++)
    if(candidate[j][i][k]==x)
    {
     wing[c][count]=j;
     count++;
     break;
    }
  wing[c][count]=i;
  return count;
}
int is_identical(int A[],int B[])
{
  int i;
  for(i=0;i<2;i++)
   if(A[i]!=B[i])
    return 0;
  return 1;
}

7. Y-Wing

int ywing(int candidate[9][9][10])
{
  int x,i,j,k,l,a,b,c,m,t,work=0;
  for(x=1;x<=9;x++)
  {
   for(i=0;i<9;i++)
   {
    for(j=0;j<9;j++)
    {
     a=c=-1;
     if(candidate[i][j][0]==2&&(candidate[i][j][1]==x||candidate[i][j][2]==x))
     {
      if(candidate[i][j][1]==x)
       c=candidate[i][j][2];
      if(candidate[i][j][2]==x)
       c=candidate[i][j][1];
      for(k=0;k<9;k++)
      {
       if(candidate[i][k][0]==2&&k!=j)
       {
	if(candidate[i][k][1]==x&&candidate[i][k][2]!=c)
	 a=candidate[i][k][2];
	if(candidate[i][k][2]==x&&candidate[i][k][1]!=c)
	 a=candidate[i][k][1];
	if(a!=-1&&a!=c)
	{
	 for(l=0;l<9;l++)
	 {
	  if(candidate[l][k][0]==2&&l!=i)
	  {
	   if((candidate[l][k][1]==a&&candidate[l][k][2]==c)||(candidate[l][k][2]==a
&&candidate[l][k][1]==c))
	   {
	    if(_delete(candidate[l][j],c))
	    {
	     return 1;
	    }
	   }
	  }
	 }
	}
       }
      }
     }
    }
   }
  }
  for(x=1;x<=9;x++)
  {
   for(i=0;i<9;i++)
   {
    for(j=0;j<9;j++)
    {
     b=c=-1;
     if(candidate[i][j][0]==2&&(candidate[i][j][1]==x||candidate[i][j][2]==x))
     {
      if(candidate[i][j][1]==x)
       b=candidate[i][j][2];
      else
       b=candidate[i][j][1];
      for(k=0;k<9;k++)
      {
       if(candidate[i][k][0]==2&&j!=k)
       {
	if(candidate[i][k][1]==x&&candidate[i][k][2]!=x)
	 c=candidate[i][k][2];
	if(candidate[i][k][1]!=x&&candidate[i][k][2]==x)
	 c=candidate[i][k][1];
	if(c!=-1&&b!=c&&(j/3)*3!=(k/3)*3)
	{
	 for(l=(i/3)*3;l<(i/3)*3+3;l++)
	 {
	  for(m=(j/3)*3;m<(j/3)*3+3;m++)
	  {
	   if(candidate[l][m][0]==2&&l!=i)
	   {
	    if((candidate[l][m][2]==b&&candidate[l][m][1]==c)||
(candidate[l][m][1]==b&&candidate[l][m][2]==c))
	    {
	     for(t=(j/3)*3;t<(j/3)*3+3;t++)
	      if(_delete(candidate[i][t],c))
	       work=1;
	     for(t=(k/3)*3;t<(k/3)*3+3;t++)
	      if(_delete(candidate[l][t],c))
	       work=1;
	    if(work==1)
	     return 1;
	    }
	   }
	  }
	 }
	}
       }
      }
     }
    }
   }
  }
  for(x=1;x<=9;x++)
  {
   for(i=0;i<9;i++)
   {
    for(j=0;j<9;j++)
    {
     b=c=-1;
     if(candidate[i][j][0]==2&&(candidate[i][j][1]==x||candidate[i][j][2]==x))
     {
      if(candidate[i][j][1]==x)
       b=candidate[i][j][2];
      else
       b=candidate[i][j][1];
      for(k=0;k<9;k++)
      {
       if(candidate[k][j][0]==2&&i!=k)
       {
	if(candidate[k][j][1]==x&&candidate[k][j][2]!=x)
	 c=candidate[k][j][2];
	if(candidate[k][j][1]!=x&&candidate[k][j][2]==x)
	 c=candidate[k][j][1];
	if(c!=-1&&b!=c&&(i/3)*3!=(k/3)*3)
	{
	 for(l=(i/3)*3;l<(i/3)*3+3;l++)
	 {
	  for(m=(j/3)*3;m<(j/3)*3+3;m++)
	  {
	   if(candidate[l][m][0]==2&&l!=i)
	   {
	    if((candidate[l][m][2]==b&&candidate[l][m][1]==c)||
(candidate[l][m][1]==b&&candidate[l][m][2]==c))
	    {
	     for(t=(i/3)*3;t<(i/3)*3+3;t++)
	      if(_delete(candidate[t][j],c))
	       work=1;
	     for(t=(k/3)*3;t<(k/3)*3+3;t++)
	      if(_delete(candidate[t][m],c))
	       work=1;
	    if(work==1)
	     return 1;
	    }
	   }
	  }
	 }
	}
       }
      }
     }
    }
   }
  }
  return 0;
}


Discussions and Conclusions              So far what we have discussed have some certain drawbacks. It has been stated that these are the most popular strategies in order to solve Sudoku puzzles of any level. But it is not guaranteed that even after the successful execution of all these strategies the puzzle gets solved completely. Generally these strategies turn out to be sufficient for solving a very typical Sudoku puzzle. But still there is no guarantee that these are always sufficient. There are several more tough to tougher strategies. Although needed rarely, still they may come into play. Even those strategies may not be sufficient at times and at one stage we may just have to try the trial and error method. In this case backtracking is needed. And it amounts a very high complexity. In this case we try out the available candidates for the cells and try to fill the puzzle. As long as the constraints of the board are maintained it is fine, but when we reach a state that the puzzle generated so far looks to be a valid one, but there is a cell where we can’t place any number from 1 to 9 as the constraints seem to get violated we perform backtracking and change the value of the cell which was lastly placed. And when same happening go on even after trying all the candidates for that cell, we backtrack again to change the value of previous to the lastly placed cell, and proceed as this. Now the main problem of this backtracking is that the complexity for this is not known at all, means the variable complexity. It might pull off the things within seconds or might take a while, for example several tens of minutes. But these are the rare cases as it is found from the survey on more than hundreds of Sudoku puzzles of various levels published in the news dailies and web that the implemented strategies are very often found to be more than sufficient in order to fill the puzzle and that too in a very very timely manner. This is the main advantage of our implementation.

References  

http://www.sudokuwiki.org/Naked_Candidates#NP

http://www.sudokuwiki.org/Intersection_Removal#IR

http://www.sudokuwiki.org/X_Wing_Strategy

http://www.sudokuwiki.org/Y_Wing_Strategy

http://en.wikipedia.org/wiki/Sudoku

From → Academics

3 Comments
  1. Ishita Banerjee permalink

    Approach towards solving the problem is commendable. good job

  2. arindam permalink

    great work

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: