[QUIZ] Pen and Paper (#90)

[Ruby Quiz]

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk 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.

 

[James Edward Gray II]

- 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



James Edward Gray II

 

[Mat Schaffer]

- 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

 

[James Edward Gray II]

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

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

James Edward Gray II

 

[Mat Schaffer]

On Aug 11, 2006, at 7:58 AM, Ruby Quiz 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.

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

$ 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 Can't wait to
see it!
-Mat

 

[Elliot Temple]

On Aug 11, 2006, at 7:58 AM, Ruby Quiz 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.

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

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 Temple
http://www.curi.us/blog/

 

[Suraj N. Kurapati]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
[timings for 6x6 square snipped]

Here's what I get, although I'm sure we have different hardware.

[sun@yantram 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
[sun@yantram 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
[sun@yantram 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


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

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

 

[Trans]

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk 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|
-------------------

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.

 

[Elliot Temple]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
[timings for 6x6 square snipped]

Here's what I get, although I'm sure we have different hardware.

<timings snipped>

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 Temple
http://www.curi.us/blog/

 

[Justin Collins]

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

On Aug 11, 2006, at 7:58 AM, Ruby Quiz 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.

<timings snipped>

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 Temple
http://www.curi.us/blog/

[justin@cheese ruby]$ time -p ruby penpaper.rb 10 > /dev/null
real 0.02
user 0.01
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 50 > /dev/null
real 1.85
user 1.85
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 100 > /dev/null
real 18.27
user 18.25
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 200 > /dev/null
real 21.32
user 21.31
sys 0.00
[justin@cheese 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...
My script keeps trying until it finds a solution, so keep that in mind
for the timings above.

-Justin

 

[Suraj N. Kurapati]

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

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

 

[Elliot Temple]

[justin@cheese ruby]$ time -p ruby penpaper.rb 200 > /dev/null
real 21.32
user 21.31
sys 0.00
[justin@cheese 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...
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 Temple
http://www.curi.us/blog/

 

[Justin Collins]

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

 

[James Edward Gray II]

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

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

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

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

James Edward Gray II

 

[Trans]

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


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

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

T.

 

[Elliot Temple]

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

 

[Morton Goldberg]

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

 

[James Edward Gray II]

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

'Bout 10 seconds (James time, not computer time). Did you read the
quiz?

James Edward Gray II

 

[Morton Goldberg]

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.

Regards, Morton

 

[James Edward Gray II]

You mean your first solution was cut and paste from the quiz
posting? That's really cheating!
That's what I did, too

You're cracking me up.

In all fairness, I really would love to go back and add the solver,
but I am very, very busy this weekend. We will see if I can
steal the time.

I bet we're about to see some solvers tomorrow though...

but I was naive enough to believe you wrote a script that generated
at least one solution.

The quiz said to build a solution that goes as fast as possible.
Then it gave me an idea for a hell of a shortcut. I couldn't
resist.

James Edward Gray II