Leetcode 37: Sudoku solver - a warm up practice

May 21, 2016

Introduction

It is time to warm up Leetcode 37: Sudoku solver algorithm. The problem statement is here. I reviewed the blog written in July, 2015 first, the blog link is here.

I also like to review one blog written by fightforyourdream, the link is here.

Analysis about Sudoku solver in Chinese

I like to translate the analysis from Chinese to English. The analysis from the above Chinese blog:

典型 DFS/递归/回溯/深搜题。对于 DFS，说白了

1. 什么时候返回？

在本题中，

    1. 当 x > 8 或 y > 8 表示已经遍历完所有的格子，因此成功完成，返回 true。

    2. 当下一个搜索（子搜索）返回true，说明已经找到，返回 true。  

    3. 如果测试过本轮的所有可能解，但无一是对的，说明无解，返回false。  

    4. 如果当前空格不是空格，则改变x，y坐标后，继续下一个空格的尝试

2）DFS 就是针对本轮的所有可能解进行逐一尝试，找到本轮的一个可能解后，这时要调用递归，基于本轮的解对下一轮（子问题）进行求解。如果下一轮（子问题）求解成功，则说明大功告成，及时返回true，停止之后的尝试。

否则如果下一轮（子问题）求解失败，则说明本轮的解不适合子问题，因此，必须换一个本轮的解，然后基于本轮的新解，继续尝试子问题。如果已经本轮所有的解都尝试过了，也都失败了，说明本问题无解，返回false。

当然在每次尝试子问题前和如果失败返回后，都要恢复原来的环境（撤销动作）。

所以，要想使 DFS 成功返回, 条件就是找到满足本轮的解和这个解也要满足下一轮（子问题）。

Analysis in English 

Plan to write down English translation on Nov. 3, 2017.

Warm up practice

May 21, 2016

Try to finish in 30 minutes, here is Julia's C# practice, based on past practice - C# code.