Last Updated: 15 Dec, 2020

Sudoku

Easy

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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:

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:

Check for each ARR[ROW][i] where 1<= i <= 9 if, ARR[row][i] is equal to VAL return FALSE.
Check for each ARR[i][COLUMN] where 1<= i <= 9 if, ARR[i][COLUMN] is equal to VAL return FALSE.
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.
Else return TRUE.

Solve now