Wednesday 5 August 2015

How to validate Sudoku With O(n2) complexity

Sudoko is number placement puzzle, We have to fill 9X9 matrix with numbers ranging 1 to 9 and  following criteria should be fulfilled.

1)  Each row should contain unique digits
2)  Each column should contain unique digits
3)  Each subgrid or region (3X3)(Coloured) should also contain unique digits




For any valid Sudoku, above criterion should be fulfilled.
First we have to check, it should contain digits from 1-9 and should not be repeated in same row. Same is true for column and subgrid.






Lets take a row, it is nothing but 1-D Array with size 9.

How to check whether array has duplicate number or missing number from given range 1-9. ...???

One way to solve this problem is, Sort the array and validate it. Sorting will work here but the complexity would be nlogn or O(n)(counting sort). In case of counting sort space complexity would be O(n).

Is there any way to solve this problem in O(n) time complexity and space complexity should be O(1)...???

Yes, we can achieve it by using XOR operation. Column validation could also be done in similar fashion.

Now, I have to check each highlighted sub grid(3X3).






Lets write a Program to solve this problem in O(n2):

public static boolean isSudokuSolutionValid(int[][] sudoku) {
        int row = 1;
        int col = 1;
        int block1 = 1;
        int block2 = 1;
        int block3 = 1;
        boolean isValid = true;
       for (int i = 0; i < sudoku.length; i++) {

            for (int j = 0; j < (sudoku.length)/3; j++) {
                row = row ^ sudoku[i][j];
                col = col ^ sudoku[j][i];
                block1 = block1 ^ sudoku[i][j];
            }

            for (int j = 3; j < 3+(sudoku.length)/3; j++) {
                row = row ^ sudoku[i][j];
                col = col ^ sudoku[j][i];
                block2 = block2 ^ sudoku[i][j];
            }
            for (int j = 6; j < 6+(sudoku.length)/3; j++) {
                row = row ^ sudoku[i][j];
                col = col ^ sudoku[j][i];
                block3 = block3 ^ sudoku[i][j];
            }
            if ((i + 1) % 3 == 0) {
                if (block1 != 0 || block2 != 0 || block3 != 0) {
                    return false;
                }
                block1 = 1;
                block2 = 1;
                block3 = 1;
            }
            if (row != 0 || col!=0) {
                return false;
            }
            row = 1;
            col = 1;
        }
        return isValid;

    }




 Above Sudoku is  an example of invalid Sudoku.





Above Sudoku is an example of valid Sudoku.

This Problem takes O(n2) complexity to validate whether Sudoku is valid or not.
                        

4 comments:

  1. This solution is unique. It will be nice if you include the program in code tags :-)

    ReplyDelete
  2. I am a beginner learning data structures. Please let me know how did you derive to O(n2) complexity?

    ReplyDelete
    Replies
    1. Hi,
      If you see the program, There is a outer for loop "for(int i = 0; i < sudoku.length; i++)", which runs exactly length of sudoku(say n)in other work 9 times. Inside this for loop we have 3 internal for loop which runs exactly n/3 time.
      so internal loop will be (n/3+n/3+n/3==n). So each value of out loop internal executes n time.
      SO
      1st iteration outer loop == n time internal loop

      2nd iteration outer loop == n time internal loop

      3rd iteration outer loop == n time internal loop
      .
      .
      .
      .
      nth iteration outer loop == n time internal loop


      Total ==> n+n+n+.........+n(n times)
      n(1+1+1+..........+n times)
      n(n)
      O(n2)


      Hope This will help you to understand the complexity. Please post if you have more questions

      Delete
  3. Guys, you can have a graphical java solution here.

    http://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGame_Sudoku.html

    ReplyDelete