9 Jun 2014

Soduku

Problem Statement:
      Solve the given Soduku
Fig Soduku
Download Source Code
Solution: 
      For optimally solving the above soduku, we would require the technique of Backtracking.

Back-Tracking is a technique which incrementally builds candidates to a solution, and it rejects the candidate as soon as it determines the choosing that particular candidate will not lead to valid solution.
Back-Tracking takes the advantage of choosing and rejecting a candidate in a solution with the help of combined effect of Tail and Head Recursion.

In this problem , backtracking fills up a valid cell with the number , and moves the to the next cell and assumes the same set of conditions as was with the previous cell. At any cell if all numbers from '1' to '9' are invalid, then we back track to the previous cell and fill that with another valid number, then we move to the next cell and continue the process until all cells are filled which will give the solution or the first cell is tried with all numbers fro  1 to 9 and still soduku was not solved, then soduku is unsolvab
le.

The Backtracking sub-routine is shown below: 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 /**
  * Subroutine to solve the Soduku
  * @return true if soduku is solvable
  */
 public boolean solve(int row, int col) {

  if (soduku[row][col] != BLANK)
   nextCell(row, col);

  else {
   // Try the vacant cell with every Number
   for (int num = 1; num <= size; num++) {

    // check if current number can fit the cell with the given
    // constraints
    if (isValid(row, col, num)) {
     soduku[row][col] = num; // Assuming to be true

     if (row == size - 1 && col == size - 1) {
      printSoduku();
      return true;
     }

     if (solve(row, col)) // will be called again and other cells
      return true;    // will be processed
      
     // printSoduku();
     soduku[row][col] = BLANK; // Reverting
    }
   }
  }
  return false; // will be reached if for any cell none of the number(1-9)
      // fit
 }

 /**
  * Find the next free cell
  * @return , true if free cell found and currentRow and currentColumn are set
  */
 private void nextCell(int row, int col) {
  if (col < size - 1)
   solve(row, col + 1);
  else if (row < size - 1)
   solve(row + 1, 0);
 }

To Check if a cell is valid is shown below, for a number to be valid in a cell it should not appear in 
1. the row of that cell
2. the column of that cell
3. the box, the cell belongs to

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 /**
  * check validity of number at the given position, combining the result of 3
  * conditions
  * @return true, if the number can fit at the current position
  */
 private boolean isValid(int row, int col, int num) {
  return checkRow(row, col, num) && checkCol(row, col, num)
    && checkBox(row - row % boxSize, col - col % boxSize, num);
 }

 /**
  * Check particular for the existance of given number (in a particular row)
  * @return true if the number does not exist
  */
 private boolean checkRow(int row, int col, int num) {
  for (int c = 0; c < size; c++)
   if (soduku[row][c] == num)
    return false;
  return true;
 }

 /**
  * Check particular for the existance of given number (in a particular col)
  * @return true if the number does not exist
  */
 private boolean checkCol(int row, int col, int num) {
  for (int r = 0; r < size; r++)
   if (soduku[r][col] == num)
    return false;
  return true;
 }

 /**
  * Check particular for the existance of given given BOX
  * @return true if the number does not exist
  */
 private boolean checkBox(int row, int col, int num) {
  for (int r = 0; r < boxSize; r++) {
   for (int c = 0; c < boxSize; c++) {
    if (soduku[r + row][c + col] == num)
     return false;
   }
  }
  return true;
 }

Happy Coding !! :)

17 comments:

  1. If he seems to go out of his strategy to touch you, particularly if you are alone,
    it can be almost without doubt he likes you. To my mind
    there is nothing simpler or spontaneous than arranging fresh
    flowers in a very vase. If the customer had to purchase
    a display, it might either should be a one-size-fits-all model, or they may have to
    purchase several unique sized exhibits.

    My webpage: portable displays company

    ReplyDelete
  2. At the delicatessen a serve over enables you
    to display every one of the cakes as well as other sweets and sundries which are on offer.
    However, locking in rates early can assist you
    secure the best bargain and help you spread out expenditures
    over the greater span of time for optimum savings.
    Instead of relying upon your basic display to direct any visitors, you can consider using trade show island booths for the more dramatic
    and effective directing force.

    Also visit my web blog; inexpensive trade shows displays

    ReplyDelete
  3. I'm really enjoying the design and layout of your blog.
    It's a very easy on the eyes which makes it much more enjoyable for me to come here and visit more often. Did you hire out a
    designer to create your theme? Excellent work!

    My homepage :: small business website design

    ReplyDelete
  4. Hi, all is going well here and ofcourse every one is sharing information,
    that's in fact excellent, keep up writing.


    Here is my page - simply click the up coming internet page

    ReplyDelete
  5. Hello, the whole thing is going well here and ofcourse every one is
    sharing data, that's really good, keep up writing.

    Feel free to visit my blog :: affiliate product

    ReplyDelete
  6. I am in fact thankful to the owner of this web page who has shared this great article at here.


    Look into my page; social media event

    ReplyDelete
  7. Very nice article, just what I needed.

    Feel free to surf to my page seo london

    ReplyDelete
  8. Nice post. I learn something totally new and challenging on websites I stumbleupon every day.
    It's always exciting to read content from other writers and
    practice a little something from their web sites.


    my web blog social media strategy example

    ReplyDelete
  9. Hey there just wanted to give you a quick heads up
    and let you know a few of the images aren't loading properly.
    I'm not sure why but I think its a linking issue.
    I've tried it in two different internet browsers and both show the same results.


    My webpage: people shouldnt

    ReplyDelete
  10. It's really very difficult in this busy life to listen news on TV, therefore
    I just use the web for that reason, and obtain the most up-to-date news.


    my webpage ... no win no fee solicitors medical negligence

    ReplyDelete
  11. Thanks for every other magnificent article. Where else may anybody get
    that kind of information in such an ideal means of writing?

    I have a presentation subsequent week, and I'm at the search for such info.


    my web blog :: developing a social media strategy

    ReplyDelete
  12. Hi, yes this piece of writing is really good and I have learned lot of things from it regarding blogging.
    thanks.

    Here is my web page - time online

    ReplyDelete
  13. I comment each time I especially enjoy a article on a site or if I have something to add to the conversation. Usually it's caused by the fire displayed
    in the post I looked at. And after this article "Soduku".
    I was excited enough to drop a commenta response :) I actually do have 2 questions for you if it's okay.
    Is it simply me or do a few of the comments appear like they
    are left by brain dead individuals? :-P And, if you
    are writing on other online sites, I would like to keep up with you.
    Would you make a list every one of your social sites like your Facebook page, twitter feed, or linkedin profile?


    Feel free to visit my webpage private jet rental uk

    ReplyDelete
  14. I am sure this post has touched all the internet people, its
    really really good post on building up new website.


    Here is my blog post ... seo detroit

    ReplyDelete
  15. I was able to find good info from your content.

    Take a look at my web blog private jet best

    ReplyDelete
  16. Appreciating the persistence you put into your blog and
    detailed information you offer. It's nice to come across a
    blog every once in a while that isn't the same outdated rehashed
    material. Wonderful read! I've bookmarked your
    site and I'm including your RSS feeds to my Google account.


    My website: freelance designer

    ReplyDelete
  17. Hurrah! Finally I got a web site from where I can genuinely take useful information concerning my study and knowledge.


    Have a look at my web blog :: spend money

    ReplyDelete