# Problem of the Month (February 2016)

Consider a chess piece that has some possible moves that are not necessarily symmetric, each possible move being one square horizontally, vertically, diagonally, a knight move. What is the longest loop that piece can make on an n×m chessboard, visiting each square no more than once? How does the size of the longest loop change as n, m, or both approach infinity?

Up to symmetry, there are 17 different collections of such 3 moves, where loops of length more than 2 are possible. The longest-known loops (and paths) are shown for each of these below. Can you extend these results? Can you find any patterns? What about collections of 4 such moves? Which n×m chessboards can be completely visited?

Paths
1234567n
111111111
222222222
3369121518213n
44710131619223n+1
55811141720233n+2
661215212632386n–4
771319253137436n+1
nn3⌊n/3⌋+n4n–3–3⌊(n+1)/3⌋?????
Loops
1234567n
100000000
200000000
303333333
403333333
503666666
6039152127336n–9
70312182430366n–6
n033n–9?????

1234567n
111111111
222222222
3369121518213n
44710131619223n+1
55811141720233n+2
6691821273338?
77101925313743?
nnn+36⌊n/3⌋+n?????
1234567n
100000000
200000000
300666666
400666666
5006612121212
6006121824306n–12
700618243036?
n006?????

1234567n
111111111
224681012142n
335791113152n+1
4461214182225?
5571317212529?
6681822263438?
7791925313743?
nnn+24⌊n/2⌋+n?????
1234567n
100000000
200444444
300444444
400481216204n–8
5004121620244n–4
600416202832?
700420243236?
n004?????

1234567n
11234567n
22345678n+1
3369121518213n
44812162024284n
551015202530355n
66111824303542?
771421283542??
nn2n–⌊(n+2)/4⌋
+⌊(n+1)/4⌋
3n4n????
1234567n
100000000
200000000
304444444
4048121620244n–4
5048121620244n–4
60412202428364n+4
70416283240??
n04??????

1234567n
11234567n
224681012142n
3369121518213n
44812162024284n
551015202530355n
661218243036426n
771421283542497n
nn2n3n4n5n6n7nn2
1234567n
100000000
203333333
303691215183n–3
403912152124?
5031215182730?
6031521273339?
70318243039??
n033n–3*?6n–3??
* = 3n+3⌊(n–3)/3⌋

1234567n
111111111
222446682⌊(n+1)/2⌋
3369121518213n
4471013172124?
55815202530355n
6691723283442?
77101826334045?
nnn+3*?????
* = 3n–2+2⌊(n+1)/3⌋–2⌊n/3⌋
1234567n
100000000
200000000
300888888
400888888
500881616248⌊(n-1)/2⌋
600816243240?
7008162432??
n008?????

1234567n
111111111
224681012142n
335791113152n+1
44612161824284n–2⌊(n+1)/3⌋+2⌊n/3⌋
55713172125294n–2⌊(n+1)/3⌋+2⌊n/3⌋+1
66818242836426n–2⌊(n+1)/3⌋+2⌊n/3⌋
77919253137??
nnn+24⌊n/2⌋+n6⌊n/2⌋+n?10⌊n/2⌋+n12⌊n/2⌋+n?
1234567n
100000000
200666666
300666666
400612121824?
500612182424?
600618243036?
700624303642?
n006?????

1234567n
111111111
222446682⌊(n+1)/2⌋
333557792⌊(n+1)/2⌋+1
444881212164⌊(n+1)/2⌋
555991313174⌊(n+1)/2⌋+1
66612121818246⌊(n+1)/2⌋
77713131919256⌊(n+1)/2⌋+1
nnn2⌊n/2⌋+n2⌊n/2⌋+n4⌊n/2⌋+n4⌊n/2⌋+n6⌊n/2⌋+n⌊(n2+1)/2⌋
1234567n
100000000
200444444
300444444
4004488124⌊(n-1)/2⌋
500441212164⌊(n+1)/2⌋
60044161620?
70044161624?
n0044**??
* = 4n–4⌊(n+5)/4⌋

