I wonder if I ever get serious and finish my projects or any for that matter. Last time I presented a fairly complicated algorithm idea about a more humanized based Sudoku solver instead of the brute force ones that applications usually utilize.

Someone can argue, what’s the point of creating a fairly complicated solution to a simple problem that can be solved in just a few seconds using brute force.

Well Because its fun. So, here you go, another made up Sudoku solving algorithm

This time, I though, that it would be interesting to combine my geometrical and topological background, as well as some GIS based algorithms that we have developed over time.

The first implementation cannot solve all Sudoku puzzles but it can do fairly well in medium strength ones like this one

input

1 |
input.9.........1..6....6..8..7.3......1.....39.......5...217.4...28.....3....86....57 |

output

1 |
894317265731526894562984173358642719247139586619758432173465928925873641486291357 |

The first step in solving is pretty straight forward. Create a set of horizontal and vertical lines through each number and Classifying two types of intersections (green and yellow, see image below).

It is pretty much obvious, on the above diagram, that where the arrow points the number 8 should be filled.

The same algorithm can be applied three-wise horizontally, vertically and as the examples box-based.

The core algorithm lies in the following code

where **_lnsGeometrys[i]** is the collection of available horizontal lines,

**_clsGeometrys[i]** is the collection of available vertical lines

and **_binaryMatrix** is a sudoku matrix filled with zeros

STEP A) The algorithm chooses the lines that are needed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public static void MatchLinesWithNumbers() { for (int p = 1; p <= 9; p++) { var tListL = new List<IGeometry>(); var tListC = new List<IGeometry>(); for (var i = 0; i <= _matrix.GetUpperBound(0); i++) { for (var j = 0; j <= _matrix.GetUpperBound(0); j++) { if (_matrix[i, j] == p) { tListL.Add(_lnsGeometrys[i]); tListC.Add(_clsGeometrys[j]); } } } GetInterSections(tListL, tListC); . . . //SOLVER CODE (what interprets the above results) } |

STEP B) Then it calculated all intersections

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public static void GetInterSections(List<IGeometry> tListL, List<IGeometry> tListC) { var inters = new List<IGeometry>(); foreach (IGeometry c in tListL) { IGeometry c1 = c; inters.AddRange(from t in _clsGeometrys where c1.Intersects(t) select c.Intersection(t)); } foreach (IGeometry c in tListC) { IGeometry c1 = c; inters.AddRange(from t in _lnsGeometrys where c1.Intersects(t) select c.Intersection(t)); } BinaryPattern(inters); } |

STEP C) creates a binary matrix with all intersections points

1 2 3 4 5 6 7 8 |
public static void BinaryPattern(List<IGeometry> tList) { foreach (var geometry in tList) { _binaryMatrix[(int) geometry.Centroid.Y, (int) geometry.Centroid.X] = 1; } } |

STEP D) each number with its equivalent binary matrix is fed in the **solver **function (see STEP A, function)

Obviously every time a number is filled, the process repeats it self until it either solves the puzzle or reach a dead end.