[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

[XSL] Accessing part of the result tree illustrated wi

Subject: [XSL] Accessing part of the result tree illustrated with "The Sudoku solver" example.
From: Alain <alainb06@xxxxxxx>
Date: Tue, 04 Sep 2007 01:19:45 +0200
 [XSL] Accessing part of the result tree illustrated wi
I guess you already talked a lot about that ("accessing" the result tree), but I couldn't find an complete post.

I think there's a "missing feature" in XSL (or I just haven't found it) when you do recursing programs, but I would appreciate your point of view of experts and W3C members.

I'll try to illustrate my point with a well-known and "fun" example.
Assuming you all know what a SUDOKU is (if you don't, it's easy to find it with your preferred search engine), here is the XML input :


****** XML INPUT **************

<?xml version="1.0" encoding="utf-8"?>
<sudo>
   <ku x="0" y="0" z="0">8</ku>
   <ku x="1" y="0" z="0"></ku>
   <ku x="2" y="0" z="0"></ku>
   <ku x="3" y="0" z="1"></ku>
   <ku x="4" y="0" z="1">4</ku>
   <ku x="5" y="0" z="1"></ku>

<!-- and so on, you must have 81 (9 x 9) "ku" elements...
Empty nodes is where you must find the matching numbers
Not-empty nodes are initial values of your Sudoku puzzle
-->

   <ku x="4" y="8" z="7">8</ku>
   <ku x="5" y="8" z="7"></ku>
   <ku x="6" y="8" z="8"></ku>
   <ku x="7" y="8" z="8"></ku>
   <ku x="8" y="8" z="8">5</ku>

<!-- This last "ku" (number 82) is dedicated to Abel ;-)
It's here so that we can eliminate a not-pretty xsl:if and end gracefully the recursion (a recursion always need an "ending condition"... even with XSL, otherwise it turns to a forever loop and it will most certainly result in an out-of-stack error !).
This "ku" must be the last element in the order of the algorithm, eq here: document order -->


<ku the-end="1"/>

</sudo>


****** XML OUTPUT **************


The solution of the Sudoku.
Same thing as input (elements can be in a different order as long as you have your 81 elements), but all the elements (except the end marker -optional in the output) must have a number that complies with the rules of the Sudoku.




****** BONUS (help) **************
If you want to generate an "empty" Sudoku so that you can enter your own puzzle to solve, just run this template on an XML containing : <sudo/>


With this template, no need to use your keyboard to enter the 81 elements (and you could mistype them, that would break the program).

<!-- Template to generate an "Empty" sudoku puzzle -->
<xsl:output method="xhtml" indent="yes"/>

<xsl:template match="/sudo">
  <sudo>
    <xsl:for-each select="0 to 8">
      <xsl:variable name="y" select="."/>
      <xsl:for-each select="0 to 8">
        <ku x="{.}" y="{$y}" z="{($y idiv 3) * 3 + . idiv 3}"/>
      </xsl:for-each>
    </xsl:for-each>
    <ku the-end="1"/>
  </sudo>
</xsl:template>

Note that it is not XHTML, but the XHTML method is handy because it will serialize the result as <ku x="0" y="0" z="0"></ku> so that it is easy to input the initial values of your puzzle without having to type the closing tag.

In the "ku" elements :
x stands for abscissas
y stands for ordinates
z stands for "zones" (the 3 x 3 inner squares).
You can use the Cartesian coordinate system as it was intended, or reverse the order or direction of the axis, as long as you do that consistently, it will still work.



Here comes the "fun"...
If you've been annoyed by a devilish Sudoku you could not complete, that's the end of your nightmares !



****** XSL : The Magical SUDOKU solver ! **************


<?xml version='1.0' encoding="UTF-8"?>
<xsl:stylesheet version="2.0"
		xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

<xsl:output method="xml" indent="yes"/>

<xsl:template match="/sudo">
  <sudo>
    <xsl:apply-templates select="ku[.=''][1]">
      <xsl:with-param name="sudo" select="."/>
    </xsl:apply-templates>
  </sudo>
</xsl:template>

<xsl:template match="ku">
  <xsl:param name="sudo"/>
  <xsl:variable name="this" select="."/>

<xsl:variable name="existing-numbers"
select="distinct-values($sudo/ku[@x = $this/@x or @y = $this/@y or @z = $this/@z][. != ''])"/>


  <xsl:for-each select="1 to 9">
    <xsl:if test="not(. = $existing-numbers)">

