# Pen and Paper (#90)

**URL:** <https://www.ruby-forum.com/t/pen-and-paper-90/65315>\
**Category:** Ruby\
**Created:** [August 17, 2006, 2:53pm UTC](https://www.ruby-forum.com/t/pen-and-paper-90/65315 "2006-08-17T14:53:16Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [August 17, 2006, 2:53pm UTC](https://www.ruby-forum.com/t/pen-and-paper-90/65315/1 "2006-08-17T14:53:16Z")

</div>

I enjoyed this problem. It’s fun to play with and gives you a little  
room to  
get creative with solving techniques.

As many people pointed out, this is pretty much the Knight’s Tour  
problem with  
some unusual Knight jumps. Most solutions will solve either problem, if  
you  
change their idea of neighbor squares. The good news about that is that  
we can  
take advantage of the shortcuts people use to solve that problem.

The most straightforward solution to this problem is I can dream up is:

```
1. Pick a random starting square
2. Make a list of all the possible moves from the current square
3. If there are no moves, undo the last move and try the next choice
    from that square
4. Otherwise, make the first move in the list
5. Goto step 2 until the grid is full

```

That’s a boring brute force approach, which is the computer science term  
for  
“try everything until something works.” When it gets stuck somewhere,  
it  
backtracks and tries another jump. It may, at times, need to backtrack  
several  
steps to get back to a place where it could try another move.

This approach has one major plus and one major minus. First, the good  
news: it  
will find a solution. The bad news: eventually. Because it has to  
check every  
possibility, it can take a good long while to find a path that works.  
The  
bigger the board gets, the more places it has to check. The waits get  
longer  
and longer.

Now, when solving the Knight’s Tour there is a common shortcut that  
often leads  
to a solution much faster. Luckily it works here too. The idea is  
that, you  
should visit the squares with the least choices first. Those are the  
places you  
are likely to run out of options, so getting them out of the way while  
you still  
have plenty of open squares increases your chances of making it around  
the  
board. This is called the JC Warnsdorff heuristic, because JC  
Warnsdorff made  
the suggestion all the way back in 1823.

The downside of the JC Warnsdorff heuristic is that is doesn’t always  
work.  
Depending on your starting position and which squares you visit first,  
it can  
paint itself into a corner. The problem is more common on certain board  
sizes,  
but it does happen. The upside is, it’s so darn quick (because it  
doesn’t  
backtrack), you can do multiple searches and still be quicker than the  
brute  
force approach. If one attempt fails, just try again. Most solutions  
used this  
approach.

I found one more corner to cut. When the quiz mentioned circular  
solutions, it  
made me realize you could cheat a bit, if you had one. If you can go  
from the  
end of the line back to the beginning (the definition of a circular  
solution),  
you can start anywhere on that path and follow it for the entire length  
to get  
all the numbers out. In truth, these are all the same solution (in my  
opinion),  
but the numbers move around so they look different. It’s also lightning  
quick  
to shift all the numbers by some offset. Sadly it can be pretty slow to  
find a  
circular solution in the first place. It’s a trade off.

Another technique, subdividing the grid and piecing together multiple  
smaller  
solutions, was used be Elliot T… See the later postings in the  
quiz thread  
for a good discussion of that approach.

OK, let’s get to the code already!

I’m going to so show my solution, just because it takes both shortcuts  
and I’m  
very familiar with how it works. I do not think my solution came out  
the  
cleanest though, so definitely go through the others to find some pretty  
code.  
Here’s the beginning of my solution:

```
#!/usr/bin/env ruby -w

require "enumerator"

class PenAndPaperGame
  def self.circular_solutions
    @circular ||= if File.exist?("circular_solutions.dump")
      File.open("circular_solutions.dump") { |file| Marshal.load(file) 

```

}  
else  
Array.new  
end  
end

```
  def initialize(size)
    @size = size
    @largest = @size * @size

    @grid = Array.new(@largest)
  end

  # ...

```

I pull in enumerator here, because I’m addicted. Can’t wait until that  
library  
is in the core.

The class method here is my persistent memory for circular solutions.  
It reads  
the data file, if it exists, and creates an Array of circular solutions  
at  
various sizes. If we don’t have the file, a new Array is used. The ||=  
caching  
operator is used for the assignment so we only look the value up once.

