Pen and Paper (#90)

Ruby
#1

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this quiz
    until
    48 hours have passed from the time on this message.

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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.

#2

On Aug 11, 2006, at 7:58 AM, Ruby Q. wrote:

  • 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)

$ time ruby grid_fill.rb -s 6

| 15 8 26 16 7 27 |
| 34 11 5 29 12 22 |
| 25 17 14 9 18 1 |
| 4 30 33 21 6 28 |
| 35 10 24 36 13 23 |

32 20 3 31 19 2

real 0m0.037s
user 0m0.026s
sys 0m0.010s
$ time ruby grid_fill.rb -s 6

| 28 21 3 29 20 4 |
| 11 24 18 6 25 35 |
| 2 30 27 22 31 14 |
| 17 7 10 34 19 5 |
| 12 23 1 13 26 36 |

9 33 16 8 32 15

real 0m0.037s
user 0m0.026s
sys 0m0.010s
$ time ruby grid_fill.rb -s 6

| 19 12 30 20 11 31 |
| 2 15 9 33 16 26 |
| 29 21 18 13 22 5 |
| 8 34 1 25 10 32 |
| 3 14 28 4 17 27 |

36 24 7 35 23 6

real 0m0.037s
user 0m0.026s
sys 0m0.010s

:slight_smile:

James Edward G. II

#3

On Aug 11, 2006, at 2:39 PM, James Edward G. II wrote:

On Aug 11, 2006, at 7:58 AM, Ruby Q. wrote:

  • 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)

[snip: lots of fast filled boards]

Do you by any chance have a background in artificial intelligence?
That’s really impressive how quickly you cranked out a solution to a
problem I can’t yet see a decent strategy for. Hats off to you, my
friend.
-Mat

#4

On Aug 11, 2006, at 2:42 PM, Mat S. wrote:

Do you by any chance have a background in artificial intelligence?
That’s really impressive how quickly you cranked out a solution to
a problem I can’t yet see a decent strategy for. Hats off to you,
my friend.

I bet you are going to be very surprised when I post my pathetic
little toy. If it’s good at anything it’s cheating… :wink:

James Edward G. II

#5

On Aug 11, 2006, at 12:48 PM, James Edward G. II wrote:

[snip: lots of fast filled boards]

Do you by any chance have a background in artificial
intelligence? That’s really impressive how quickly you cranked
out a solution to a problem I can’t yet see a decent strategy
for. Hats off to you, my friend.

I bet you are going to be very surprised when I post my pathetic
little toy. If it’s good at anything it’s cheating… :wink:

I’ve done a similar problem before, years ago called a Knight’s Tour.
You move a knight around a chess board and try to visit each square
once. I’ve seen someone do it live, blindfolded which was pretty
cool. Here’s a brief English description of one technique I used.

MINOR SPOILER WARNING

One simple technique that helped get decent results was to keep track
of how many still-open squares are connected to each square. Then
when choosing what square to visit next, choose the square with the
lowest number of open, connected squares. Corners are only connected
to two others squares at the start (for the knight’s tour). This
makes sure if you move adjacent to a corner, you’ll move to the
corner next, which helps avoid being struck (it’s not strictly always
necessary because you could end in a corner). I can’t remember if it
ever had incomplete runs using just the open square scoring technique
or not.

– Elliot T.

#6

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

James Edward G. II wrote:

On Aug 11, 2006, at 7:58 AM, Ruby Q. wrote:

- 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)

[timings for 6x6 square snipped]

Here’s what I get, although I’m sure we have different hardware. :slight_smile:

[[email protected] j0 s0 ~/src/ruby_quiz]
612$ time ruby -w 90.rb 10

| 17 62 28 18 65 60 48 95 89 79 |
| 6 20 39 7 86 40 75 87 97 76 |
| 27 9 66 61 47 67 88 78 98 91 |
| 16 63 29 19 64 59 49 94 90 80 |
| 5 21 38 8 85 41 74 84 96 77 |
| 26 10 33 23 46 68 53 43 99 92 |
| 15 1 30 12 35 58 50 70 55 81 |
| 4 22 37 3 32 42 73 83 52 72 |
| 25 11 34 24 45 69 54 44 100 93 |
| 14 2 31 13 36 57 51 71 56 82 |

real 0m0.011s
user 0m0.007s
sys 0m0.002s
[[email protected] j0 s0 ~/src/ruby_quiz]
613$ time ruby -w 90.rb 10