<!-- We found a number that fits in this ku (e.q. not already
existing in the same line/column/zone) so we build a new sudo
replacing current empty "ku" with the value found and we
recurse it -->
<xsl:variable name="next-sudo">
<xsl:copy-of select="$sudo/ku except $this"/>
<ku x="{$this/@x}" y="{$this/@y}" z="{$this/@z}"><xsl:value-of select="."/></ku>
</xsl:variable>


      <xsl:apply-templates select="$next-sudo/ku[.=''][1]">
        <xsl:with-param name="sudo" select="$next-sudo"/>
      </xsl:apply-templates>
				
    </xsl:if>
  </xsl:for-each>
</xsl:template>


<!-- Solution found = we output it (no more empty "ku", the-end must be last element for that) -->


<xsl:template match="ku[@the-end]" priority="1">
  <xsl:param name="sudo"/>

  <xsl:copy-of select="$sudo"/>
</xsl:template>

</xsl:stylesheet>


****** XSL Processor : Saxon8.9J **************



By the way, it does also illustrate the power of XSL: 50 lines including comments and spacing lines for readability and the Sudoku is solved !..


Well, don't tell me it is a bad algorithm, I know it ! It is just "brute force". We recurse on the empty elements and try every possible value that fits in that element up to the point where all the elements have a value matching the Sudoku rules (or no solution if your initial input is incorrect).

Abel, you were right, it is so graceful ending a recursion without a bad looking xsl:if (prioritized template do the job) :-)
But there is still an xsl:if you might try to eliminate. I got a bit confused with sequence functions, and could not find a way to do the equivalent of an "except" on two sequences (it works only for nodes).



You had the "fun" part, now comes the question.



A naive reader might say this algorithm is cool because it gives a solution. Although depending on the initial values you enter and the speed of your computer it might run from a few seconds to many minutes.


But experts as you are, you would have noticed that there is a major BUG: even when we have found the solution, the recursion continues!..
So you can get "lucky" and find a solution in the first seconds, then run for many minutes uselessly just terminating the recursion.


What's missing ?

When we come to the last template (end of recursion) we might have stacked 60 levels (depending on how many numbers you gave to the initial XML) each level being in the middle of a for-each (would have been the same with an apply-templates or other "internal loops").
This design is perfectly correct and is what was intended for this "brute force algorithm", but then when the last templates returns to its caller template, this later template continues with its for-each, and you have no mean of knowing if something was output by the preceding-sibling of the for-each "current-sequence" to stop recursing. So you must continue, assuming that the solution was not found, up to the end (when the first level of the recursion terminates).


That's because constructs like for-each, apply-templates, etc... build internal loops with the selected sequence, and your program "gets the hand" to read a variable constructed by the loop, only when ALL the elements in the sequence has been run through.

So I would expect, as we have a "current context", "current node"... to have a "current-loop-result" being result output by preceding-siblings of the sequence selected by the current for-each or apply-templates (or other loop-like constructs).
Note that, we do not need access to the entire output tree (we can use xsl:variable outside of loops constructs) and also, the entire output tree is not always well-formed if you read it in the middle of a transformation. But an element of sequence of an internal loop always give well-formed XML, or if it does not you get an XSL fatal error.



I don't know if I make my point perfectly clear... but I will continue to illustrate.



So, what solutions do we have to "end the recursion".


*** Piggy solutions *****

Solution 1)
In the end template you do :
<xsl:message terminate="yes">
  <xsl:copy-of select="$the-solution"/>
</xsl:message>

And you output your results on the screen and let the user cope with that !..

Solution 2)
You are a little bit nicer, you do a :
<xsl:result-document ...>

You output the solution in a document and the you do the <xsl:message terminate="yes">The end !</xsl:message>

(Because if you output your solution to the standard output and terminate, as terminate generate an exception, you will have no output at all !)


*** "Clean" solution *****


As the for-each prevents you from knowing what happened with the preceding-sibling of the current node in the selected sequence... just don't use for-each and replace it with a recursion on each element of that sequence.

Here is the XSL code for that

<xsl:template match="/sudo">
  <sudo>
    <xsl:apply-templates select="ku[.=''][1]">
      <xsl:with-param name="sudo" select="."/>
    </xsl:apply-templates>
  </sudo>
</xsl:template>

<xsl:template match="ku">
  <xsl:param name="sudo"/>
  <xsl:variable name="this" select="."/>

