Sudoku

Easy
0/40
6 upvotes
Asked in companies
SalesforceMakeMyTripProvidence Global Center LLP

Problem statement

You are given a 9x9 sudoku. Your task is to solve sudoku and return the solution.

A sudoku is a puzzle in which players insert the numbers one to nine into a grid consisting of nine squares subdivided into a further nine smaller squares in such a way that every number appears once in each horizontal line, vertical line, and square.

For example: Consider following sudoku:

example1

To solve it you have to fill blank spaces by numbers from 1 to 9 subject to constraints:

Any number should not occur more than once per row.

Any number should not occur more than once per column.

Any number should not occur more than once per block of 3x3(here, each block is distinguished by bold borders).

It will be solved as:

example1

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

First nine lines of input contain N(=9) space-separated integers, representing elements of 2D array ARR.

Note: Empty slots in the input are represented by number 0.

Output Format

For each test case, return the solution of sudoku.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

The system will print ‘CORRECT SOLUTION’ if your solution to sudoku is correct, ‘INCORRECT SOLUTION’ otherwise.

Constraints:

N = 9
0<= ARR[i][j] <=9

Time Limit: 1 second

Sample Input 1:

0 8 0 0 0 0 5 0 2
0 0 4 0 0 5 0 0 0
3 0 0 0 4 0 8 0 0
0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 6 9
0 0 0 2 0 0 0 0 0
0 1 0 0 5 0 2 0 8
7 6 0 0 0 0 0 0 0
2 0 0 9 0 0 1 0 0

Sample Output 1:

CORRECT SOLUTION

Explanation of Input 1:

The output will be CORRECT SOLUTION  when you return correct solution to sudoku. Here, it will be:
1 8 7 3 6 9 5 4 2
9 2 4 7 8 5 6 1 3
3 5 6 1 4 2 8 9 7
8 4 3 5 9 6 7 2 1 
5 7 2 4 1 8 3 6 9
6 9 1 2 3 7 4 8 5
4 1 9 6 5 3 2 7 8
7 6 5 8 2 1 9 3 4
2 3 8 9 7 4 1 5 6

Sample Input 2:

0 0 0 0 0 0 0 0 0
5 0 0 2 0 0 0 0 0
0 6 8 0 0 4 0 9 0
1 2 0 0 0 0 0 0 0 
0 0 0 0 0 0 9 0 5
0 0 0 1 4 0 0 6 0
9 0 0 3 0 5 0 0 0
0 0 0 0 0 8 1 4 6
8 0 0 0 7 0 3 0 0

Sample Output 2:

CORRECT SOLUTION
Hint

Try to place each number from one to nine at each empty slot one by one and check if it is not violating any constraint.

Approaches (1)
BACKTRACKING

Our approach here will be to check for each empty slot that filling it with which number will not violate any constraint. We will start from the first block and keep on checking for each block using recursion. Consider a function SOLVESUDOKU for this, that accepts as a parameter an ArrayList ARR and  do:

  1. Check, if ARR[i][j] = 0 for each 1<=i<=9 and 1<=j<=9:
    1. Iterate for each 1<= VAL <=9 and update ARR[i][j] to VAL and check if it is safe to place VAL at ARR[i][j] using function ISSAFE:
      1. If it is safe, call the function SOLVESUDOKU for ARR.
      2. Else make ARR[i][j] = 0.

To check if it is safe to place any value at an index, we use function ISSAFE that accepts ArrayList ARR, integer VAL, integer ROW and integer COLUMN as parameters and do:

  1. Check for each ARR[ROW][i] where 1<= i <= 9 if, ARR[row][i] is equal to VAL return FALSE.
  2. Check for each ARR[i][COLUMN] where 1<= i <= 9 if, ARR[i][COLUMN] is equal to VAL return FALSE.
  3. Check for each block i.e. for each ARR[i][j], ROW-(ROW%3) <= i <= (ROW-(ROW%3))+3 and COLUMN-(COLUMN%3) <= i <= (COLUMN-(COLUMN%3))+3, if ARR[i][j] is equal to VAL return FALSE.
  4. Else return TRUE.
Time Complexity

O(9^N*N), where N is the length of array ARR because for every element of ARR we have 9 options, number one to nine.

Space Complexity

O(N*N), where N is the length of array ARR because a function call stack will be created in the memory. It is the total space required to store the elements.

Code Solution
(100% EXP penalty)
Sudoku
Full screen
Console