• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Problem Statement:


Given a Sudoku, design an algorithm to solve it.

A sudoku solution must satisfy all of the following rules:
  • Each of the digits 1-9 must occur exactly once in each row.
  • Each of the digits 1-9 must occur exactly once in each column.
  • Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '0' character indicates empty cells.

Solution:


  • NOTE: I highly recommend going through the Backtracking chapters in the order they are given in the Index page to get the most out of it and be able to build a rock-solid understanding.


This is one of my personal favorites. Solving this problem shows the power and advantage of knowing the basic algorithms really good.

If someone is asked to design an algorithm with working code in a 40 mins coding interview, it might seem daunting. But here we would see how if you understand how backtracking works you would be able to come up with a very simple yet elegant algorithm with working code in under 30 minutes.

The concept is simple: we do an exhaustive search. For every cell that does not contain '.' we compute what are the values that cell can contain, and for each and every valid candidate we recursively call backtrack(...) to see if we can get a valid solution. Once we get the first valid solution the process stops.

We will be using our backtracking template discussed in Backtracking Fundamentals to write our code.



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Don't forget to take in-depth look at the other backtracking problems because that is what would make you comfortable with using the backtracking template and master the art of Backtracking:


The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave