From: Robert Evans Date: 2006-08-13T15:16:42+09:00 Subject: Re: [QUIZ] Pen and Paper (#90) 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 On Aug 11, 2006, at 5:58 AM, Ruby Quiz wrote: > 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. >