Wednesday, September 30, 2020

Diabolical Sudoku Solver

Here we are again at another MATLAB program show-off: SuDoKu Solver v11.

SuDoKu Solver v11

Yes, you read that right. A huge quantal jump from the current v7.2 to v11.0 because four new Logics have been added over the last month or so. This allows SS v11 to solve more Sudokus like the ‘diabolical’ ones that appear in newspapers, or generated at the ‘Grandmaster’ level in “MS Sudoku” game, which are only rarely really diabolical. But who is looking at the meaning of that word, anyway?

Those who remember my first detailed post about this MATLAB program will know that 1+3 Logics were ‘my own’ but other 2 ‘advanced’ Logics (Grids and Chains) were borrowed from the exhaustively detailed website on Sudoku strategies: SudokuWiki.org (SW). Continuing that tradition, I have borrowed a lot more this time and implemented them in my own way and bunched them up in 4 more advanced Logics (Scissors, Pincers, Cycles and Nets). That makes a total of 10 Logics and one Smart Brute Force Algorithm leading the way straight to v11.0 and Release 22.

Before I go on to map my ‘Logics’ to SW’s ‘Strategies’, let me talk a little about other important changes. One change that has already appeared in the changelog is the display of recording indicator [] when speech input is on. “Why is this change repeated here again then?”, one might ask. To that non-reader of my posts, I say “Because I am proud of that achievement and this is a show-off post. So get in line with the program and stop interrupting my train of boasts heading full-speed towards the Grandiose Terminal!”. Another significant change that hits visually when SS starts solving a Sudoku is that the various possibilities in cells keep updating as other cells get filled with final answers. It is as if someone forgot to turn off the “Solve Partially” option. It really brings the dynamism of a Sudoku puzzle to the foreground which the visual senses take in to relive its full kaleidoscopic glory. I wish I could write such non-sensical sentences with all the vigour and gusto rivalling those novelists who do it for a living.

Visibility of Possibilities

Talking about solving a sudoku, the nonlinear run over the Logics has also been tweaked to follow SW’s style, up to a point. A major difference is that I still don’t go checking for “Single Possibilities” after every single successful application of a Logic. I check it ‘sneakily’ instead and if no such possibility has arisen, I continue with the same Logic looking for next chain or pincer or net or whatever. Once that is properly done, I go back to the start of the list of Logics (Logic 2 in the table below) and re-iterate till all the Logics are exhausted or the Sudoku is completely solved. Other changes include updated Logic descriptions (including name changes of the Logics), updated colour palette for names of the Logic in the “Comments” box, and some minor code enhancements and cosmetic changes.

Update: I forgot to mention one of the only, really new feature in the program: "Export Solution". Using this menu option, you can export the list of steps that appear on the right as a webpage to compare with other solutions and/or scrutinize the Logics used by the solver. You can see an example in the webpage linked at the end of this post.

Ten Shades of Red

Now let’s enumerate the Logics implemented in v11:

No. Logics in SS v11 Strategies on SW
1 Single Possibilities Hidden Singles [1]
2 Reduction via Intersection Intersection Removal [5,6]
3 Reduction to Multi-sets Hidden Candidates [3,4]
4 Deduction from Multi-sets Naked Candidates [2,4]
5 Deduction from Grids X-Wing [7], Swordfish [10], Jellyfish [16]
6 Deduction from Chains* Simple Colouring [8]
7 Deduction from Scissors Y-Wing [9], XYZ-Wing [11], WXYZ-Wing [21]
8 Deduction from Pincers XY-Chains [14]
9 Deduction from Cycles X-Cycles [12]
10 Deduction from Nets 3d Medusa [15]

*Logic 6 included four rules till v7.2 – two based on “simple colouring” and two on “multi-colouring”. However, it turns out that the two latter rules have been deprecated in favour of six rules of “3d Medusa”. Thus, I have also stripped Logic 6 down to include just the two former rules (and updated their implementation as digging in my decade old code made me realize I had coded only 2 out of 3 cases for one of the rules and 1 out of those 2 cases had a bug so, effectively, I had coded only 1/3 of that rule!) and implemented 3d Medusa in Logic 10 as seen above.

Finally, let’s end this post with some discussion and future outlook as one does in a research paper. One point of discussion is that Logic 9 may be merged with Logic 6 in a future version as both deal with colouring of a single digit. How will that affect the versioning would then become another point of discussion. Second point of discussion could be that the way I have implemented Logic 7 reeks of incompetence, especially given that I pride myself in being a MATLAB programmer. Third point of discussion is whether this program will be ever ported to a uifigure-based app like PG or KC. The short answer is: NOT in the near future. The long answer is: HELL NO! Such an app cannot handle so many “drawnow” commands and unnecessarily slows down the solver (as of R2020b). The speech input via “text()” function had serious issues till now, which have been just fixed in MATLAB R2020b (Very many thanks to the MathWorks support team and engineers who took interest in my ‘bug reports’ and ‘service requests’ regarding this). Though, the implementation is still rough ‘around the edges’ leading to the feeling of overall ‘slowness’ of the app GUI. So ya, I won’t port SS (and even AB because of the heavy usage of GUILT) to uifigure-based app for the foreseeable future.

The last point of discussion is what more can one expect in terms of additions to the list of Logics in SS. The short answer is: NOT much. The long answer is: I don’t think I will ever try to implement “Extreme” strategies of SW so let’s only consider the list till “Diabolical” strategies totalling 22 strategies. I am not interested in the strategies related to uniqueness so four strategies numbered [13, 17, 19 & 20] (numbers as of writing this post) can be safely ignored. That leaves only two strategies out of the 22 that I have not included in SS yet: SK Loops [18] and APE [22]. Not sure about the former but the latter has been on my mind since more than a decade as one can verify from the end of my previous post. So over the course of next couple or so years, we may see one major version upgrade: SS v12. Till then, have a go at

SUDOKU SOLVER 11.0.σ Release 22

No comments:

Post a Comment