| 30 21 8 31 22 54 73 47 87 74 |
| 14 37 93 15 38 94 81 60 95 82 |
| 7 69 46 53 70 45 1 75 88 98 |
| 29 20 9 32 23 55 72 48 84 61 |
| 13 36 92 16 39 91 80 59 96 83 |
| 6 68 41 52 71 44 2 76 89 99 |
| 28 19 10 33 24 56 65 49 85 62 |
| 12 35 26 17 40 51 79 58 97 78 |
| 5 67 42 4 66 43 3 77 90 100 |
| 27 18 11 34 25 57 64 50 86 63 |

real 0m0.011s
user 0m0.009s
sys 0m0.000s
[[email protected] j0 s0 ~/src/ruby_quiz]
614$ time ruby -w 90.rb 10

| 61 19 46 30 20 100 73 64 88 83 |
| 12 36 59 13 37 66 93 81 67 94 |
| 45 29 62 44 74 63 87 75 97 84 |
| 60 18 47 31 21 48 72 65 89 82 |
| 11 35 58 14 38 57 92 80 68 95 |
| 6 28 1 43 25 52 40 76 98 85 |
| 3 17 8 32 22 49 71 54 90 78 |
| 10 34 5 15 39 56 24 51 69 96 |
| 7 27 2 42 26 53 41 77 99 86 |
| 4 16 9 33 23 50 70 55 91 79 |

real 0m0.011s
user 0m0.009s
sys 0m0.000s

:slight_smile:
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE3OsCmV9O7RYnKMcRAnSuAKCJY/JP8i+HSzYFzNSGzcBxkevRygCfQ7jk
BmjqVksuBLsjAJr2cZwRoIw=
=iLJD
-----END PGP SIGNATURE-----

#7

Ruby Q. wrote:

| . 1 4 . 14|
| 6 23 16 5 22|
| 18 10 13 19 9|
| 15 4 7 24 3|

12 20 17 11 21

I know I’m stupid and all that, but I’m not sure there’s enough
explination here for someone who’s never played this game before. Could
you explain the rules of game a little better.

Thanks,
T.

#8

On Aug 11, 2006, at 3:48 PM, James Edward G. II wrote:

[snip: lots of fast filled boards]

Do you by any chance have a background in artificial
intelligence? That’s really impressive how quickly you cranked
out a solution to a problem I can’t yet see a decent strategy
for. Hats off to you, my friend.

I bet you are going to be very surprised when I post my pathetic
little toy. If it’s good at anything it’s cheating… :wink:

$ gem install pen_and_paper --remote
Attempting remote installation of ‘pen_and_paper’
ERROR: While executing gem … (Gem::GemNotFoundException)
Could not find pen_and_paper (> 0) in the repository

Okay, well at least it wasn’t THAT sort of cheating :slight_smile: Can’t wait to
see it!
-Mat

#9

On Aug 11, 2006, at 1:40 PM, Suraj N. Kurapati wrote:

[timings for 6x6 square snipped]

Here’s what I get, although I’m sure we have different hardware. :slight_smile:

Mine did 50x50 in

real 0m0.516s
user 0m0.473s
sys 0m0.013s

on it’s third attempt. it fails sometimes (i guess i could have it
loop and keep trying until it gets a good run). i haven’t written
printing out a pretty board though (using pp is no good over about
15x15, at least with the defaults)

i tried 500x500 a few times and it failed them all. 500x500 should be
easy though, for a smarter algorithm. you could treat it like a bunch
of smaller games with a requirement that you end near a certain edge.

– Elliot T.

#10

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Trans wrote:

