Knight's tour on a rectangle [closed]

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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[]).

Answer 5

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"

Answer 6

Python, 370 367 366 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'

Answer 7

VBA 494 574 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

Answer 8

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