Knight's tour on a rectangle [closed]

Given an a-by-b sized grid, and a chess knight, determine:

• A starting point and path the knight can take to visit every square in the grid
• or "NOT POSSIBLE", if not possible.

Input: Two integers, a, b.

Output: Numbers output in an a-by-b grid:

1 4 7 10
8 11 2 5
3 6 9 12


Where 1 is where the knight starts, a*b is where the knight ends, and the numbers signify the path the knight must take, in ascending order. The knight cannot land on the same square twice.

The rows of the grid must be separated with a newline, and the items in each row must be separated with a space.

Test Cases:
| is a newline.
3 4 -> 1 4 7 10 | 8 11 2 5 | 3 6 9 12
2 3 -> NOT POSSIBLE

If there is a solution there will be more than one: any valid solution is acceptable.

Shortest code wins. Please do not use any programming languages that are known to produce short programs: e.x. GolfScript, APL, J, K, etc.

• The recently added language restriction seems to be against the spirit of code golf, and is additionally rather vague on languages like Perl. Commented Jun 25, 2012 at 16:23
• -1. Although I have no desire to ever write solutions in GolfScript, APL, J, or K, I find this restriction irksome enough to warrant a down-vote (which I will rescind if you change the requirement). Commented Jun 25, 2012 at 17:04
• @beary605: I'll happily upvote any answer to this question in GolfScript, APL, J, K, or any similarly extremely terse programming language. It's takes plenty of work to write short programs in those languages because it takes plenty of work to learn them. I've coded all my answers in Python (except for one in Perl). The game I play is that I try to be shortest among Ruby, Perl, Python, JavaScript, etc. Doing so usually produces a satisfactory number of upvotes even if I don't "win". Not winning is my fault for not taking time to learn the right tool for the job. Commented Jun 26, 2012 at 2:05
• Writing GolfScript isn't easy. The debugging support is negligible, and you have to keep track of exactly what's on the stack at any time with no static checking to ensure you were right. Commented Jun 26, 2012 at 6:35
• The language thing is ridiculous. APL and K are not designed specifically to make short answers (like Golfscript for example) - they are programming languages people use in actual jobs (well paying ones too). I know people that only know how to program in APL - they aren't even allowed to answer? Commented Jun 9, 2014 at 3:43

Ruby, 306 284 characters

w,h=eval"[#{gets}]"
f=Hash.new{|g,k|s,x,y,*r=k
x<0||y<0||x<w&&y<h&&s>0&&'\$&(,268:'.bytes{|u|r|=f[[s-1,x-2+u%5,y-9+u/5]].select{|l|l[y*w+x]<1}}
g[k]=r.map{|l|l=l*1;l[y*w+x]=s;l}}
f[[1,0,0]]=[[1]+[0]*(w*h-1)]
(s=f[[w*h,w-1,h-1]][0]||(puts"NOT POSSIBLE"))&&s.each_slice(w){|f|puts f*" "}


Implementation in Ruby, takes input from STDIN and outputs to STDOUT. Although a little bit optimized it is still extremely slow on large grids.

> 5,3
NOT POSSIBLE

> 5,4
1 18 5 12 9
6 15 10 19 4
17 2 13 8 11
14 7 16 3 20


Edit: Ventero pointed out some improvements whiche saved several chars. I also changed the encoding of possible moves to be much shorter now.

• You don't need the splat in front of k, instead of x>=0&&y>=0&& you can use x<0||y<0|| and you can parse the input using something like w,h=eval"[#{gets}]" to save a few characters. Commented Jun 26, 2012 at 21:44
• @Ventero I don't know how I could miss that eval thing - did it several times before... Thank you very much. Commented Jun 27, 2012 at 6:01

Python, 420

w,h=input()
s=w*h
d=range
def r(l):y=l/w;x=l%w;return[x+p+w*(q+y)for p,q in[(1,2),(2,1),(-2,1),(-1,2),(-1,-2),(-2,-1),(2,-1),(1,-2)]if 0<=x+p<w and 0<=q+y<h]
def f(p):
a={l:len(r(l))for l in r(p[-1])if l not in p}
for l in[k for k in a if a[k]==min(a.values())]:
x=f(p+[l])
if len(x)==s:return x
return p
e=f([0])
print len(e)<s and"NOT POSSIBLE"or'\n'.join([' '.join(e.index(x+y*w)+1for x in d(w))for y in d(h)])


