Tävlingsprogrammering/Uppgifter/Senet
Senet (PO-kvalet 2008)
Senet är ett uråldrigt egyptiskt brädspel som hittats i otaliga gravar. Reglerna är okända men en av de vanligaste rekonstruktionerna beskrivs här. Spelplanen kan betraktas
som en serie med rutor där vi i denna uppgift endast bryr oss om de första 15. De två
spelarna, som vi kallar A och B, har vardera 5 pjäser som vid spelets början alltid står
uppställda enligt översta schemat i figur 2. Spelarna turas om att göra drag, A har första draget. I varje drag kastar spelaren några stickor, vilka tillsammans utgör en slags
tärning som kan anta värdena 1, 2, 3, 4 eller 5. Därefter väljer spelaren en av sina pjäser och flyttar den framåt med så många steg som tärningen visade. För att vara ett
godkänt drag måste pjäsen sluta på en ruta som antingen är tom eller innehåller en
obevakad motståndarpjäs. I det senare fallet flyttas moståndarpjäsen tillbaka till den
ruta varifrån den flyttade pjäsen kom, så att pjäserna i praktiken byter plats. En pjäs
är obevakad om det inte finns en likadan pjäs i någon av de två angränsande rutorna.
Du ska skriva ett program som givet pjäsernas nuvarande positioner bestämmer det minimala antalet drag N som har spelats, samt en möjlig sådan dragsekvens.
Programmet ska fråga efter en sträng med längd 15, där varje tecken beskriver en ruta på spelplanen: A för en pjäs tillhörande spelare A, B för en pjäs tillhörande spelare B och . (punkt) för en tom ruta. Det finns alltid fem A:n, fem B:n och fem punkter i strängen.
Programmet ska skriva ut den kortaste dragsekvensen som leder från utgångsställningen till den inmatade ställningen. Närmare bestämt ska programmet skriva ut en rad med N tal i intervallet 1..5, där varje tal anger hur många steg som har tagits i respektive drag (första talet indikerar första draget etc.). Vilken pjäs som flyttats i varje drag behöver inte anges. Om det finns flera sekvenser med minimal längd kan program- met ange vilken som helst av dem. I samtliga testfall är N ≤ 6. Notera att N kan vara udda, d.v.s. A kan ha gjort ett drag mer än B.
Körningsexempel:
Ställning ? ABAAABBB.B...A. Dragsekvens: 5 3
Lösning
[redigera]Detta är ett klassiskt exempel på ett problem som enklast löses genom en rekursiv funktion. Funktionen testar att göra alla möjliga förstadrag (max 25 stycken: 5 tärningsutfall och 5 pjäser att välja mellan) och för vart och ett av dem anropar den sig själv för att göra alla möjliga andradrag o.s.v. En sådan lösning (s.k. backtracking) har tyvärr en tidsåtgång som växer exponentiellt med antalet drag, men eftersom vi vet att antalet drag är högst 6 behöver vi inte göra någon effektivisering (i praktiken kommer man aldrig i närheten av 256 dragsekvenser eftersom många drag är otillåtna).
Om en effektivare lösning hade krävts hade en enorm förbättring varit om vi markerat de ställningar vi redan varit vid eller ännu hellre gjort bredden-först-sökning.
Lösningsförslag i C
#include <stdio.h>
#define L 15
int p[L],f[L],d[100],brad[100],min;
void MLX(int nr, int player) { //Den rekursiva funktionen, nr är antalet spelade drag, player A=0, B=1
int i,j,pt[L],ny,opp;
opp=player^1; //motståndaren (eftersom 1^1=0 och 0^1=1)
for(i=0;i<L;i++) if(p[i]!=f[i]) break;
if(i==L) { //Har vi kommit till den inmatade ställningen? I så fall spara dragen
min=nr;
for(i=0;i<nr;i++) brad[i]=d[i];
}
if(nr+1>=min) return; //Ingen idé att fortsätta, vi kommer aldrig förbättra det minsta antalet drag
for(i=0;i<L;i++) pt[i]=p[i]; //Spara undan ställningen före draget
for(d[nr]=1;d[nr]<=5;d[nr]++) { //Testa varje möjligt tärningsutfall (1..5)
for(i=0;i+d[nr]<L;i++) if(p[i]==player) { //Testa varje möjlig pjäs som tillhör player
ny=i+d[nr];
if(p[ny]==-1) { //Går draget till en tom ruta?
p[i]=-1; p[ny]=player; //Uppdatera brädet...
MLX(nr+1,opp); //...och rekursera fast med motståndaren i tur att flytta
}
else if (p[ny]==opp && p[ny+1]!=opp && p[ny-1]!=opp){ //Går draget till en obevakad motståndarruta?
p[i]=opp; p[ny]=player; //Uppdatera brädet...
MLX(nr+1,opp); //...och rekursera fast med motståndaren i tur att flytta
}
for(j=0;j<L;j++) p[j]=pt[j]; //Återställ ställningen före draget
}
}
}
int main() {
int i;
char buf[100];
for(i=0;i<10;i++) p[i]=i%2;
for(i=10;i<L;i++) p[i]=-1;
scanf("%s", buf);
for(i=0;i<L;i++) f[i]=(buf[i]=='.')?-1:(buf[i]=='A')?0:1;
min=7; //Detta gör att vi aldrig söker efter lösningar med mer än sex drag
MLX(0,0); //Kör igång rekursionen!
for(i=0;i<min;i++) printf("%d ", brad[i]);
printf("\n");
return 0;
}
Här nedan är ett lösningsexempel i Java. Det använder sig av bredden-först-sökning, d.v.s. tar en ställning genererar alla möjliga ställningar som kan genereras ur den ställningen och lägger dem i en kö, plockar en ställning ur kön och gör samma sak med den. Fördelen med detta lösningssätt är att man hittar den kortaste/bästa lösningen först, så man behöver inte testa alla kombinationer. Nackdelen är att metoden kräver en hel del minne.
Dock vet vi att antalet drag som krävs aldrig överstiger 6, vilket utnyttjas i exemplet nedan. Men även om vi inte kommer i närheten av 256 olika ställningar (p.g.a. att många drag är otillåtna), så kommer vi ändå att få för många ställningar för testdata som kräver 6 drag att lösa för datorns minne att klara av. Hur löser vi då detta? Jo med hjälp av en metod som testar huruvida det är lönt att fortsätta generera ställningar ur en given ställning. Men när är det inte lönt att fortsätta? Jo när antalet felaktiga positioner för spelpjäserna inte går att rätta till innan vi kommit upp i 6 drag. Med ett drag kan man max "rätta till" 2 positioner, så om vi t.ex. redan har gjort 4 drag, då har vi 2 drag kvar och om det skulle vara så att det i vår nuvarande ställning skulle finnas fler än 4 olikheter med ställningen vi vill nå, så är problemet omöjligt att lösa på bara 2 drag och därför är det inte lönt att fortsätta.
Det som beskrivits ovan görs i lösningsexemplet med hjälp av metoden isPossible(). Skulle man ta bort den metoden skulle programmet fortfarande fungera utmärkt för tesdata 1 och testdata 2, men för testdata 3 (som kräver 6 drag för att lösa) så skulle vi få OutOfMemoryError.
Lösningsexemplet använder sig dessutom av en char-array för att beskriva spelplanen och en hjälpklass Node för att spara undan en spelställning tillsammans med antalet drag och dragsekvens.
import java.util.*;
public class Senet
{
//Talar om för oss huruvida det specifierade draget är tillåtet eller ej.
public static boolean isValidMove(char [] current, int from, int to)
{
if(to>14) //Storleken är ju alltid 15 på arrayen, så vi kan göra sådana här antaganden.
{
return false;
}
else if(current[to]=='.')
{
return true;
}
else
{
if(current[from]=='A')
{
if(current[to]=='A') return false;
if(to==14)
{
if(current[to-1]=='A' || current[to-1]=='.') return true;
}
else
{
if( (current[to-1]=='A'||current[to-1]=='.') && (current[to+1]=='A'||current[to+1]=='.') ) return true;
}
}
else
{
if(current[to]=='B') return false;
if(to==14)
{
if(current[to-1]=='B' || current[to-1]=='.') return true;
}
else
{
if( (current[to-1]=='B'||current[to-1]=='.') && (current[to+1]=='B'||current[to+1]=='.') ) return true;
}
}
}
return false;
}
//Flyttar en pjäs.
public static void move(char [] current, int from, int to)
{
char tmp = current[to];
current[to] = current[from];
current[from] = tmp;
}
//Metod för att hitta positionerna för spelarens spelpjäser på brädet.
public static int [] findPositions(char [] current, char player)
{
int [] positions = new int [5]; //Man har ju alltid 5 pjäser.
int j = 0;
for(int i = 0; i<15; i++)
{
if(current[i]==player)
{
positions[j] = i;
if(j>=4) break;
else j++;
}
}
return positions;
}
//Retunerar huruvida det är möjligt att lösa problemet innan vi kommer upp i 6 drag.
public static boolean isPossible(char [] current, char [] goaler, int moves)
{
//Har man t.ex. gjort 1 drag så har man följaktligen 5 drag på sig att nå målet, vilket tillåter 10 felaktiga positioner.
int limit = 2*(6-moves); //Felgräns.
int wrongs = 0; //Antalet felaktiga positioner.
for(int i = 0; i<15; i++)
{
if(current[i]!=goaler[i]) wrongs++;
if(wrongs>limit) return false;
}
return true;
}
public static void main(String [] klein)
{
/*** Inläsning ***/
Scanner scan = new Scanner(System.in);
//Vår utgångsställning.
String start = "ABABABABAB.....";
char [] starter = start.toCharArray();
//Ställningen vi eftersträvar att nå.
System.out.print("Ställning: ");
String goal = scan.next();
char [] goaler = goal.toCharArray();
/******************/
//Information om dragen som ledde fram till vår önskade ställning. Vi initierar den så att inte kompilatorn klagar.
Node winner = new Node(starter, 0, "", 'A');
//Kön som vi ska använda för vår bredden-först-sökning.
LinkedList <Node> bfs = new LinkedList <Node> ();
//Stoppar startpositionen på kön, där inga drag gjorts och det är spelare A:s tur att göra ett drag.
bfs.add( new Node(starter, 0, "", 'A') );
//Vi kör på så länge vi behagar. (solve: är bara en så kallad etikett, den gör inget magiskt.)
solve: while(true)
{
//Plockar den översta spelställningen från kön.
Node current = bfs.remove();
//Hittar alla spelpjäser till den spelare som ska slå "tärningen".
int [] positions = findPositions(current.state, current.player);
//Vi ska testa att flytta på alla 5 spelpjäserna.
for(int i = 0; i<positions.length; i++)
{
//Vi kan flytta varje pjäs 1-5 steg åt höger.
for(int j = 1; j<=5; j++)
{
//Är detta drag tillåtet?
if( isValidMove(current.state, positions[i], positions[i]+j) )
{
//Vanlig tilldelning skulle bara ge en referens, vi vill ha en kopia av ställningen.
char [] copy = Arrays.copyOfRange(current.state, 0, 15);
//Gör det tillåtna draget.
move(copy, positions[i], positions[i]+j);
//Om det var A som gjorde draget, så är det Bs tur nästa gång.
char nextPlayer = (current.player=='A') ? 'B' : 'A';
//Skapar en ny spelställning med information om den.
Node newState = new Node(copy, current.turn+1, current.moves+j+" ", nextPlayer);
//Om den är likadan som vårt mål, så kan vi avsluta.
if(Arrays.equals(newState.state, goaler))
{
winner = newState;
//Ja det är otroligt fult att använda etiketter, men tycker du att koden i övrigt ser snygg ut?
break solve; //Vi hoppar ut ur while-loopen.
}
else //Annars lägger vi den på kön.
{
//Om vi inte kan nå målet före/på drag 6, så finns det ingen anledning att spara ställningen.
if( isPossible(newState.state, goaler, newState.turn) ) bfs.add(newState);
}
}
}
}
}
//Skriver ut dragsekvensen som ledde till den önskade ställningen.
System.out.println("Dragsekvens: " + winner.moves);
}
}
class Node
{
//Spelställningen.
char [] state;
//Antal drag som gjorts för att nå ställningen.
int turn;
//Vilka dragen var.
String moves;
//Vems tur det är.
char player;
public Node(char [] state, int turn, String moves, char player)
{
this.state = state;
this.turn = turn;
this.moves = moves;
this.player = player;
}
}