by Eric DUMINIL
Some classmates and I used to play a lot of pen and paper games while sitting in the last row of the classroom. My favorite game was this one.
We had to fill a 5x5 board as fast as possible with numbers from 1 to 25, beginning at a random position and then going from one square to another:
- jumping over 2 squares when traveling horizontally or vertically
- jumping over 1 square when traveling diagonally.
Here is an example with numbers from 1 to 14 (it would be impossible to keep on filling the board, since 1, 13, and 8 are blocking the way):
-------------------
| . 1 4 . 14|
| 10 . . 11 6|
| 3 . 8 2 .|
| . 12 5 . 13|
| 9 . . . 7|
-------------------
Here is a completed 5x5 board:
-------------------
| 14 1 8 25 2|
| 6 23 16 5 22|
| 18 10 13 19 9|
| 15 4 7 24 3|
| 12 20 17 11 21|
-------------------
Though this game is impossible with 2x2, 3x3 or 4x4 boards, it appears that NxN boards can be filled when N>4 (or n=1). For example, 6x6:
-----------------------
| 33 21 10 32 35 11|
| 16 26 5 13 25 6|
| 9 31 34 22 30 1|
| 4 20 17 27 36 12|
| 15 23 8 14 24 7|
| 18 28 3 19 29 2|
-----------------------
7x7:
---------------------------
| 46 33 26 8 32 35 9|
| 17 14 5 37 15 6 38|
| 27 22 47 34 25 48 31|
| 45 42 16 7 43 36 10|
| 18 13 4 21 12 3 39|
| 28 23 44 29 24 49 30|
| 1 41 19 2 40 20 11|
---------------------------
Here comes the quiz!
- Write a ruby script that fills a board (with a given NxN size)
as fast as possible
- Try to fill the biggest board you can with this script, in a
reasonable amount of time (let's say 48 hours minus scripting time)
You get extra points for:
- Finding more about this game (name, origin, related articles)
- Filling a 5x5 board with only pen and paper
- Filling a bigger board with only pen and paper
- Finding the worst attempt possible for a given size. For example,
getting stuck after 10 steps on a 5x5 board is pretty bad:
-------------------
| . 6 3 . 7|
| . . 9 . .|
| 4 1 . 5 2|
| . . . . 8|
| . . 10 . .|
-------------------
- Filling a board with a cycle pattern, i.e. where you can jump from
the last square to the first square:
-------------------
| 22 10 7 23 11|
| 14 19 4 1 16|
| 8 24 12 9 6|
| 21 2 15 20 3|
| 13 18 5 25 17|
-------------------
-----------------------
| 16 9 27 17 8 28|
| 35 12 6 30 13 23|
| 26 18 15 10 19 2|
| 5 31 34 22 7 29|
| 36 11 25 1 14 24|
| 33 21 4 32 20 3|
-----------------------
I can't wait to look at your solutions!
I daresay that brute-forcing won't help you much (it took me 98,268,583 attempts and 4 days on a decent computer to fill a 10x10 board) but I don't know many other ways to fill a board.
Have fun with this quiz.
Quiz Summary
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 HC Warnsdorff heuristic, because HC Warnsdorff made the suggestion all the way back in 1823.
The downside of the HC 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 Temple. 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:
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 Trans 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...
