Matt i ett drag

Vit drar och gör matt i ett drag.

När du tittar tillbaka i dina gamla årgångar av Schacknytt hittar du massvis av schackpussel. Tyvärr inser du att det var alldeles för länge sedan du spelade schack, och även triviala pussel som att hitta matt i ett drag är numera långt över din förmåga.

Men skam den som ger sig. Du inser såklart att du istället kan använda dina nyfunna algoritmiska kunskaper för att lösa problemet genom att göra ett program som hittar det vinnande draget.

Brädet du får uppfyller följande villkor:

• Ingen spelare kan göra rockad.

• Ingen spelare kan göra en passant.

• Spelbrädet är en möjlig position.

• Vit kan sätta svart i matt i ett drag.

Ditt program ska skriva ut vilket drag vit ska göra för att sätta svart i matt.

Indata

Indatan består av 8 rader med 8 tecken var. Den första raden är rad 8 på schackbrädet, och den sista raden är rad 1 på schackbrädet.

Den första kolumnen är kolumn a och den sista kolumnen är kolumn h.

Varje tecken representerar en pjäs som följer:

P

vit bonde

N

vit springare

B

vit löpare

R

vitt torn

Q

vit dam

K

vit kung

p

svart bonde

n

svart springare

b

svart löpare

r

svart torn

q

svart dam

k

svart kung

.

tom ruta

Utdata

Utdatan ska vara ett drag specifierat som fyra tecken. De två första tecknen ska ange vilken ruta vit flyttar från, och de andra två vilken ruta vit flyttar till. En ruta anges som xy, där $x$ är kolumnen och $y$ raden.

rn...q.b
pb..pPkp
.p......
..ppN..p
...P....
..NB....
PPPQ.PP.
..KR....

d2g5

..kr...r
p..n..pp
.p.Bnp..
....p...
........
........
PPP..PPP
...RKB.R

f1a6

rnbq..kr
.p.n..pp
p...p...
...pP...
......Q.
B.PB....
P.P..PPP
R....RK.

g4e6

r.bqkb.r
pp.npppp
.....n..
.....N..
...PN...
........
PPPBQPPP
R...KB.R

e4d6

........
.....p..
...p....
b...Q.K.
k.nq....
p..NR..r
..P..P..
R..Bn...

e5e8

.rbq..r.
p.Pk.K.b
.P.bnp..
..n....p
........
........
....p...
...R....

c7b8