[Matlab] N X N Sudoku Solver

A few yrs ago, a mathematician created above sudoku, he claims it is the hardest sudoku at that time. For interest, I tried to create an algorithm to solve this stuff.

Due to my laziness, I had created the logic part a year ago, but just have finsihed the guessing part of the algorithm recently.

Below is my algorithim to solve N x N sudoku, where N = n^2, n is positive integer.
N is set as 9, the usaul size of most of sudoku.

In my current acknowledgement, the algorithm to solve a sudoku can be divided into two parts mainly --- Logical Deduction And Guessing.

Logical Deduction:
 As the title mentions, logically deduct the candidates of each unfilled blocks for one or many iterations, untill all the blocks are filled. Below is the algorithm

A. Omit Candidates of each unfilled blocks one by one.
a. list all the potential candidates(1-9) of each block

b. Check the row, column and the local 3x3 matrix of the blocks belonging, omit the impossible candidates

c. If only one candidates is left, fill the block.

d. If all the other blocks of the row, column, or the local 3x3 matrix are filled, then fill in the block with the right candidate.

e. if no cnadidate is left, then the solution is determined as wrong.

f. Redo above process untill the sudoku is finished or checked as wrong.


B. Omit Candidates in a local 3x3 matrix if the N blocks in a row or column of a local matrix have N candidates.
There are some cases that the algorithim part A cannot process further. The algorithim part B was created to handle these cases.

a. If there are N blocks in the same row or column of a local 3x3 matrix, all of them have N identical candidates.It implies the other two local rows and columns should not have these candidates. Then, omit these candidates from the other two local rows or columns.


Combing above two algorithm, this Logical Deduction algorithm can finish most of the sudoku.
---------------------------------------------------------------------------------------------------------------------------------

However, there are still some sudoku like the hardest one require guessing.
Below is the algorithm of the Generic Sudoku Solver.

2. Generic Sudoku Solver:
a. Solve the sudoku by Logical Deduction

b. If not finished or still correct, continue to step, c).

c. Count the possible candidates of each blocks

d. Select the block with the least candidates, then fill in one of the candidate, do the Generic Sudoku Solver with the new sudoku recursively.

e. if the returend sudoku is correct and complete, then stop the process.


By this algorithm, only three seconds and 114 times of guessing to solve this sudoku.
below is my answer

As Matrix is excellent for matrix operations, so Matlab was used to implement this algorithm.
Below is the code reference.
https://github.com/walter426/Matlab_SudokuSolver/