Tävlingsprogrammering/Uppgifter/Åttaspelet

Åttaspelet


Till vänster startpositionen i det första exemplet. Pilen visar det första draget. Bilden i mitten visar ställningen efter det första draget och pilarna indikerar de återstående sju dragen som måste göras för att nå slutställningen som visas till höger.

Åttaspelet (ett småsyskon till det mer kända femtonspelet) är en typ av pussel som består av åtta kvadratiska brickor i en ram. Brickorna är numrerade från 1 till 8. Ramen rymmer 3x3=9 brickor, så det finns ett hål. Ett drag består i att man skjuter en intillliggande bricka till hålets plats. Skriv ett program som givet en startställning beräknar det minsta antalet drag som behövs för att uppnå den ordnade slutställningen som visas till höger i figuren ovan.

Programmet ska läsa in bricknumret på var och en av de 9 positionerna, eller 0 för hålet. Numren matas in i vanlig “läsordning” (översta raden först, från vänster till höger). I givna testfall kommer det alltid vara möjligt att nå slutställningen.

Tips: En godtycklig ställning är antingen olöslig (vilket inte förekommer i testfallen) eller har en lösning med högst 31 drag.

Körningsexempel 1

Bricka ? 1
Bricka ? 5
Bricka ? 2
Bricka ? 7
Bricka ? 0
Bricka ? 3
Bricka ? 8
Bricka ? 4
Bricka ? 6

Antal drag: 8

Körningsexempel 2

Bricka ? 3
Bricka ? 7
Bricka ? 8
Bricka ? 5
Bricka ? 4
Bricka ? 6
Bricka ? 2
Bricka ? 0
Bricka ? 1

Antal drag: 27

Lösning

Djupet-först-sökning

Först uppgiftsmakarens kommentar: Tack vare att man vet att det inte behövs mer än 31 drag så kan uppgiften lösas med brute force, lämpligtvis med hjälp av en rekursiv funktion (djupet-först-sökning). Varje gång testar man att göra ett av de högst 3 möjliga dragen (observera att man aldrig flyttar samma bricka två gånger i rad, det är meningslöst och kan göra programmet slött) och rekurserar sedan från den nya positionen (se lösningen nedan). Notera att detta inte är en särskilt bra lösning, så fort spelplanen blir större kommer det ta för lång tid. Därför rekommenderas den insända bidraget längre ner på sidan som använder bredden-först-sökning istället.

Brute force-lösning:

#include <stdio.h>
#define N 3

int DIR[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
int s[N][N],min;

void shift(int i, int j, int ni, int nj) {
  int tmp=s[i][j];
  s[i][j]=s[ni][nj];
  s[ni][nj]=tmp;
}

void MLX(int nr, int dont) {
  int ok,i,j,pi,pj,ni,nj;
  ok=1;
  for(i=0;i<N;i++) for(j=0;j<N;j++) {
      if(s[i][j]!=(i*N+j+1)%(N*N)) ok=0;
      if(s[i][j]==0) {pi=i; pj=j;}
    }
  if(ok) min=nr;
  if(nr>=min-1) return;
  for(i=0;i<4;i++) if(i!=dont){
    ni=pi+DIR[i][0];
    nj=pj+DIR[i][1];
    if(ni>=0 && ni<N && nj>=0 && nj<N) {
      shift(pi,pj,ni,nj);
      MLX(nr+1,3-i);
      shift(pi,pj,ni,nj);
    }
  }
}      

int main() {
  int i,j;
  for(i=0;i<N;i++) for(j=0;j<N;j++) scanf("%d", &s[i][j]);    
  min=32;
  MLX(0,-1);
  printf("%d\n", min);
  return 0;
}

Bredden-först-sökning

Antalet olika ställningar som högst kan uppstå är 9! = 362880. Så uppgiften kan med fördel lösas med BFS. Är man cool kan man beskriva en ställning med en bitmask där varje position beskrivs av 4 bitar var. Faktum är att en ställning beskrivs unikt av de 8 första brickorna, så ställningen skulle kunna rymmas i en int, men i lösningen nedan använder vi en long istället för enkelhetens skull. I lösningen nedan betraktas nedre högra rutan som index 0 och övre vänstra som index 8.

import java.util.*;

public class EightGame
{
	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		//Placerar ut brickorna på brädet.
		long start = 0;
		for(int i = 0; i<9; i++)
		{
			System.out.print("Bricka ? ");
			start = (start<<4) + scan.nextInt();
		}

		//Letar rätt på var den tomma rutan finns.
		int pos = 0;
		for(long i = start; (i&15)!=0; i>>=4) ++pos;

		//Här spar vi alla besökta positioner.
		HashSet <State> vis = new HashSet <State> ();
		State s = new State(start,0,pos);
		vis.add(s);

		//Kö för bredden-först-sökning.
		LinkedList <State> qu = new LinkedList <State> ();
		qu.add(s);

		while(true) //BFS
		{
			s = qu.pop();
			if(s.board==0x123456780L) //Är vi klara?
			{
				System.out.println("\nAntal drag: " + s.mvs);
				break;
			}

			start = s.board; pos = s.pos; //Återanvänder variabler. :D

			State tmp;
			if(pos<6) //Flyttar tomma rutan upp.
			{
				tmp = new State(move(start,pos+3,pos), s.mvs+1, pos+3);
				if(vis.add(tmp)) qu.add(tmp);
			}
			if(pos>2) //Flyttar ned.
			{
				tmp = new State(move(start,pos-3,pos), s.mvs+1, pos-3);
				if(vis.add(tmp)) qu.add(tmp);
			}
			if(pos%3>0) //Flyttar höger.
			{
				tmp = new State(move(start,pos-1,pos), s.mvs+1, pos-1);
				if(vis.add(tmp)) qu.add(tmp);
			}
			if(pos%3<2) //Flyttar vänster.
			{
				tmp = new State(move(start,pos+1,pos), s.mvs+1, pos+1);
				if(vis.add(tmp)) qu.add(tmp);
			}
		}
	}

	//board = brädet
	//from = positionen för brickan vi vill flytta
	//to = positionen för den tomma rutan
	//Flyttar en bricka till den tomma rutan.
	private static long move(final long board, int from, int to)
	{
		from <<= 2; //from*4
		to <<= 2;
		final long mask = 0xFL<<from;
		return (board&mask)>>from<<to|board&~mask;
	}

	private static class State
	{
		//Spelbrädet
		final long board;

		//Antal drag och positionen för den tomma rutan.
		final int mvs, pos;

		State(long b, int m, int p)
		{
			board = b; mvs = m; pos = p;
		}

		public int hashCode()
		{
			return (int)board;
		}

		public boolean equals(Object o)
		{
			return ((State)o).board==board;
		}
	}
}