1234567n
111111111
224681012142n
3369121518213n
4471115182226?
551015202530355n
66111724303641?
771421283542497n
nn***?????
* = 2n–⌊(n–1)/5⌋+⌊(n–2)/5⌋–⌊(n–4)/5⌋+⌊(n–5)/5⌋
** = 3n–⌊(n–1)/5⌋+⌊(n–2)/5⌋–⌊(n–4)/5⌋+⌊(n–5)/5⌋
1234567n
100000000
200000000
305555555
405555555
50510152025305n–5
60515202530355n
7051525303545?
n05??????

1234567n
111111111
224681012142n
335791113152n+1
44812162024284n
55913172125294n+1
661218243036426n
771319253137436n+1
nn2⌊n/2⌋+n4⌊n/2⌋+n6⌊n/2⌋+n8⌊n/2⌋+n10⌊n/2⌋+n12⌊n/2⌋+n2(n–1)⌊n/2⌋+n
1234567n
100000000
204444444
304444444
4048121620244n–4
50412162024284n
6041620243236?
7041624283640?
n044n–8?????

1234567n
111111111
222222222
3369121518213n
44710131619223n+1
55811141720233n+2
661218243036426n
771319253137436n+1
nn3⌊n/3⌋+n6⌊n/3⌋+n9⌊n/3⌋+n12⌊n/3⌋+n15⌊n/3⌋+n18⌊n/3⌋+n3(n-1)⌊n/3⌋+n
1234567n
100000000
200000000
306666666
406666666
506666666
60612182430366n–6
7061824303642?
n06??????

1234567n
111111111
21246810122n–2
3147101316193n–2
4161014172025?
5181317192633?
61101620263036?
71121925333643?
n12n–23n–2?????
1234567n
100000000
200000000
300555555
400555555
50055101520?
60055152025?
70055202530?
n0055????

1234567n
111111111
212222222
3149101318193n–2+2⌊n/3⌋–2⌊(n-1)/3⌋
4161012151921?
5181114172023?
61101519233337?
71121921303639?
n12n–23n–2?????
1234567n
100000000
200000000
300099999
400999999
5009991818?
60099182727?
70099272736?
n0099????

1234567n
111111111
212222222
3124121314167⌊n/4⌋–⌊(n+1)/4⌋+n
412613141518?
5121114172023?
6121421252636?
7121525273039?
n12??????
1234567n
100000000
200000000
3000012121212
40001212121212
50001212121212
6001212122424?
7001212122436?
n0012?????

1234567n
111111111
212222222
3167121318194⌊n/2⌋+n
4179131519212⌊n/2⌋+2n+1
51811141720233n+2
61121318253037?
71131524273639?
n13⌊n/3⌋+n2n+1?????
1234567n
100000000
200000000
300666666
406666666
50661212121212
606612182430?
706618243036?
n066?????

1234567n
111111111
212222222
31234567n
41245678n+1
5125678113⌊n/3⌋+2
6126781113*
71278111314**
n12nn+13⌊n/3⌋+2***?
* = 2⌊n/3⌋+⌊(n-1)/3⌋+n
** = 2⌊(n+1)/3⌋+⌊(n+3)/3⌋+n
1234567n
100000000
200000000
300333333
400333333
500336666
60033699***
700336912?
n00336***??
*** = 3⌊n/3⌋+3⌊(n-2)/3⌋

1234567n
111111111
212222222
3147101316193n–2
418914172025?
5191117212631?
61101318233035?
71121524293543?
n1*2n+1?????
* = ⌊(n+1)/4⌋+3⌊n/4⌋+n
1234567n
100000000
200000000
300088888
400888888
508888888
608816162432?
708816243240?
n088?????

There are 89 different sets of 4 different directions where loops might be possible, and where no move can be reversed. For some of those sets, here are the smallest grids they completely fill by loops containing all 4 different moves:

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 4/1/16.