Knight's tour: Difference between revisions

=={{header|\M2000 Interpreter}}==

<lang M2000 Interpreter>

Function KnightTour$(StartW=1, StartH=1){

def boolean swapH, swapV=True

if startW<=4 then swapH=true: StartW=8+1-StartW

if startH>4 then swapV=False: StartH=8+1-StartH

Let final=8*8, last=final-1, HighValue=final+1

Dim Board(1 to 8, 1 to 8), Moves(1 to 8, 1 to 8)=HighValue

f=stack:=1,2,3,4,5,6,7,8

if 8-StartW=2 and StartH=2 then stack f {shift 1,-8}

Function KnightMove(x,w,h) {

a=2:b=1:z=1:p=1

if x mod 2=1 then swap a,b

if x>2 then p-! : if x>4 then swap z, p : if x>6 then p-!

w+=z*a

h+=p*b

if w>=1 and w<=8 and h>=1 and h<=8 then =(w, h) else =(,)

}

For j=1 to 8 :For i=1 to 8

s=stack

For k=1 to 8

m=KnightMove(stackitem(f, k),i, j)

if len(m)>1 then Stack s {data m}

Next : Board(i,j)=s : Next

stack f {shift 1,-8}

Next

For i=1 to 8 :For j=1 to 8

s=Board(i, j)

if len(s)>2 then

so=queue

For k=1 to len(s)

m=stackitem(s, k)

Append so, Len(Board(m#val(0), m#val(1))) :=m

Next

sort ascending so as number

s=stack

stack s {for k=0 to len(so)-1:data so(k!):next}

Board(i,j)=s

end if

Next : Next

s= Board(StartW, StartH)

n=0

BackTrack=Stack

Moves=1

Moves(StartW, StartH)=1

Repeat

n++

While n>len(s) {

if Len(BackTrack)=0 then Print "Break", moves : Break

Moves--

Stack BackTrack {Read s, n}

m=stackitem(s, n)

Moves(m#val(0), m#val(1))=HighValue

n++

}

m=stackitem(s, n)

w=m#val(0)

h=m#val(1)

if Moves(w, h)>=Moves then

if Moves<last then

s1=Board(w, h) :ii=-1

for i=1 to len(s1){m1=stackitem(s1, i) :if Moves(m1#val(0),m1#val(1))>moves then ii=i-1 : exit

}

if ii>=0 then

Moves++

Moves(w,h)=Moves

Stack BackTrack {Push n, s}

s=s1: n=ii

end if

else

Moves++

Moves(w,h)=Moves

end if

end if

until Moves=final

Document export$

Inventory Tour

letters=stack:="a","b","c","d","e","f","g","h"

f=stack:=1,2,3,4,5,6,7,8

if swapV Else stack f {Shift 1,-8}

if swapH then stack letters {Shift 1,-8}

For j=1 to 8:For i=1 to 8

Append Tour, Moves(i,j) :=stackitem$(letters, i)+str$(stackitem(f, j),"")

Next : Next

Sort ascending Tour as number

one=each(Tour)

While one {

export$=Eval$(one)

if not one^=last then export$="->"

If (one^+1) mod 8=0 then

export$={

}

End if

}

=export$

}

Document ex$

ex$= {Knight's Tour from a1

}+KnightTour$()+{Knight's Tour from h1

}+KnightTour$(8,1)+{Knight's Tour from a8

}+KnightTour$(1, 8)+{Knight's Tour from h8

}+KnightTour$(8, 8)

Clipboard ex$

Report ex$

</lang>

{{out}}

<pre>

Knight's Tour from a1

a1->b3->a5->b7->d8->f7->h8->g6->

h4->g2->e1->c2->a3->b1->d2->f1->

h2->g4->h6->g8->e7->c8->a7->b5->

c7->a8->b6->a4->b2->d1->f2->h1->

g3->h5->g7->e8->f6->h7->f8->d7->

b8->a6->b4->a2->c1->e2->g1->h3->

g5->e6->f4->d3->c5->e4->c3->d5->

e3->c4->d6->f5->d4->f3->e5->c6

Knight's Tour from h1

h1->g3->h5->g7->e8->c7->a8->b6->

a4->b2->d1->f2->h3->g1->e2->c1->

a2->b4->a6->b8->d7->f8->h7->g5->

f7->h8->g6->h4->g2->e1->c2->a1->

b3->a5->b7->d8->c6->a7->c8->e7->

g8->h6->g4->h2->f1->d2->b1->a3->

b5->d6->c4->e3->f5->d4->f3->e5->

d3->f4->e6->c5->e4->c3->d5->f6

Knight's Tour from a8

a8->b6->a4->b2->d1->f2->h1->g3->

h5->g7->e8->c7->a6->b8->d7->f8->

h7->g5->h3->g1->e2->c1->a2->b4->

c2->a1->b3->a5->b7->d8->f7->h8->

g6->h4->g2->e1->f3->h2->f1->d2->

b1->a3->b5->a7->c8->e7->g8->h6->

g4->e3->f5->d6->c4->e5->c6->d4->

e6->c5->d3->f4->d5->f6->e4->c3

Knight's Tour from h8

h8->g6->h4->g2->e1->c2->a1->b3->

a5->b7->d8->f7->h6->g8->e7->c8->

a7->b5->a3->b1->d2->f1->h2->g4->

f2->h1->g3->h5->g7->e8->c7->a8->

b6->a4->b2->d1->c3->a2->c1->e2->

g1->h3->g5->h7->f8->d7->b8->a6->

b4->d3->c5->e6->f4->d5->f6->e4->

d6->f5->e3->c4->e5->c6->d4->f3

/<pre>