Could you explain the rules of game a little better.

  1. Grab a pen and piece of paper.

  2. Draw a 5x5 grid (or table or matrix or whatever you like
    to call it).

  3. Pick a cell or slot, whichever one you like, in the grid.

  4. Write the number “1” in that chosen cell.

  5. Starting from the cell you just marked (with the number "
    1"), travel to a different cell by following these rules:

     a. jump over 2 cells when traveling horizontally or
    vertically

 b. jump over 1 cell when traveling diagonally

  6. Once you have traveled to the new cell, mark it with the
    number “2”.

  7. Starting from the cell you just marked (with the number "
    2"), travel to a different cell by following the rules a.
    and b. shown above.

  8. Once you have traveled to the new cell, mark it with the
    number “3”.

See the pattern? Now you need to travel from the one you
just marked (with the number “3”) to a new cell (which you
will mark with the number “4”). Continue this process until
you have marked all cells in the grid (the last cell will be
marked with the number “25” for a 5x5 grid).

Hope that helps.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE3RCxmV9O7RYnKMcRArNPAJ4/O6aT5q7bAsoPxW/3BR+Vq67SFACeM2GS
kZxiWDHlj5vhODZUgI9b8lg=
=Kpuu
-----END PGP SIGNATURE-----

#11

Elliot T. wrote:

  reasonable amount of time (let's say 48 hours minus scripting

real 0m0.516s
of smaller games with a requirement that you end near a certain edge.

– Elliot T.
http://www.curi.us/blog/
[[email protected] ruby]$ time -p ruby penpaper.rb 10 > /dev/null
real 0.02
user 0.01
sys 0.00
[[email protected] ruby]$ time -p ruby penpaper.rb 50 > /dev/null
real 1.85
user 1.85
sys 0.00
[[email protected] ruby]$ time -p ruby penpaper.rb 100 > /dev/null
real 18.27
user 18.25
sys 0.00
[[email protected] ruby]$ time -p ruby penpaper.rb 200 > /dev/null
real 21.32
user 21.31
sys 0.00
[[email protected] ruby]$ time -p ruby penpaper.rb 300 > /dev/null
real 564.41
user 564.39
sys 0.01

I’m not sure I like where those times are going… :slight_smile:
My script keeps trying until it finds a solution, so keep that in mind
for the timings above.

-Justin

#12

On Aug 11, 2006, at 3:52 PM, Justin C. wrote:

My script keeps trying until it finds a solution, so keep that in
mind for the timings above.

ok i came up with a new approach. it doesn’t have failed runs
anymore. it has a minor restriction on what it can do. i didn’t do
anything to optimize it.

cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 500

real 0m0.650s
user 0m0.586s
sys 0m0.026s
cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 2000

real 0m41.895s
user 0m36.671s
sys 0m0.719s
cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 5000

real 9m26.551s
user 8m11.184s
sys 0m10.997s

– Elliot T.

#13

Elliot T. wrote:

– Elliot T.
http://www.curi.us/blog/

Hmm, I was going to post some new times, but those blow mine away. I’m
still stuck on the nondeterministic approach…looks like you guys are
finding actual methods of solving the game.

Nice!

-Justin

#14

Suraj N. Kurapati wrote:

    b. jump over 1 cell when traveling diagonally

See the pattern? Now you need to travel from the one you
just marked (with the number “3”) to a new cell (which you
will mark with the number “4”). Continue this process until
you have marked all cells in the grid (the last cell will be
marked with the number “25” for a 5x5 grid).

Ah. okay. Consecutive order. That’s what I was missing. Thanks Suraj.

T.

#15

On Aug 11, 2006, at 6:21 PM, Suraj N. Kurapati wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Trans wrote:

Could you explain the rules of game a little better.

This is a great answer. Let me just add one minor point…

1"), travel to a different cell by following these rules:
2"), travel to a different cell by following the rules a.
and b. shown above.

  1. Once you have traveled to the new cell, mark it with the
    number “3”.

See the pattern? Now you need to travel from the one you
just marked (with the number “3”) to a new cell (which you
will mark with the number “4”). Continue this process until
you have marked all cells in the grid (the last cell will be
marked with the number “25” for a 5x5 grid).

If you cannot make a move at any point (using either of the two move
rules), the game is lost.

James Edward G. II

#16

I changed something and got:

cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 4000

real 0m37.412s
user 0m31.385s
sys 0m1.846s
cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 10000

real 10m56.151s
user 9m8.446s
sys 0m30.292s

For 10,000 i saw in Activity Monitor it claimed to be using 1.7 gigs
of real ram, and another 1.7 of virtual at some point near-ish the end.

Elliot

#17

On Aug 12, 2006, at 2:22 PM, Morton G. wrote:

find the first 6 x 6 solution and long did that take?
'Bout 10 seconds (James time, not computer time). Did you read the
quiz? :wink:

James Edward G. II

#18

| 1 30 12 2 29 13 |
| 20 33 27 15 34 8 |
| 11 3 36 31 4 23 |
| 26 16 19 7 28 14 |
| 21 32 10 22 35 9 |

18 6 25 17 5 24

It took a while for the penny to drop. My question is: how did you
find the first 6 x 6 solution and long did that take?

Regards, Morton

#19

You mean your first solution was cut and paste from the quiz posting?
That’s really cheating!
That’s what I did, too, but I was naive enough to believe you wrote a
script that generated at least one solution. :slight_smile:

Regards, Morton

#20

Is it acceptable to roll over the edges to the other side?

I wrote a solution that did, but then I thought perhaps that wasn’t
acceptable.

Bob