#include <stdio.h>

int n,f[10],tom;

int pack(){
/* …versŠtter stŠllningen (f[], tom) till ett heltal */
  int r,s;
  s=0;
  for(r=0;r<n;r++) if(r!=tom) s=2*s+f[r];
  return s*n+tom;
}

void unpack(int val){
/* …versŠtter stŠllningens heltal till (f[], tom) */
  int r,s;
  tom=val%n;
  s=val/n;
  for(r=n-1;r>=0;r--) if(r!=tom) {
    f[r]=s%2;
    s/=2;
  }
}

int main() {
  int a,q[448],min[448],s,p,r,now,next;  
  printf("Brädets storlek ? ");
  scanf("%d",&n);
  printf("Den tomma rutan ? ");
  scanf("%d",&tom);
  tom--;  
  for(a=0;a<n;a++) f[a]=0;
  /* LŠgg in starpositionen i kšn */
  q[0]=pack();
  for(a=0;a<448;a++) min[a]=-1;
  min[q[0]]=0;  
  now=0;
  next=1;
  while(now<next) {
    unpack(q[now]);
    /* Kolla om alla brickorna Šr vita */
    for(p=0,r=0;p<n;p++) if(p!=tom) r+=f[p];
    if(r==n-1) break;
    /* Loopa šver brickorna */
    for(p=0;p<n;p++) if(p!=tom && p!=tom-1 && p!=tom+1) {
      /* Flytta bricka p till den tomma platsen och vŠnd brickorna som passeras*/
      if(tom>p+1) for(r=p+1;r<tom;r++) f[r]^=1;
      else for(r=tom+1;r<p;r++) f[r]^=1;
      f[tom]=f[p];
      tom=p;
      s=pack();
      /* LŠgg in den nya stŠllningen sist i kšn om den inte redan Šr besškt */
      if(min[s]==-1) {
        min[s]=min[q[now]]+1;
        q[next++]=s;
      }
      /* terstŠll den aktuella stŠllningen */
      unpack(q[now]);
    }  
    now++;
  }  
  if(now<next) printf("Det krävs minst %d drag.\n",min[q[now]]);
  return 0;
}