Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

Sudoku Solver Problem

Given a partially filled two-dimensional integer array, fill all the empty cells such that each row, each column and each 3 x 3 subgrid (as highlighted below by bolder lines) has every digit from 1 to 9 exactly once.

Example



Input:

8 4 9 0 0 3 5 7 0

0 1 0 0 0 0 0 0 0

7 0 0 0 9 0 0 8 3

0 0 0 9 4 6 7 0 0

0 8 0 0 5 0 0 4 0

0 0 6 8 7 2 0 0 0

5 7 0 0 1 0 0 0 4

0 0 0 0 0 0 0 1 0

0 2 1 7 0 0 8 6 5


Output:

8 4 9 1 6 3 5 7 2 

3 1 5 2 8 7 4 9 6 

7 6 2 4 9 5 1 8 3 

1 5 3 9 4 6 7 2 8 

2 8 7 3 5 1 6 4 9 

4 9 6 8 7 2 3 5 1 

5 7 8 6 1 9 2 3 4 

6 3 4 5 2 8 9 1 7 

9 2 1 7 3 4 8 6 5


Notes

Input Parameters: The function has one parameter, a two-dimensional integer array. Outer array has nine rows. Each of the inner arrays has nine integers of one row. Empty cells of the sudoku board are represented by 0.

Output: Return a two-dimensional integer array with the empty values filled correctly.

Constraints:

  • Size of the input array is exactly 9 x 9
  • 0

Optimal Solution

To solve this problem, we will use backtracking. Try each number from 1 to 9 in each empty cell one by one, check if the current position is safe, then recurse for the board with that particular cell filled. While continuing in a similar fashion, if all cells can be finished, then we have found the solution, else backtrack to the previous cell filled, try the next number from 1 to 9 in the loop, and proceed similarly. If all the digits in the loop have been tried and no answer has been found, backtrack more and keep continuing the same process. Please note that here we spend time exploring only the worthy options and not all the possible solutions.

Check the following diagrams

Diagram for problem statement:

If we start filling the board as we discussed, we will first fill 1 in the first empty cell (marked with blue colors), then next cell with 2, next with 6 (as 1,2,3,4 and 5 are not safe there).. and so on, we find that after filling 9 in the second row, the next cell cannot have any number ranging from 1 to 9, so we backtrack and increase the  previously filled cell by 1 and check for safety. Since the previously filled number is also 9 and at the end of the loop, we backtrack more to fill in 6 instead of 5 in the second row. This process continues until all the cells are filled correctly and the correct configuration is found.

Board configuration after all cells filled correctly:




Time Complexity:

The time complexity for solving sudoku using backtracking is tricky to calculate. The worst case time complexity is equal to the number of possible board configurations which is 9^81. This can be even boiled down to 9^k where k is the number of empty cells in the initial board configuration. Even now, we do not calculate all the possible options and prune a huge number of possibilities.

So, worst case time complexity is O(9^k).

Auxiliary Space Used:

O(1). Since we can have a maximum of 81 depth (81 empty cells) in the recursion function stack, the space required is constant.

Space Complexity:

O(1).


Try yourself in the Editor

Note: Input and Output will already be taken care of.

Sudoku Solver Problem

Given a partially filled two-dimensional integer array, fill all the empty cells such that each row, each column and each 3 x 3 subgrid (as highlighted below by bolder lines) has every digit from 1 to 9 exactly once.

Example



Input:

8 4 9 0 0 3 5 7 0

0 1 0 0 0 0 0 0 0

7 0 0 0 9 0 0 8 3

0 0 0 9 4 6 7 0 0

0 8 0 0 5 0 0 4 0

0 0 6 8 7 2 0 0 0

5 7 0 0 1 0 0 0 4

0 0 0 0 0 0 0 1 0

0 2 1 7 0 0 8 6 5


Output:

8 4 9 1 6 3 5 7 2 

3 1 5 2 8 7 4 9 6 

7 6 2 4 9 5 1 8 3 

1 5 3 9 4 6 7 2 8 

2 8 7 3 5 1 6 4 9 

4 9 6 8 7 2 3 5 1 

5 7 8 6 1 9 2 3 4 

6 3 4 5 2 8 9 1 7 

9 2 1 7 3 4 8 6 5


Notes

Input Parameters: The function has one parameter, a two-dimensional integer array. Outer array has nine rows. Each of the inner arrays has nine integers of one row. Empty cells of the sudoku board are represented by 0.

Output: Return a two-dimensional integer array with the empty values filled correctly.

Constraints:

  • Size of the input array is exactly 9 x 9
  • 0

Optimal Solution

To solve this problem, we will use backtracking. Try each number from 1 to 9 in each empty cell one by one, check if the current position is safe, then recurse for the board with that particular cell filled. While continuing in a similar fashion, if all cells can be finished, then we have found the solution, else backtrack to the previous cell filled, try the next number from 1 to 9 in the loop, and proceed similarly. If all the digits in the loop have been tried and no answer has been found, backtrack more and keep continuing the same process. Please note that here we spend time exploring only the worthy options and not all the possible solutions.

Check the following diagrams

Diagram for problem statement:

If we start filling the board as we discussed, we will first fill 1 in the first empty cell (marked with blue colors), then next cell with 2, next with 6 (as 1,2,3,4 and 5 are not safe there).. and so on, we find that after filling 9 in the second row, the next cell cannot have any number ranging from 1 to 9, so we backtrack and increase the  previously filled cell by 1 and check for safety. Since the previously filled number is also 9 and at the end of the loop, we backtrack more to fill in 6 instead of 5 in the second row. This process continues until all the cells are filled correctly and the correct configuration is found.

Board configuration after all cells filled correctly:




Time Complexity:

The time complexity for solving sudoku using backtracking is tricky to calculate. The worst case time complexity is equal to the number of possible board configurations which is 9^81. This can be even boiled down to 9^k where k is the number of empty cells in the initial board configuration. Even now, we do not calculate all the possible options and prune a huge number of possibilities.

So, worst case time complexity is O(9^k).

Auxiliary Space Used:

O(1). Since we can have a maximum of 81 depth (81 empty cells) in the recursion function stack, the space required is constant.

Space Complexity:

O(1).


Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Accelerate your Interview prep with Tier-1 tech instructors
blue tick
360° courses that have helped 14,000+ tech professionals
blue tick
100% money-back guarantee*
Register for Webinar

Recommended Posts

All Posts