The constructor is trivial and almost every solution had one just like  
it. We  
record the size, figure out what the largest number needs to be, and  
build the  
grid Array.

The Array was a dumb choice on my part. It somehow made me feel more  
manly to  
use a one dimensional Array and deal with the two dimensional indexing.  
However, looking at David T.s super clear 45 line solution that uses  
normal  
nested Arrays just made me feel dumb.

Here’s the cheat solver I described earlier:

```
# ...

def solve
  if self.class.circular_solutions[@size].nil?
    solve_manually
  else
    @grid = self.class.circular_solutions[@size]
    offset = @grid[rand(@grid.size)]
    @grid.map! { |n| (n + offset) % @largest + 1 }
    to_s
  end
end

# ...

```

If we haven’t yet found a circular solution for this size, a handoff is  
made to  
solve\_manually(). If we do have one, the else clause is a full  
(cheating)  
solution. We set the grid to the complete solution, choose a random  
value from  
the grid (similar to picking a starting square), adjust all the values  
in the  
grid by the chosen starting point, and print the results.

Now that we’ve looked at my super cheat, let’s get to a real solution:

```
# ...

def solve_manually
  x, y = rand(@size), rand(@size)
  count = mark(x, y)

  loop do
    to = jumps(x, y)
    return self.class.new(@size).solve_manually if to.empty?

    scores = rate_jumps(to)
    low = scores.min
    next_jump = to.enum_for(:each_with_index).select do |jump|
      scores[jump.last] == low
    end.sort_by { rand }.first.first

    count = mark(*(next_jump + [count]))
    x, y = next_jump

    if count > @largest
      if circular?
        self.class.circular_solutions[@size] = @grid
        File.open("circular_solutions.dump", "w") do |file|
          Marshal.dump(self.class.circular_solutions, file)
        end
        return to_s
      else
        puts "Found this solution:"
        puts to_s
        puts "Continuing search for a circular solution..."
        return self.class.new(@size).solve_manually
      end
    end
  end
end

# ...

```

This method looks big, but hopefully it’s fairly high level and thus  
easy enough  
to read. First, we select a random starting x and y and mark() that  
square.  
Then we dive into the main solution loop.

In the loop, we pull all possible jumps() from this square and make sure  
we have  
at least one choice. If we don’t, we got stuck and can’t find a  
solution so we  
just build a new solver, trigger the search for another attempt, and  
return the  
results of that.

If we did get some jumps, we need to score them, based on how many moves  
we  
would have from there. The call to rate\_jumps() does this. Then we  
pluck out  
the low score as our target move. The complicated ball of iterators  
right after  
that is just a lazy way to select a random move from all the choices  
matching  
the lowest score, which gets slotted into next\_jump.

With a jump selected we mark the new square and move.

Before we loop(), we check to see if that was the final mark. When it  
is, we  
have a solution, but we want to check if it’s a circular solution we  
could reuse  
for cheating. If it is circular, we add it to the collection and update  
our  
storage file. Then we show the solution. When it’s not circular, we go  
ahead  
and show it, but trigger another search to see if we can hunt down a  
circular  
solution.

Here’s the printing code:

```
# ...

def to_s
  width = @largest.to_s.size
  border = " -" + (["-" * width] * @size).join("-") + "- \n"

  border +
  @grid.enum_for(:each_slice, @size).inject(String.new) do |grid, row|
    grid + "| " + row.map { |n| n.to_s.center(width) }.join(" ") + " 

```

|\n"  
end +  
border  
end

```
# ...

```

Nothing too tricky here. We find a cell size and build a border. Then  
we print  
a border, each row, and another border. The complicated row iteration  
is just  
another sign that I used the wrong Array.

Here are the missing helper methods:

```
  # ...

  private

  def at(x, y)
    x + y * @size
  end

  def mark(current_x, current_y, mark = 1)
    @grid[at(current_x, current_y)] = mark
    mark + 1
  end

  def jumps(from_x, from_y, grid = @grid)
    [[-3, 0],
      [3, 0],
      [0, -3],
      [0, 3],
      [2, 2],
      [-2, 2],
      [2, -2],
      [-2, -2] ].map do |jump|
      [from_x + jump.first, from_y + jump.last]
    end.select do |jump|
      jump.all? { |to| (0...@size).include? to } and 

```

