# Knight's tour on a rectangle

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. – Peter Taylor Jun 25 '12 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). – Steven Rumbalski Jun 25 '12 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. – Steven Rumbalski Jun 26 '12 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. – Peter Taylor Jun 26 '12 at 6:35
If you want to eliminate GolfScript, J, APL etc. from the answers to your questions, you should make the questions difficult, impractical or impossible to answer in those languages. (eg. require floats and GolfScript is out, the requirement for operator precedence in this question made it difficult enough for me to give up trying in J). – Gareth Jun 26 '12 at 9:56

### 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. – Ventero Jun 26 '12 at 21:44
@Ventero I don't know how I could miss that `eval` thing - did it several times before... Thank you very much. – Howard Jun 27 '12 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)+1`for 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.

-
 +1 for performance – w0lf Jun 26 '12 at 6:29

### 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)+1`for 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)+1`for 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. – beary605 Jun 26 '12 at 15:17 Added changes, thank you. – Ante Jun 26 '12 at 18:23

## 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. – Gaffi Jun 25 '12 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... – Gaffi Jun 25 '12 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 – w0lf Jun 25 '12 at 21:28 @w0lf Right, and I know what the issue is; I just have to get some time to fix it. – Gaffi Jun 25 '12 at 21:33