Sudoku Recursive Common Table Expression Solver

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!

Share this post

Comment (1)

Comments are closed.

Use Percona's Technical Forum to ask any follow-up questions on this blog topic.