grid[at(\*jump)].nil?  
end  
end

```
  def rate_jumps(choices)
    choices.map { |jump| jumps(*jump).size }
  end

  def circular?
    grid = @grid.dup
    grid[grid.index(@largest)] = nil

    x, y = grid.index(1).divmod(@size).reverse

    not jumps(x, y, grid).empty?
  end
end

# ...

```

The at() method is used to turn x and y coordinates into an index for  
the one  
dimensional grid I am using. mark() will place a number in the  
indicated square  
and return the next mark that should be placed. (This was another odd  
choice.  
I have no idea why I didn’t use an instance variable here.)

The jumps() method uses offset to locate all possible moves from the  
current  
location. It then filters those by removing any out-of-bound indices  
and any  
squares that aren’t nil. rate\_jumps() is just a thin shell over jumps  
to count  
the moves available at each step.

The circular?() check duplicates the solved grid, knocks the last move  
back to  
nil, locates the starting square, and checks to see if the starting  
square now  
has one jump (to the only nil square).

Using those pieces, here’s the application code:

```
# ...

if __FILE__ == $PROGRAM_NAME
  size = ARGV.first && ARGV.first =~ /\A-s(?:ize)?\Z/ ? ARGV.last.to_i 

```

: 5  
puts PenAndPaperGame.new(size).solve  
end

That just reads the size parameter or sets the default to 5 and kicks  
off the  
solver process.

A big thank you to all those who were so creative with their solutions  
this time  
around. You guys taught me how to finish off my own solution.

