Nov
22
2017
--

Sudoku Recursive Common Table Expression Solver

Recursive Common Table Expressions

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:

WITH RECURSIVE
 input(sud) AS (
   VALUES('53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79')
 ),
 digits(z, lp) AS (
   VALUES('1', 1)
   UNION ALL SELECT
   CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
 ),
 x(s, ind) AS (
   SELECT sud, instr(sud, '.') FROM input
   UNION ALL
   SELECT
     substr(s, 1, ind-1) || z || substr(s, ind+1),
     instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
    FROM x, digits AS z
   WHERE ind>0
     AND NOT EXISTS (
           SELECT 1
             FROM digits AS lp
            WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
               OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
               OR z.z = substr(s, (((ind-1)/3) % 3) * 3
                       + ((ind-1)/27) * 27 + lp
                       + ((lp-1) / 3) * 6, 1)
        )
 )
SELECT s FROM x WHERE ind=0;

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:

WITH RECURSIVE
 input(sud) AS (
   SELECT '53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'
 ),
 digits(z, lp) AS (
   SELECT '1', 1
   UNION ALL SELECT
   CAST(lp+1 AS CHAR), lp+1 FROM digits WHERE lp<9
 ),
 x(s, ind) AS (
   SELECT sud, instr(sud, '.') FROM input
   UNION ALL
   SELECT
     concat(substr(s, 1, ind-1) , z , substr(s, ind+1)),
     instr( concat(substr(s, 1, ind-1) ,z ,substr(s, ind+1)), '.' )
    FROM x, digits AS z
   WHERE ind>0
     AND NOT EXISTS (
           SELECT 1
             FROM digits AS lp
            WHERE z.z = substr(s, ((ind-1) DIV 9)*9 + lp, 1)
               OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
               OR z.z = substr(s, (((ind-1) DIV 3) % 3) * 3
                       + ((ind-1) DIV 27) * 27 + lp
                       + ((lp-1) DIV 3) * 6, 1)
        )
 )
SELECT s FROM x WHERE ind=0;

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.

MySQL 8 first run time: 0.16s. 5 runs: 0.16, 0.16, 0.17, 0.16, 0.16
MariaDB Server 10.2 first run time: 0.20s. 5 runs: 0.22, 0.22, 0.21, 0.21, 0.20
MariaDB Server 10.3.2 first run time: 0.206s. 5 runs: 0.237, 0.199, 0.197, 0.198, 0.192
SQLite3 first run time: Run Time: real 0.328 user 0.323333 sys 0.003333 / Run Time: real 0.334 user 0.333333 sys 0.000000

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:

MySQL 8 first run time: 4.87s. 5 runs: 5.43, 5.35, 5.10, 5.19, 5.05
MariaDB Server 10.2 first run time: 6.65s. 5 runs: 7.03, 6.57, 6.61, 6.59, 7.12
MariaDB Server 10.3.2 first run time: 6.121s. 5 runs: 5.701, 6.043, 6.043, 5.849, 6.199
SQLite3 first run time: Run Time: real 10.105 user 10.099999 sys 0.000000 / Run Time: real 11.305 user 11.293333 sys 0.000000

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!

Powered by WordPress | Theme: Aeros 2.0 by TheBuckmaker.com