Dames: King Me?

Défi:

Étant donné un damier, sortez le plus petit nombre de mouvements qu'il faudrait (en supposant que le noir ne bouge pas du tout) pour rogner une pièce rouge, si possible.

Règles :

Le côté rouge sera toujours en bas, mais leurs pièces peuvent commencer dans n'importe quelle rangée (même la rangée du roi vers laquelle ils doivent se rendre). Les pièces noires sont immobiles , ce qui signifie qu'elles ne se déplacent pas entre les mouvements des rouges, mais elles sont retirées du plateau lorsqu'elles sont capturées. Notez que les pièces peuvent commencer sur n'importe quel espace du plateau, y compris les unes à côté des autres. Ce n'est pas ainsi que se jouent les dames normales, mais votre programme doit être capable de les résoudre. (Voir entrée 5) Cependant, les pions ne doivent se déplacer qu'en diagonale (voir entrée 3). La capture en arrière est autorisée si la première capture est en avant dans la chaîne (voir entrée 7).

Contribution:

Un damier 8x8, avec des espaces de tableau définis comme les caractères suivants (n'hésitez pas à utiliser des alternatives tant qu'elles sont cohérentes):

. - Vide

R - Pièce (s) rouge (s)

B - Pièce (s) noire (s)

Production:

Le plus petit nombre de mouvements, il faudrait une pièce rouge pour être «roi» en entrant dans la rangée du roi sur la rangée supérieure du plateau (côté noir), 0 si aucun mouvement n'est requis (une pièce rouge a commencé sur la rangée du roi), ou un nombre négatif s'il est impossible de rois une pièce rouge (c'est-à-dire que le noir occupe toute la première rangée).

Entrée 1:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Sortie 1:

Entrée 2:

. . . . . . . .
. . . . . . . .
. . . . . B . .
. . . . . . . .
. . . B . . . .
. . . . . . . .
. B . . . . . .
R . . . . . . .

Sortie 2:

Entrée 3:

. B . B . B . B
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Sortie 3:

-1

Entrée 4:

. . . . . . . R
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Sortie 4:

Entrée 5:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. B . . B . . .
B . . . . B . .
. B . B . . . .
. . B . . B . .
. . . R R . . .

Résultat 5:

Entrée 6:

. . . . . . . .
. . . . . . . .
. B . . . . . .
. . B . . . . .
. B . B . . . .
. . . . R . . .
. . . B . . . .
. . . . R . . .

Résultat 6:

Entrée 7:

. . . . . . . .
. . . . . . . .
. . B . . . . .
. . . . . . . .
. . B . . . . .
. B . B . B . .
. . . . B . . .
. . . . . R . R

Sortie 7:

Notation:

C'est le code-golf , donc le code le plus court en octets gagne.

code-golf grid game path-finding board-game Yodle
la source

Le deuxième cas de test ne devrait-il pas être 2, car vous pouvez faire un double / triple saut?

James

Un tableau d'état de tableaux d'entiers comme entrée est-il OK?

Jonathan Allan

J'ai ajouté un autre test qui devrait s'avérer difficile. Cela implique plusieurs sauts, plusieurs pièces et des sauts en arrière afin d'obtenir la meilleure solution possible.

orlp

@orlp Hm, j'allais dire qu'aucune des pièces rouges n'est autorisée à reculer, car aucune d'entre elles n'est rois (d'où le but du défi), mais il semble que certaines personnes jouent avec des règles où la capture à l'envers est autorisée par des non pièces royales si la première capture était en avant. J'ajouterai cela aux règles puisque je n'en étais pas au courant auparavant.

Yodle

ooooooooh, vous n'avez pas à choisir une seule pièce rouge, ils peuvent faire équipe! Je comprends

Greg Martin

JavaScript (ES6), 354 322 octets

Prend un tableau en entrée avec:

0 = carré vide
1 = pièce rouge
2 = pièce noire

Renvoie le nombre optimal de coups, ou 99 s'il n'y a pas de solution.

C'est très rapide mais pourrait être joué beaucoup plus.

F=(b,n=0,C=-1,i)=>b.map((v,f,X,T,x=f&7,y=f>>3)=>v-1||(y&&n<m?[-9,-7,7,9].map(d=>(N=c=X=-1,r=(d&7)<2,T=(t=f+d)>=0&t<64&&(x||r)&&(x<7||!r)?(!b[t]&d<0)?t:b[t]&1?N:b[t]&2&&(d<0&y>1|d>0&C==f)?(X=t,x>1||r)&&(x<6|!r)&&!b[t+=d]?c=t:N:N:N)+1&&(b[f]=b[X]=0,b[T]=1,F(b,n+!(C==f&c>N),c,1),b[f]=1,b[X]=2,b[T]=0)):m=n<m?n:m),m=i?m:99)|m

var test = [
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,2,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,2,0,2,0,2,0,2,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,1,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,2,0,0,0,
    2,0,0,0,0,2,0,0,
    0,2,0,2,0,0,0,0,
    0,0,2,0,0,2,0,0,
    0,0,0,1,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,2,0,0,
    0,0,0,0,2,0,0,0,
    0,0,0,0,0,1,0,1
  ]
];

test.forEach((b, n) => {
  console.log("Test #" + (n + 1) + " : " + F(b));
});

Développer l'extrait

Arnauld
la source

99 est probablement très bien, je ne peux pas imaginer une vraie solution prenant 99 mouvements sur une carte 8x8. Bon travail!

Yodle

Dames: King Me?

Défi:

Réponses:

JavaScript (ES6), 354 322 octets