Tomorrow we will play around with interactively defining Ruby methods…

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [August 17, 2006, 4:26pm UTC](https://www.ruby-forum.com/t/pen-and-paper-90/65315/2 "2006-08-17T16:26:25Z")

</div>

On Aug 17, 2006, at 8:51 AM, Ruby Q. wrote:

> board. This is called the JC Warnsdorff heuristic, because JC  
> Warnsdorff made  
> the suggestion all the way back in 1823.

So what I was calling the one-step look-ahead is properly called the  
JC Warnsdorff heuristic. I’m glad to learn that.

> force approach. If one attempt fails, just try again. Most  
> solutions used this  
> approach.

Re: … because it doesn’t backtrack …

The heuristic can be used to improve a backtracking solver. The  
interesting question is whether backtracking is ever better than  
restarting. I think there are such situations. One might write a  
solver that tries backtracking a little first and then does a restart  
as Plan B. Of course, one would have to make a precise definition of  
what “a little” means 😉

Regards, Morton

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [August 17, 2006, 9:00pm UTC](https://www.ruby-forum.com/t/pen-and-paper-90/65315/3 "2006-08-17T21:00:09Z")

</div>

On Aug 17, 2006, at 9:23 AM, Morton G. wrote:

> > force approach. If one attempt fails, just try again. Most  
> > solutions used this  
> > approach.
> 
> Re: … because it doesn’t backtrack …
> 
> The heuristic can be used to improve a backtracking solver.

That’s a good point. David T.'s solution does both.

James Edward G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [August 18, 2006, 3:06am UTC](https://www.ruby-forum.com/t/pen-and-paper-90/65315/4 "2006-08-18T03:06:42Z")

</div>

Just one last minor point. A Google search on Warnsdorff revealed  
that it’s HC Warnsdorff, not JC, and that its usually referred to as  
the Warnsdorff rule, not Warnsdorff heuristic. The latter is probably  
because “rule” is a lot easier to type than “heuristic” 😃

Regards, Morton

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [August 18, 2006, 10:46am UTC](https://www.ruby-forum.com/t/pen-and-paper-90/65315/5 "2006-08-18T10:46:56Z")

</div>

On 8/18/06, James Edward G. II [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> On Aug 17, 2006, at 8:05 PM, Morton G. wrote:
> 
> > Just one last minor point. A Google search on Warnsdorff revealed  
> > that it’s HC Warnsdorff, not JC

This is a wild shot but the H and the J keys are quite close on the  
keyboard. HC gets 299 hits and JC only 113.  
Now what intrigues me is that I could not find what  
[H_299/412,J_113/412]  
means. So I guess as a native speaker that  
HC means Hans Conrad or something similar, but I cannot rule out JC ☹

Interesting. It seems to appear both ways:

> I choose to call it a heuristic because I defined those in last  
> week’s summary. I thought it would be good for the regular readership.
> 
> James Edward G. II

–  
Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui  
concerne l’univers, je n’en ai pas acquis la certitude absolue.

- Albert Einstein

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [August 18, 2006, 10:52am UTC](https://www.ruby-forum.com/t/pen-and-paper-90/65315/6 "2006-08-18T10:52:57Z")

</div>

First post, then think. ☹

But just to tell you it is HC.

My proof goes here  
[http://www.google.fr/search?hl=fr&client=firefox-a&rls=org.mozilla%3Aen-US%3Aofficial&q=Des+Rösselsprungs+einfachste+und+allgemeinste+Lösung+jc&btnG=Rechercher&meta=](http://www.google.fr/search?hl=fr&client=firefox-a&rls=org.mozilla%3Aen-US%3Aofficial&q=Des+R%C3%B6sselsprungs+einfachste+und+allgemeinste+L%C3%B6sung+jc&btnG=Rechercher&meta=)  
No hits  
but  
[http://www.google.fr/search?hl=fr&client=firefox-a&rls=org.mozilla%3Aen-US%3Aofficial&q=Des+Rösselsprungs+einfachste+und+allgemeinste+Lösung+hc&btnG=Rechercher&meta=](http://www.google.fr/search?hl=fr&client=firefox-a&rls=org.mozilla%3Aen-US%3Aofficial&q=Des+R%C3%B6sselsprungs+einfachste+und+allgemeinste+L%C3%B6sung+hc&btnG=Rechercher&meta=)  
64 hits (can you believe it 64 hits for the Warnsdorff algorithm, that  
is  
really NICE!!!).

Cheers  
Robert

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [August 18, 2006, 5:40am UTC](https://www.ruby-forum.com/t/pen-and-paper-90/65315/7 "2006-08-18T05:40:26Z")

</div>

On Aug 17, 2006, at 8:05 PM, Morton G. wrote:

> Just one last minor point. A Google search on Warnsdorff revealed  
> that it’s HC Warnsdorff, not JC

Interesting. It seems to appear both ways:

[JC Warnsdorff - Google Search](http://www.google.com/search?q=JC+Warnsdorff)

> and that its usually referred to as the Warnsdorff rule, not  
> Warnsdorff heuristic. The latter is probably because “rule” is a  
> lot easier to type than “heuristic” 😃

I imagine it’s because it was stated before computer’s existed to  
make heuristic a popular term. 😉

I choose to call it a heuristic because I defined those in last  
week’s summary. I thought it would be good for the regular readership.

James Edward G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [August 18, 2006, 9:27pm UTC](https://www.ruby-forum.com/t/pen-and-paper-90/65315/8 "2006-08-18T21:27:18Z")

</div>

On Aug 17, 2006, at 10:23 AM, Morton G. wrote:

> One might write a solver that tries backtracking a little first and  
> then does a restart as Plan B. Of course, one would have to make a  
> precise definition of what “a little” means 😉

I have implemented such a program, one which applies the Warnsdorff  
rule starting from a random position and which allows backtracking to  
be turned on or off. I find the results convincing – backtracking  
does have value even when the Warnsdorff rule is used, especially  
when a cyclic solution is wanted.

17x17 grid – cyclic solution required – average of 5 runs for each  
case

no backtracking: 10.2562504 sec  
with backtracking: 1.1582514 sec

I appologize if I’m being a bore on this subject, but I hope at least  
a few people will be interested in this result.

Regards, Morton

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [August 18, 2006, 4:08pm UTC](https://www.ruby-forum.com/t/pen-and-paper-90/65315/9 "2006-08-18T16:08:34Z")

</div>

On Aug 18, 2006, at 3:51 AM, Robert D. wrote:

> But just to tell you it is HC.

Thanks for looking into this. I’ve updated the summary.

James Edward G. II