<!-- first build a variable with all the numbers that fits in this
"ku" -->
<xsl:variable name="existing-numbers"
select="distinct-values($sudo/ku[@x = $this/@x or @y = $this/@y or @z = $this/@z][. != ''])"/>


  <xsl:variable name="fitting">
    <xsl:for-each select="1 to 9">
      <xsl:if test="not(. = $existing-numbers)">
        <number><xsl:value-of select="."/></number>
      </xsl:if>
    </xsl:for-each>
  </xsl:variable>

  <!-- Then we transform the for-each to a recursion through these
       "fitting" numbers -->
  <xsl:apply-templates select="$fitting/number[1]">
    <xsl:with-param name="sudo" select="$sudo"/>
    <xsl:with-param name="ku" select="."/>
    <xsl:with-param name="other-fitting"
                  select="remove($fitting/number,1)"/>
  </xsl:apply-templates>
</xsl:template>


<xsl:template match="number"> <xsl:param name="sudo"/> <xsl:param name="ku"/> <xsl:param name="other-fitting"/>

  <!-- We recurse through all the numbers and read the result
       in a variable -->

  <xsl:variable name="solution">
    <xsl:apply-templates select="$other-fitting[1]">
      <xsl:with-param name="sudo" select="$sudo"/>
      <xsl:with-param name="ku" select="$ku"/>
      <xsl:with-param name="other-fitting"
                    select="remove($other-fitting,1)"/>
    </xsl:apply-templates>
  </xsl:variable>

  <!-- If something is in the variable, it means that the solution
       was found so, no need to continue recursing -->

<xsl:if test="$solution=''">
<!-- As nothing was found here... we recurse ! -->

<xsl:variable name="new-sudo">
<xsl:copy-of select="$sudo/ku except $ku"/>
<ku x="{$ku/@x}" y="{$ku/@y}" z="{$ku/@z}"><xsl:value-of select="."/></ku>
</xsl:variable>


    <!-- Recursing with the next empty "ku" -->
    <xsl:apply-templates select="$new-sudo/ku[.=''][1]">
      <xsl:with-param name="sudo" select="$new-sudo"/>
    </xsl:apply-templates>
  </xsl:if>

  <!-- We output either nothing, or the solution if it was found -->
  <xsl:copy-of select="$solution"/>
</xsl:template>


<xsl:template match="ku[@the-end]" priority="1"> <xsl:param name="sudo"/>

  <xsl:copy-of select="$sudo"/>
</xsl:template>


That is perfectly correct and works fine and generally faster than the first one.
I saw timings like :
3,7 sec (1st) 1 sec (modified)
13,2 min (1st) 2,25 min (modified)... unlucky or complicated Sudoku


So, ending the recursion when a solution is found works fine and gives better timings as expected.

But when the initial solution was using 2MB memory with its recursions, the second one uses 4MB !
This amount of memory is very small compared to recent computers memory, but that's only an example and small XML input. Think the second solution needs twice as much memory as the first one.


Also, with the "clean" solution, obviously, the code is more complex thus less easy to maintain.

And last, I can't think it is a good idea to say : "Hey you, XSL processor, I know you can do a for-each, but I will do it my own way because I need to access an internal value you would not let me read... and I'm so much smarter than you !". Of course doing your-own-for-each is certainly slower than letting the processor do it (I can guess !).

As you can see in the "clean" solution, we have two templates that look alike because they both recurse on a list, working on the first element of that list and giving the remaining elements for the next steps of recursion. But the first template is made on purpose because we need that to solve our Sudoku Puzzle, and the second template is made on despair because it's the only "clean" solution I could think of ("clean" means without terminate exception, that is in fact a nasty "goto end" we want to avoid) .


So, what would be your advices to clean up my "Sudoku templates" (or any other more "serious" templates having the same needs) and end the recursion properly ?
- an extension function I couldn't notice ?
- future feature XSLT3.0 ?
- stop writing recursing programs with XSL (although XSL seamed perfect to me for recursions) !..



Many thanks in advance. Alain BENEDETTI



Note : you can create additional templates to display your sudokus.xml (initial and solutions) nicely in your browser. That's the easy part and a good exercise for readers that would like to practice XML/XSL/XHTML !

Final note: a Sudoku puzzle, when it is "correct", must have one and only one solution. If you suspect you have been sold a book of Sudoku puzzles containing "incorrect" games that have more than one solution (it's the reason why you could not complete them!), you can run the first XSL templates to check that. Because they recurse all the way round, if you have several solutions it will give you all of them... and may be they might refund your book with this proof.
So, continuing the recursion after having found a solution may not be a bug, it may be a feature afterall!..


Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.