{"id":10,"date":"2012-10-31T14:17:02","date_gmt":"2012-10-31T14:17:02","guid":{"rendered":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/?p=10"},"modified":"2025-08-12T16:11:01","modified_gmt":"2025-08-12T06:11:01","slug":"what-the-knights-tour-might-look-like-in-xslt-3-0","status":"publish","type":"post","link":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/archives\/10","title":{"rendered":"What the Knight’s Tour might look like in XSLT 3.0?"},"content":{"rendered":"\n

At the time of writing XSL Transformations (XSLT) Version 3.0 (W3C Working Draft 10 July 2012)<\/a> 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<\/p>\n\n\n\n

First we build a generic package for solving any kind of tour over the chess board. Here it is…
(Updated 31-Oct-2012)<\/em><\/p>\n\n\n\n

<br \/>&lt;xsl:package xsl:version="3.0"<br \/>  xmlns:xsl=&amp;amp;quot;http:\/\/www.w3.org\/1999\/XSL\/Transform&amp;amp;quot;<br \/>  xmlns:xs=&amp;amp;quot;http:\/\/www.w3.org\/2001\/XMLSchema&amp;amp;quot;<br \/>  xmlns:fn=&amp;amp;quot;http:\/\/www.w3.org\/2005\/xpath-functions&amp;amp;quot;<br \/>  xmlns:tour=&amp;amp;quot;http:\/\/www.seanbdurkin.id.au\/tour&amp;amp;quot;<br \/>  name=&amp;amp;quot;tour:tours&amp;amp;quot;&amp;amp;gt;<br \/>&amp;amp;lt;xsl:stylesheet&amp;amp;gt;<br \/>  &amp;amp;lt;xsl:function name=&amp;amp;quot;tour:manufacture-square&amp;amp;quot;<br \/>       as=&amp;amp;quot;element(square)&amp;amp;quot; visibility=&amp;amp;quot;public&amp;amp;quot;&amp;amp;gt;<br \/>    &amp;amp;lt;xsl:param name=&amp;amp;quot;rank&amp;amp;quot; as=&amp;amp;quot;xs:integer&amp;amp;quot; \/&amp;amp;gt;<br \/>    &amp;amp;lt;xsl:param name=&amp;amp;quot;file&amp;amp;quot; as=&amp;amp;quot;xs:integer&amp;amp;quot; \/&amp;amp;gt;<br \/>    &amp;amp;lt;square file=&amp;amp;quot;$file&amp;amp;quot; rank=&amp;amp;quot;$rank&amp;amp;quot; \/&amp;amp;gt;<br \/>  &amp;amp;lt;\/xsl:function&amp;amp;gt;<br \/><br \/>  &amp;amp;lt;xsl:function name=&amp;amp;quot;tour:on-board&amp;amp;quot; as=&amp;amp;quot;xs:boolean&amp;amp;quot; visibility=&amp;amp;quot;public&amp;amp;quot;&amp;amp;gt;<br \/>    &amp;amp;lt;xsl:param name=&amp;amp;quot;rank&amp;amp;quot; as=&amp;amp;quot;xs:integer&amp;amp;quot; \/&amp;amp;gt;<br \/>    &amp;amp;lt;xsl:param name=&amp;amp;quot;file&amp;amp;quot; as=&amp;amp;quot;xs:integer&amp;amp;quot; \/&amp;amp;gt;<br \/>    &amp;amp;lt;xsl:copy-of select=&amp;amp;quot;($rank ge 1) and ($rank le 8) and<br \/>                         ($file ge 1) and ($file le 8)&amp;amp;quot; \/&amp;amp;gt;<br \/>  &amp;amp;lt;\/xsl:function&amp;amp;gt;<br \/><br \/>  &amp;amp;lt;xsl:function name=&amp;amp;quot;tour:solve-tour&amp;amp;quot; as=&amp;amp;quot;item()*&amp;amp;quot; visibility=&amp;amp;quot;public&amp;amp;quot;&amp;amp;gt;<br \/>    &amp;amp;lt;!-- Solves the tour for any specified piece. --&amp;amp;gt;<br \/>    &amp;amp;lt;!-- Outputs either a full solution of 64 squares, of if fail,<br \/>         a copy of the $state input. --&amp;amp;gt;<br \/>    &amp;amp;lt;xsl:param name=&amp;amp;quot;state&amp;amp;quot; as=&amp;amp;quot;item()+&amp;amp;quot; \/&amp;amp;gt;<br \/>    &amp;amp;lt;xsl:variable name=&amp;amp;quot;compute-possible-moves&amp;amp;quot;<br \/>      select=&amp;amp;quot;$state[. instance of function(*)]&amp;amp;quot;<br \/>\t  as=&amp;amp;quot;function(element(square)) as element(square)*&amp;amp;quot;&amp;amp;gt;<br \/>    &amp;amp;lt;xsl:variable name=&amp;amp;quot;way-points&amp;amp;quot; select=&amp;amp;quot;$state\/self::square&amp;amp;quot; \/&amp;amp;gt;<br \/>    &amp;amp;lt;xsl:choose&amp;amp;gt;<br \/>      &amp;amp;lt;xsl:when test=&amp;amp;quot;count($way-points) eq 64&amp;amp;quot;&amp;amp;gt;<br \/>        &amp;amp;lt;xsl:sequence =&amp;amp;quot;$state&amp;amp;quot; \/&amp;amp;gt;<br \/>      &amp;amp;lt;\/xsl:when&amp;amp;gt;<br \/>      &amp;amp;lt;xsl:otherwise&amp;amp;gt;<br \/>        &amp;amp;lt;xsl:sequence select=&amp;amp;quot;<br \/>\t  let $try-move := function( $state as item()*, $move as item()) as item()*)<br \/>\t        {<br \/>\t         if $state\/self::square[@file=$move\/@file]<br \/>\t                               [@rank=$move\/@rank]<br \/>\t           then $state<br \/>\t           else tour:solve-tour( ( $state, $move) )<br \/>                },<br \/>              $possible-moves := $compute-possible-moves( $way-points[last()])<br \/>\t      return if empty( $possible-moves) then $state<br \/>                     else fn:fold-left( $try-move, $state, $possible-moves)&amp;amp;quot; \/&amp;amp;gt;<br \/>      &amp;amp;lt;\/xsl:otherwise&amp;amp;gt;<br \/>    &amp;amp;lt;\/xsl:choose&amp;amp;gt;<br \/>  &amp;amp;lt;\/xsl:variable&amp;amp;gt;&amp;amp;lt;\/xsl:function&amp;amp;gt;<br \/>&amp;amp;lt;\/xsl:stylesheet&amp;amp;gt;<br \/><br \/>&amp;amp;lt;xsl:expose component=&amp;amp;quot;function&amp;amp;quot;<br \/>  names=&amp;amp;quot;tour:manufacture-square tour:on-board tour:solve-tour&amp;amp;quot;<br \/>  visibility=&amp;amp;quot;public&amp;amp;quot; \/&amp;amp;gt;<br \/><br \/>&amp;amp;lt;\/xsl:package&amp;amp;gt;<br \/><\/pre><\/pre>\n\n\n
\n
\"The<\/a><\/figure>\n<\/div>\n\n\n
And now for the style-sheet to solve the Knight’s tour…<\/strong>
<\/p>\n\n\n\n
\n&amp;lt;xsl:stylesheet version=&amp;quot;3.0&amp;quot;\n  xmlns:xsl=&amp;quot;http:\/\/www.w3.org\/1999\/XSL\/Transform&amp;quot;\n  xmlns:xs=&amp;quot;http:\/\/www.w3.org\/2001\/XMLSchema&amp;quot;\n  xmlns:fn=&amp;quot;http:\/\/www.w3.org\/2005\/xpath-functions&amp;quot;\n  xmlns:tour=&amp;quot;http:\/\/www.seanbdurkin.id.au\/tour&amp;quot;\n  exclude-result-prefixes=&amp;quot;xsl fn xs tour&amp;quot;&amp;gt;\n&amp;lt;xsl:use-package name=&amp;quot;tour:tours&amp;quot; \/&amp;gt;\n&amp;lt;xsl:output indent=&amp;quot;yes&amp;quot; encoding=&amp;quot;UTF-8&amp;quot; omit-xml-declaration=&amp;quot;yes&amp;quot; \/&amp;gt;\n&amp;lt;xsl:mode on-no-match=&amp;quot;shallow-copy&amp;quot; streamable=&amp;quot;yes&amp;quot;\/&amp;gt;\n\n&amp;lt;xsl:template match=&amp;quot;knight[square]&amp;quot;&amp;gt;\n  &amp;lt;xsl:variable name=&amp;quot;error&amp;quot;&amp;gt;\n    &amp;lt;error&amp;gt;Failed to find solution to Knight's Tour.&amp;lt;\/error&amp;gt;\n  &amp;lt;\/xsl:variable&amp;gt;\n  &amp;lt;xsl:copy&amp;gt;\n    &amp;lt;xsl:copy-of select=&amp;quot;\n    let $final-state := tour:solve-tour((\n    function( $piece-position as element(square)) as element(square)*\n      { (: This function defines a knight's move. :)\n\t    let $r0 := number( $piece-position\/@rank),\n\t    let $f0 := number( $piece-position\/@file),\n\t    for $r in -2..2, $f in -2..2 return\n\t\t  if (abs($r) + abs($f) eq 3) and\n\t\t     tour:on-board($r+$r0, $f+$f0) then\n\t\t    tour:manufacture-square($r+$r0, $f+$f0)\n\t      else ()\n\t  }\n      , current()\/square)),\n     $solution := $final-state\/self::square\n    return if count($solution) eq 64 then $solution\n           else $error\/*&amp;quot; \/&amp;gt;\n  &amp;lt;\/xsl:copy&amp;gt;\n&amp;lt;\/xsl:template&amp;gt;\n\n&amp;lt;!-- Add templates for other piece types if you want to solve\n     their tours too. Solve by calling tour:solve-tour() .    --&amp;gt;\n\n&amp;lt;\/xsl:stylesheet&amp;gt;\n<\/pre><\/pre>\n\n\n\n
So an input like this…<\/p>\n\n\n\n
\n&amp;lt;tt&amp;gt;\n &amp;lt;knight&amp;gt;\n   &amp;lt;square file=&amp;quot;1&amp;quot; rank=&amp;quot;1&amp;quot; \/&amp;gt;\n &amp;lt;\/knight&amp;gt;\n&amp;lt;\/tt&amp;gt;\n<\/pre><\/pre>\n\n\n\n
…should be transformed in something like this…<\/p>\n\n\n\n
\n&amp;lt;tt&amp;gt;\n &amp;lt;knight&amp;gt;\n   &amp;lt;square file=&amp;quot;1&amp;quot; rank=&amp;quot;1&amp;quot; \/&amp;gt;\n   &amp;lt;square file=&amp;quot;2&amp;quot; rank=&amp;quot;3&amp;quot; \/&amp;gt;\n   &amp;lt;square file=&amp;quot;1&amp;quot; rank=&amp;quot;5&amp;quot; \/&amp;gt;\n   ... etc for 64 squares.\n &amp;lt;\/knight&amp;gt;\n&amp;lt;\/tt&amp;gt;\n<\/pre><\/pre>\n","protected":false},"excerpt":{"rendered":"
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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":19,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[3],"tags":[4,13],"class_list":["post-10","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-xslt-3-0","tag-knights-tour","tag-xslt-3-0"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/seanbdurkin.id.au\/pascaliburnus2\/wp-content\/uploads\/2012\/10\/knightstour1.jpg?fit=224%2C225","jetpack_shortlink":"https:\/\/wp.me\/p2QXbt-a","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/posts\/10","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/comments?post=10"}],"version-history":[{"count":29,"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/posts\/10\/revisions"}],"predecessor-version":[{"id":405,"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/posts\/10\/revisions\/405"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/media\/19"}],"wp:attachment":[{"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/media?parent=10"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/categories?post=10"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/seanbdurkin.id.au\/pascaliburnus2\/wp-json\/wp\/v2\/tags?post=10"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}