<story><title>Show HN: Solving Rush Hour, the 6x6 Sliding Block Puzzle</title><url>https://www.michaelfogleman.com/rush/</url></story><parent_chain></parent_chain><comment><author>tromp</author><text>Many years ago I investigated [1] the problem of Rush Hour with minimal size cars. I called it Unit Rush Hour, as the cars are just 1x1, but restricted to either horizontal or vertical movement. Interestingly, the puzzles can also be viewed as a kind of maze with restricted movement. My web page has the hardest 4x4 and 5x5 instances in playable form.
I found the hardest 6x6 puzzle to require a whopping 732 steps [2].&lt;p&gt;[1] &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;tromp.github.io&amp;#x2F;orimaze.html&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;tromp.github.io&amp;#x2F;orimaze.html&lt;/a&gt;&lt;p&gt;[2] &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;tromp.github.io&amp;#x2F;rh.ps&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;tromp.github.io&amp;#x2F;rh.ps&lt;/a&gt;</text></comment>
<story><title>Show HN: Solving Rush Hour, the 6x6 Sliding Block Puzzle</title><url>https://www.michaelfogleman.com/rush/</url></story><parent_chain></parent_chain><comment><author>losvedir</author><text>Very cool!&lt;p&gt;I&amp;#x27;m interested in the &amp;quot;hardest&amp;quot; 6x6 puzzle. You show the one that takes the most moves to complete, but I don&amp;#x27;t think that&amp;#x27;s necessarily very difficult, if they&amp;#x27;re all pretty straightforward. Rather, I think the hardest puzzle is one where you have a lot of options to choose from. IOW, a very broad tree, rather than a very deep one. Are you able to quantify the hardest puzzle along those lines somehow?</text></comment>