SudokuSolve

A Java implemention for solving sudoku puzzle.

The problem first comes from LeetCode#37

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 the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
• Empty cells are indicated by the character '.'.

Note:

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

The basic algorithm is Backtracking, several performance optimizations were included:

• Use a 1-Dimension array to replace the 2-Dimension array to be CPU-cache friendlly.
• Bits operations to accelerate Set Union.
• Use an int array to perform as a stack to aviod recursive.
• Certain order to reduce search-tree depth.

This solution can beats 90% of the total submissions, More details please click Here,the article is written in Chinese.