At the time of writing XSL Transformations (XSLT) Version 3.0 (W3C Working Draft 10 July 2012) is still a working draft. I can’t test this, but this is my estimate of what a solution for the Knight’s tour might look like in XSLT 3.0 .d
First we build a generic package for solving any kind of tour over the chess board. Here it is…
(Updated 31-Oct-2012)
<br /><xsl:package xsl:version="3.0"<br /> xmlns:xsl=&amp;quot;http://www.w3.org/1999/XSL/Transform&amp;quot;<br /> xmlns:xs=&amp;quot;http://www.w3.org/2001/XMLSchema&amp;quot;<br /> xmlns:fn=&amp;quot;http://www.w3.org/2005/xpath-functions&amp;quot;<br /> xmlns:tour=&amp;quot;http://www.seanbdurkin.id.au/tour&amp;quot;<br /> name=&amp;quot;tour:tours&amp;quot;&amp;gt;<br />&amp;lt;xsl:stylesheet&amp;gt;<br /> &amp;lt;xsl:function name=&amp;quot;tour:manufacture-square&amp;quot;<br /> as=&amp;quot;element(square)&amp;quot; visibility=&amp;quot;public&amp;quot;&amp;gt;<br /> &amp;lt;xsl:param name=&amp;quot;rank&amp;quot; as=&amp;quot;xs:integer&amp;quot; /&amp;gt;<br /> &amp;lt;xsl:param name=&amp;quot;file&amp;quot; as=&amp;quot;xs:integer&amp;quot; /&amp;gt;<br /> &amp;lt;square file=&amp;quot;$file&amp;quot; rank=&amp;quot;$rank&amp;quot; /&amp;gt;<br /> &amp;lt;/xsl:function&amp;gt;<br /><br /> &amp;lt;xsl:function name=&amp;quot;tour:on-board&amp;quot; as=&amp;quot;xs:boolean&amp;quot; visibility=&amp;quot;public&amp;quot;&amp;gt;<br /> &amp;lt;xsl:param name=&amp;quot;rank&amp;quot; as=&amp;quot;xs:integer&amp;quot; /&amp;gt;<br /> &amp;lt;xsl:param name=&amp;quot;file&amp;quot; as=&amp;quot;xs:integer&amp;quot; /&amp;gt;<br /> &amp;lt;xsl:copy-of select=&amp;quot;($rank ge 1) and ($rank le 8) and<br /> ($file ge 1) and ($file le 8)&amp;quot; /&amp;gt;<br /> &amp;lt;/xsl:function&amp;gt;<br /><br /> &amp;lt;xsl:function name=&amp;quot;tour:solve-tour&amp;quot; as=&amp;quot;item()*&amp;quot; visibility=&amp;quot;public&amp;quot;&amp;gt;<br /> &amp;lt;!-- Solves the tour for any specified piece. --&amp;gt;<br /> &amp;lt;!-- Outputs either a full solution of 64 squares, of if fail,<br /> a copy of the $state input. --&amp;gt;<br /> &amp;lt;xsl:param name=&amp;quot;state&amp;quot; as=&amp;quot;item()+&amp;quot; /&amp;gt;<br /> &amp;lt;xsl:variable name=&amp;quot;compute-possible-moves&amp;quot;<br /> select=&amp;quot;$state[. instance of function(*)]&amp;quot;<br /> as=&amp;quot;function(element(square)) as element(square)*&amp;quot;&amp;gt;<br /> &amp;lt;xsl:variable name=&amp;quot;way-points&amp;quot; select=&amp;quot;$state/self::square&amp;quot; /&amp;gt;<br /> &amp;lt;xsl:choose&amp;gt;<br /> &amp;lt;xsl:when test=&amp;quot;count($way-points) eq 64&amp;quot;&amp;gt;<br /> &amp;lt;xsl:sequence =&amp;quot;$state&amp;quot; /&amp;gt;<br /> &amp;lt;/xsl:when&amp;gt;<br /> &amp;lt;xsl:otherwise&amp;gt;<br /> &amp;lt;xsl:sequence select=&amp;quot;<br /> let $try-move := function( $state as item()*, $move as item()) as item()*)<br /> {<br /> if $state/self::square[@file=$move/@file]<br /> [@rank=$move/@rank]<br /> then $state<br /> else tour:solve-tour( ( $state, $move) )<br /> },<br /> $possible-moves := $compute-possible-moves( $way-points[last()])<br /> return if empty( $possible-moves) then $state<br /> else fn:fold-left( $try-move, $state, $possible-moves)&amp;quot; /&amp;gt;<br /> &amp;lt;/xsl:otherwise&amp;gt;<br /> &amp;lt;/xsl:choose&amp;gt;<br /> &amp;lt;/xsl:variable&amp;gt;&amp;lt;/xsl:function&amp;gt;<br />&amp;lt;/xsl:stylesheet&amp;gt;<br /><br />&amp;lt;xsl:expose component=&amp;quot;function&amp;quot;<br /> names=&amp;quot;tour:manufacture-square tour:on-board tour:solve-tour&amp;quot;<br /> visibility=&amp;quot;public&amp;quot; /&amp;gt;<br /><br />&amp;lt;/xsl:package&amp;gt;<br />
And now for the style-sheet to solve the Knight’s tour…
&lt;xsl:stylesheet version=&quot;3.0&quot;
xmlns:xsl=&quot;http://www.w3.org/1999/XSL/Transform&quot;
xmlns:xs=&quot;http://www.w3.org/2001/XMLSchema&quot;
xmlns:fn=&quot;http://www.w3.org/2005/xpath-functions&quot;
xmlns:tour=&quot;http://www.seanbdurkin.id.au/tour&quot;
exclude-result-prefixes=&quot;xsl fn xs tour&quot;&gt;
&lt;xsl:use-package name=&quot;tour:tours&quot; /&gt;
&lt;xsl:output indent=&quot;yes&quot; encoding=&quot;UTF-8&quot; omit-xml-declaration=&quot;yes&quot; /&gt;
&lt;xsl:mode on-no-match=&quot;shallow-copy&quot; streamable=&quot;yes&quot;/&gt;
&lt;xsl:template match=&quot;knight[square]&quot;&gt;
&lt;xsl:variable name=&quot;error&quot;&gt;
&lt;error&gt;Failed to find solution to Knight's Tour.&lt;/error&gt;
&lt;/xsl:variable&gt;
&lt;xsl:copy&gt;
&lt;xsl:copy-of select=&quot;
let $final-state := tour:solve-tour((
function( $piece-position as element(square)) as element(square)*
{ (: This function defines a knight's move. :)
let $r0 := number( $piece-position/@rank),
let $f0 := number( $piece-position/@file),
for $r in -2..2, $f in -2..2 return
if (abs($r) + abs($f) eq 3) and
tour:on-board($r+$r0, $f+$f0) then
tour:manufacture-square($r+$r0, $f+$f0)
else ()
}
, current()/square)),
$solution := $final-state/self::square
return if count($solution) eq 64 then $solution
else $error/*&quot; /&gt;
&lt;/xsl:copy&gt;
&lt;/xsl:template&gt;
&lt;!-- Add templates for other piece types if you want to solve
their tours too. Solve by calling tour:solve-tour() . --&gt;
&lt;/xsl:stylesheet&gt;
So an input like this…
&lt;tt&gt; &lt;knight&gt; &lt;square file=&quot;1&quot; rank=&quot;1&quot; /&gt; &lt;/knight&gt; &lt;/tt&gt;
…should be transformed in something like this…
&lt;tt&gt; &lt;knight&gt; &lt;square file=&quot;1&quot; rank=&quot;1&quot; /&gt; &lt;square file=&quot;2&quot; rank=&quot;3&quot; /&gt; &lt;square file=&quot;1&quot; rank=&quot;5&quot; /&gt; ... etc for 64 squares. &lt;/knight&gt; &lt;/tt&gt;
You must be logged in to post a comment.