I've sacrificed shorter code for reasonable performance, so it should be able to find solutions for boards up to 9x9 in under 3 seconds.

Ruby 364 359

K=->a,b{A,B=a,b;(0...A*B).each{|i|Z[[i]]};p"NOT POSSIBLE"}
Z=->v{c=v.last
abort (0...v.size).map{|i|{:i=>i+1,:x=>v[i]}}.sort_by{|i|i[:x]}.map{|i|i[:i]}.each_slice(B).map{|r|r*' '}*?\n if v.size==A*B
([[1,2],[2,1],[-2,1],[-1,2],[-1,-2],[-2,-1],[2,-1],[1,-2]].map{|d|o=(c/B)+d[0]
u=(c%B)+d[1]
(o>=0&&0<=u&&A>o&&B>u)?o*B+u :-1}.flatten-[-1]-v).each{|i|Z[v+[i]]}}


Same idea as my C# answer.

This gets invoked like this: K[a,b] and outputs the desired result to the console.

Online demos:

Test case 1: http://ideone.com/yDiiS

Test case 2: http://ideone.com/WVUmX

Example of a bigger board (4x5): http://ideone.com/hItNo

C# 796 793

using System;using System.Collections.Generic;using System.Linq;namespace Z{public class P{public static void Main(){new P().K(3,4);}int x, y;void K(int a, int b){x=a;y=b;for(var s=0;s<x*y;s++)K(new[]{s});Console.WriteLine("NOT POSSIBLE");}void K(int[] v){if(v.Length<x*y)foreach(var m in M(v))K(v.Concat(new[]{m}).ToArray());else{Console.WriteLine(String.Join("\n",v.Select((p,i)=>new{p,i}).OrderBy(e=>e.p).GroupBy(e=>e.p/y).Select(g=>String.Join(" ",g.Select(e=>e.i+1)))));Environment.Exit(0);}}IEnumerable<int> M(int[] v){var c=v.Last();var q=new{X=c/y,Y=c%y};return(from m in new[]{new{X=1,Y=2},new{X=2,Y=1}}from d in Enumerable.Range(0,4).Select(i=>new{X=(i&2)-1,Y=(i&1)*2-1})select new{X=q.X+d.X*m.X,Y=q.Y+d.Y*m.Y}into p where p.X>=0&&p.Y>=0&&p.X<x&&p.Y<y select p.X*y+p.Y).Except(v);}}}


This code finds a solution (if any) using brute force. Here's the ungolfed (and slightly refactored) version: http://pastie.org/4149829

Input: Modify the parameters in the new P().K(...); call.

Output: To the console, in the required format

Online demos:

Test Case 1 (3, 4): http://ideone.com/UU9sw (another solution than OP's, but it's a valid one)

Test Case 2 (2, 3): http://ideone.com/ZX9xC

A bigger board (4, 7): http://ideone.com/QKuXL (this takes close to 5s to run, so retry if it fails the first time).

Note: Mono does not have the String.Join method overload that takes as a parameter an IEnumerable<T>, so in order to get this working on IdeOne I have to modify the code a bit (modify these IEnumerable<T>s to string[]).

Python, 316

Took about 30 minutes to run on input of 3 4. I wouldn't try it on anything larger.

import itertools as I
r=range
x,y=map(int,raw_input().split())
m=[(a,b)for a in r(x)for b in r(y)]
q=[n for n in I.permutations(m,x*y)if all((abs(o[0]-p[0]),abs(o[1]-p[1]))in((1,2),(2,1))for(o,p)in zip(n,n[1:]))]
print'\n'.join(' '.join([q[0].index(z)+1for z in m][i:i+y])for i in r(0,x*y,y))if q else"NOT POSSIBLE"


I notice the other Python answers get input by doing x,y=input() rather than x,y=map(int,raw_input().split()), but the question does not allow for commas in the input so it seems the former method would fail. If the question does allow commas in the input, I'll shave an additional 20 characters off my answer.

I tried a recursive solution, but the best I could get was 334 characters:

r=range
x,y=map(int,raw_input().split())
m=[(a,b)for a in r(x)for b in r(y)]
o=[]
def f(m,x=0):
for n in m:
if x==0 or map(lambda x,y:abs(x-y),n,x)in([1,2],[2,1])and not o:
if len(m)==1 or f(m-{n},n)or o:o.append(n)
f(set(m))
print'\n'.join(' '.join([o.index(z)+1for z in m][i:i+y])for i in r(0,x*y,y))if o else"NOT POSSIBLE"


Python, 370367366 338

Simple recursive solution. It isn't efficient, but works fast for example cases :-)

import itertools as I
P=I.product
a,b=input()
r=range;A=r(a);B=r(b);T={}
def S(x,y):
if 0<=x<a and 0<=y<b and(x,y)not in T:
T[x,y]=len(T)+1
for i,j in P((-2,2),(-1,1)):S(x+i,y+j);S(x+j,y+i)
if len(T)!=a*b:T.pop((x,y))
for q,w in P(A,B):S(q,w)
print"\n".join(" ".join(str(T[i,j])for j in B)for i in A)if len(T)==a*b else'NOT POSSIBLE'

• A,B,T=range(a),range(b),{} -> r=range;A,B,T=r(a),r(b),{}. any(S(q,w) for q,w in P(A,B)) -> any(S(q,w)for q,w in P(A,B)). If you state C=(-2,2);D=(-1,1), you can go list(P(C,D))+list(P(D,C)) instead to save 1 character. Commented Jun 26, 2012 at 15:17

VBA 494574 833 chars

Fixing to account for the transposed example added quite a bit of code...

I squeezed a little more out be shifting around some If checks to avoid using End If.

This now correctly handles 4, 5 and 5, 4, but it takes impossibly long for 4, 7, and I'm not 100% sure it works for that set.

Dim z,v,e,i,j,p,l
Sub k(a,b)
e=a*b:q:i=2
If c(a,b) Then z(e)=e:j=e+1
For i=1 To e:s=s & z(i) & IIf(i Mod b=0,vbCr,vbTab):Next
MsgBox IIf(j-1=e,s,"NOT POSSIBLE")
End Sub
Sub o()
z(l)=j:v(l)=1:p=l:i=p:j=j+1
End Sub
Sub u(r,t)
z(r)=0:v(r)=0:p=t:j=j-1
End Sub
Sub q()
ReDim z(1 To e),v(1 To e):z(e)=e:v(e)=1:p=1:z(1)=p:v(1)=p:j=2
End Sub
Function w(b)
f=(p-1) Mod b+1:m=(l-1) Mod b+1:g=Int((p-1)/b)+1:n=Int((l-1)/b)+1:w=(((f-2=m Or f+2=m) And (g-1=n Or g+1=n)) Or ((f-1=m Or f+1=m) And (g-2=n Or g+2=n)))
End Function
Function c(a,b)
t=p:m=i:
If i>1 And i<e Then
For h=1 To 8:l=p+Choose(h,(b-2),(b+2),(2*b-1),(2*b+1),-(b-2),-(b+2),-(2*b-1),-(2*b+1)):r=l:If l>1 And l<e Then If v(l)=0 Then If w(b) Then o:If j>=e Then l=j:If w(b) Then c=1 Else u r,t Else c=c(a,b):If c=0 Then u r,t
Next:End If
If c=(i>=e) Then i=m+1:c=c(a,b)
End Function

• And wouldn't you know it. I only tested on the two examples given. This does work for 3 4, but not for 4 3 (which should be equivalent, transposed answers...) Looking into this. Commented Jun 25, 2012 at 15:22
• Looking at this more carefully, I don't believe it will actually accurately catch all solutions. Some recursion will fix that (and more code) but I will have to come back to it later... Commented Jun 25, 2012 at 17:28
• I've tested it and it runs fine for both 3,4 and 4,3. However, it says "NOT POSSIBLE" for 4,5, which has a solution: ideone.com/y5hl1 Commented Jun 25, 2012 at 21:28
• @w0lf Right, and I know what the issue is; I just have to get some time to fix it. Commented Jun 25, 2012 at 21:33

APL (Dyalog Extended), 22 bytes (SBCS)

⊃⌂kt,⍥⊆'NOT POSSIBLE'⍨


Try it online!

⊃ the first of…

⌂kt the first knights tour (if possible, else: an empty list)

,⍥⊂ juxtaposed with

'NOT POSSIBLE'⍨ the required fall-back value