EmergencyEMERGENCY? Get 24/7 Help Now!

Sudoku Recursive Common Table Expression Solver

 | November 22, 2017 |  Posted In: Insight for DBAs, MariaDB, MySQL, MySQL 8.0


Recursive Common Table ExpressionsIn this blog post, we’ll look at a solving Sudoku using MySQL 8.0 recursive common table expression.

Vadim was recently having a little Saturday morning fun solving Sudoku using MySQL 8. The whole idea comes from SQLite, where Richard Hipp has come up with some outlandish recursive query examplesWITH clause.

The SQLite query:

Which should provide the answer: 534678912672195348198342567859761423426853791713924856961537284287419635345286179.

The modified query to run on MySQL 8.0.3 release candidate and MariaDB Server 10.2.9 stable GA courtesy of Vadim:

The test environment for the setup is a standard Linode 1024 instance, with one CPU core and 1GB of RAM. The base OS was Ubuntu 17.04. MySQL and MariaDB Server were installed via their respective tarballs. No configuration is done beyond a basic out-of-the-box install inside of the MySQL sandbox. This is similar for sqlite3. Remember to run “.timer on” for sqlite3.

Note that initially they were done on separate instances, but because of the variance you get in cloud instances, it was decided that it would be better to run on the same instance using the MySQL Sandbox.

Trying a more complex Sudoku routine, “..41..2.3……..12…..8..82.6.43…..8.9…..67.2.48..5…..64……..3.7..69..” to produce the result “574198263638425791219367854821654379743819625956732148195273486462981537387546912″the results are:

Conclusions from this fun little exercise? SQL, even though it’s a standard is not portable between databases. Thankfully, MySQL and MariaDB are syntax-compatible in this case! MySQL and MariaDB Server are both faster than sqlite3 when returning a recursive CTE. It would seem that the MySQL 8.0.3 release candidate is faster at solving these Sudoku routines compared to the MariaDB Server 10.2 stable GA release. It also seems that MariaDB Server 10.3.2 alpha is marginally quicker than MariaDB Server 10.2.

Kudos to Team MariaDB for getting recursive common table expression support first in the MySQL ecosystem, and kudos to Team MySQL for making it fast!

Colin Charles

Colin Charles is the Chief Evangelist at Percona. He was previously on the founding team for MariaDB Server in 2009, worked in MySQL since 2005, and been a MySQL user since 2000. Before joining MySQL, he worked actively on the Fedora and OpenOffice.org projects. He’s well known within many open source communities, and has spoken on the conference circuit.

One Comment

  • For another take on solving sudokus with MySQL, I wrote a rather lengthy 3-part article on the subject and optimization for sudoku solving. It’s written in French but Google Translate usually does a job good enough for you to be able to understand!

    Part 1 (https://endormitoire.wordpress.com/2012/01/07/comment-presser-un-citron-premiere-partie/),
    Part 2 (https://endormitoire.wordpress.com/2012/01/08/comment-presser-un-citron-deuxieme-partie/)
    Part 3 (https://endormitoire.wordpress.com/2013/05/27/comment-presser-un-citron-troisieme-partie/).

    The blog post is titled “Comment presser un citron” which roughly translate to “How to squeeze a lemon” !

Leave a Reply