Solving Sudoku with XSLT

Introduction

If you run into XSLT, having used only imperative languages so far, you might be a bit startled!

If that can help, what made me click is when I asked on the mailing list: "When I run a template on a node list, how can I count how many nodes have already been processed so far?"

Wasn't that a stupid question? Short answer: you can't!

Long answer: look at the description of current node, current node list and processing model.

Basically, when you run an XSL tranformation you are always executing a template. This template is instantiated with a current node that belongs to the current node list. So yes, there is an order: the order of the current node list, which is an immutable value for the current template (unless you enter a repetition). This order allows you to know the position() of the current node in the current node list. The current node is the base for all relative location paths you will use to trigger further computations.

The processing model says that the result of the tranformation MUST be as if all nodes in the current node list where instantiated sequentially (eg one by one from position() 1 to last()). But it also clearly states that as long as the result respects that, the implementation is free to instantiate nodes in any order it sees fit.

So you can imagine an implementation that computes the current node list, picks the template and instantiates it in parallel on different process/cores/machines, each instantiation receiving a different node from the list. That would be a perfectly valid implementation as long as the final result is reordered according to the initial current node list. It could even be very useful on a multi-core processor for some kind of transformations. It could also be the way to go on distributed architectures (à la "Big Data"), to push the templates on Data Nodes: sort of "distributed current node list", or XSLT-map-reduce! Then, all the nodes will be processed simultaneously, and you understand now why the initial question does not make any sense: there is no such thing as "processed so far" on a node list. Also, having that would create huge "side effects" that XSLT seeks to avoid.

Once you understand that, variables that do not vary and if with no else (you can do without... even without any if or choose at all!) will be the least of the peculiarity of XSLT!

XSLT is awesome!

Yes it is!

Ok... it might have some minor inconveniences, let's face it!

But look at the bright side:

Solving the Sudoku in 20 lines of XSLT!

See, although XSL is verbose, it takes only 20 lines to solve the Sudoku (in XSLT1.0).

I originally made that to check if a sudoku had a unique solution. Thus it will recurse up to the end, even if a solution was already found in the first iterations. In the end, it will tell you if there are no solutions, only one, or several, and display them.

  <!--
  This is THE solving template !
  (yes only 15 lines of code to solve, but it is "brute force")
  Principle is simple:
  - this template is called with the first empty cell
  - we find what can fit in this cell
  - for every number that fits, we build a new sudoku containing all the cell except the current one
    current cell is replaced by a cell containing the value that fits
  - we call recursively the same template
  -->
  <xsl:template match="cell" mode="solve">
    <xsl:param name="numbers"/>
    <xsl:param name="cells"/>
    <xsl:variable name="this" select="."/>

      <!-- We find numbers that fit in this cell (e.q. not already existing in the same line/column/zone)
      so we build a new grid of cells replacing current empty cell with the value found and we recurse it -->
    <xsl:for-each select="$numbers[not (.= $cells[@L = current()/@L or @C = current()/@C or @B = current()/@B][. != '']) ]">
      <xsl:variable name="next-cells">
        <xsl:copy-of select="$cells[not (@L = $this/@L and @C = $this/@C)]"/>
        <cell L="{$this/@L}" C="{$this/@C}" B="{$this/@B}" bold="no"><xsl:value-of select="."/></cell>
      </xsl:variable>

      <xsl:apply-templates select="exslt:node-set($next-cells)/cell[.=''][1]" mode="solve">
        <xsl:with-param name="numbers" select="$numbers"/>
        <xsl:with-param name="cells" select="exslt:node-set($next-cells)/cell"/>
      </xsl:apply-templates>
    </xsl:for-each>

  </xsl:template>

  <!-- 
  This is the "end recursion condition".
  Having a "marker" simplifies the process as it can then be just a template
  If this template is reached it means that all the empty cells were filled with a value that works.
  So a solution found = we output it to the main result.
  Note that the recursion will continue, searching for other possible solutions
  -->
  <xsl:template match="cell[@the-end]"  mode="solve">
    <xsl:param name="cells"/>
    <grid>
      <xsl:copy-of select="$cells"/>
    </grid>
  </xsl:template>

Time to experiment it!

You can enter your own sudoku here on the empty grid.

Here are some examples that run in less than 2 minutes on a reasonable 2008 computer.

Limitation and warning.

As you can guess from the templates, it does NOT check that your input respects the Sudoku's rules! Let's say you'll enter a sudoku full of 1's and let one cell empty, it will gladly find 8 solutions. As an good exercice, you could try to add a template that checks it. ;-)
Obviously, this limitation does not apply to the examples: they are all correct sudokus, except for the variant with no solution or several (there is a non-official rule saying that a "correct" sudoku must have a unique solution).

Of course, the other huge limitation is that this is a "brute force" algorithm. It tries all possible solutions... and that could be veeeery long depending on your initial grid. It is probably the slowest Sudoku solver you can find on the net!

WARNING: note that apparently browsers do not do any kind of garbage collection during an XSL Transformation! I assume that is because such a transformation is thought to be quick and PC have a lot a memory, so you won't need that. Unfortunately, that is not true here, a sudoku can take very long time to solve. This means that the browser will gradually fill the memory, where a sound GC would limit the memory need to N times the sudoku grid, plus one grid per solution, where N is the number of initial free cells. Then two things happen: on Windows the browser will crash, on Linux you will start gradually filling up you swap, your system will probably become completely irresponsive, and in the end the browser might still fail with an "out of memory" error. So, if you plan to solve a difficult Sudoku, save every document you might have opened before in case you have to switch off abruptly your PC!

Code

The full code, including the php part (that only reflects back your sudoku grid with the solve-it.xsl template) is available on my GitHub: https://github.com/Bylon/XSLT_Sudoku_Solver

Licence.

The XSLT Sudoku Solver

MIT License

Copyright (c) 2016 - Alain BENEDETTI

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.