Annoying problem, the edge cases for small solutions are killing me.

Anyway sufficiently big grids ( $R,$C >4 )are easily constructed

In the following for simplicity we assume $R >= $C (otherwise just swap the result).

First starting form 0/0 you do $R knight moves (+1,+2) module $C till each row was visited.

It's obvious that successive moves can't collide here.

- (5,4) --------------------

  1   0   0   0 

  0   0   2   0 

  3   0   0   0 

  0   0   4   0 

  5   0   0   0
[download]

Now we have a pattern which can be moved horizontally by a value $shift.

That is point p6 = (r6,c6) = (r1, c1 + $shift)

For $shift= 1 this results in

- (5,4) --------------------

  1   6' 11  16 

 12  17   2   7' 

  3   8' 13  18 

 14  19   4   9' 

  5  10' 15  20
[download]

and it's obvious that a shifted group like p6..p10 can't collide because the original pattern in p1..p5 didn't.

The only possible collision happen between the last element of a group and the first of the following, i.e p5 -> p6 are not allowed to be on the same column, to avoid vertical collision

Diagonal and horizontal collision can't happen, since we supposed $R > $C, i.e the diagonals starting from the bottom row cant reach the top row.

So in case p5 was blocking the spot right of p1, we could easily rotate all to the left by using $shift = -1.

that's demonstrated in the following case

- (9,5) --------------------

  1   0   0   0   0 

  0   0   2   0   0 

  0   0   0   0   3 

  0   4   0   0   0 

  0   0   0   5   0 

  6   0   0   0   0 

  0   0   7   0   0 

  0   0   0   0   8 

  0   9   0   0   0 


- (9,5) -------------------- -1 shift to the left

  1  37  28  19  10 

 20  11   2  38  29 

 39  30  21  12   3 

 13   4  40  31  22 

 32  23  14   5  41 

  6  42  33  24  15 

 25  16   7  43  34 

 44  35  26  17   8 

 18   9  45  36  27
[download]

Now how about the other cases and does $shift always need to be 1 or -1?

No, but 1 and -1 are easy since they obviously guaranty to fill the whole grid before returning to start.

But so do all numbers which are prime to $C: In the case above shifts 2 = -3 and 3 =-2 modulo $C=5 would have worked too.

But a shift 2 for $C=4 would create a loop (which is actually only complicating the solution to another shift)

The remaining solvable edge cases for $R==$C with $C>4 are done by choosing $shift=1. The diagonals reach the top row, but never the spot to right of the start if $C>4.

This is not the case for $R==$C==4 is quite special, exactly one diagonal collisions happens, between opposing corners.

- (4,4) --------------------

  1   5   9  13* 

 10  14   2   6 

  3   7  11  15 

 12* 16   4   8
[download]

This is easily fixed by renumbering the sequence and starting at the right upper corner. Hence 13 =>1 .. 16 =>4 , 1=>5 .. 12=>16 and no succeeding points can ever collide

Possible solutions with $C <=4 requires swapping rows and columns and special shift values

like

- (2,5) -------------------- $shift = -1

  1   0   0   0   0 

  0   0   2   0   0
[download]

or

- (3,5) -------------------- $shift = 3

  1   0   0   0   0 

  0   0   2   0   0 

  0   0   0   0   3
[download]

So how valuable are these results?

• no random jumps needed
• proven to work for all big grids
• very fast
• the remaining edge cases are very few
• those can be either hard coded or brute forced.

That's it, now I want my life back :)

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.