Tävlingsprogrammering/Uppgifter/Solitär

Solitär

Solitär är ett franskt enpersonsspel som spelas på ett bräde med ett rutnät av gropar där det i varje grop kan ligga en kula. I varje drag väljer man en kula och flyttar två steg, antingen uppåt, neråt, åt höger eller åt vänster. För att draget ska vara godkänt krävs att gropen där kulan hamnar är tom och att det i den mellanliggande gropen finns en kula. Den kula som därmed blir “överhoppad” tas bort. Exempel på drag visas i figuren ovan.

Orginalversionen spelas på ett bräde med 37 hål och 36 kulor, och det går att utföra 35 drag så att det bara blir en kula kvar. I den här uppgiften är brädet ett obegränsat rutnät och kulorna kan vara utplacerade hur som helst. Skriv ett program som beräknar det minsta antalet kvarvarande kulor som kan uppnås från en given utgångsställning.

På första raden i filen solitar.dat står ett heltal N : antalet kulor (minst 2 och högst 10). Därefter följer N rader med två heltal på varje rad separerade med blanksteg, koordinater (x och y ) för varje kula. Alla kulor har olika koordinater och från början ligger dessa i intervallet 0..9 (men detta behöver inte gälla när kulorna flyttats). Programmet ska skriva ut det minsta antalet kulor som kan uppnås efter en serie godkända drag.

Exempel: Filen solitar.dat med innehållet

7 
2 2 
2 3 
2 1 
1 2 
3 2 
4 2 
6 3 

ska ge svaret

Minsta antal kulor: 2

Lösning

Detta är ett typexempel på problem som enklast löses genom en rekursiv funktion. Funktionen testar att göra alla möjliga förstadrag 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 en tidsåtgång som växer exponentiellt med antalet drag, men några tester räcker för att förvissa sig om att med 10 kulor blir lösningen ändå tillräckligt snabb. Om man är lat behöver man inte ens skapa en "karta" över brädet utan man kan kosta på sig att söka igenom listan över koordinater varje gång.

Lösningsexempel i C:

#include <stdio.h>

int n,x[20],y[20],borta[20],min;

void MLX(int kvar) {
  int xx,yy,i,j,k,nx,ny;
  if(kvar<min) min=kvar;    //Har vi funnit en bästa lösning?
  for(i=0;i<n;i++) if(!borta[i]) {       //Testa alla par av   
      for(j=0;j<n;j++) if(!borta[j]) {   //icke borttagna kulor
          xx=x[j]-x[i];
          yy=y[j]-y[i];
          if(xx*xx+yy*yy==1) {    //Ligger de bredvid varandra?
            nx=x[i]+2*xx;       //Vilken blir i så fall målgropen för hoppet?
            ny=y[i]+2*yy;
            for(k=0;k<n;k++) if(!borta[k] && x[k]==nx && y[k]==ny) break;  //Kolla så att denna är tom
            if(k==n) {
              borta[j]=1;   //Ta bort den överhoppade kulan och ändra koordinater för hoppkulan
              x[i]=nx;  
              y[i]=ny;
              MLX(kvar-1);   //Rekursera från den nya ställningen
              x[i]-=2*xx;    //Vi backtrackar - sätt tillbaka kulan och återställ koordinaterna
              y[i]-=2*yy;
              borta[j]=0;  
            }
          }
        }
    }
}
      
int main(){
  int i;
  scanf("%d", &n);
  for(i=0;i<n;i++) {
    scanf("%d %d", &x[i],&y[i]);
    borta[i]=0;
  }
  min=n; 
  MLX(n);
  printf("%d\n", min);
  return 0;
}

Ett lösningsexempel i Java där vi har en "matris" som får representera spelplanen där vi flyttar omkring kulorna. Det går att göra en hel del optimeringar i programmet, men det behövs inte, eftersom vi ändå klarar tidsgränsen med råge då högsta antalet kulor aldrig är fler än 10.

import java.util.*;
import java.io.*;
import java.awt.*; //Så att vi får tillgång till klassen Point.

public class Solitar
{
	//Vår spelplan.
	static boolean [][] spelplan;

	//Minsta antalet kulor som blir över.
	static int min = 11;

	//Vår rekursiva funktion som testar alla drag och löser problemet.
	//antal: Hur många kulor vi har för stunden.
	public static void rek(int antal)
	{
		//Kulornas koordinater.
		Point [] positions = findPositions(antal);

		//Går igenom alla kulor.
		for(int i = 0; i<antal; i++)
		{
			//Testar varje tillåtet drag med kulan.
			for(int j = 1; j<5; j++)
			{
				//Om draget är tillåtet.
				if(isValid(positions[i], j))
				{
					//Gör draget.
					move(positions[i], j);

					//Testar alla drag utifrån den nya ställningen
					// som har en kula mindre.
					rek(antal-1);

					//Är ju inte säkert att det här var det optimala draget.
					undoMove(positions[i], j);
				}
			}
		}

		//Hit kommer vi om vi gjort alla tillåtna drag.
		//Om antalet kulor vi har är färre än minsta, så ska detta antal vara minst.
		if(antal<min) min = antal;
	}

	//Hittar alla kulors koordinater på spelplanen.
	//antal: Antalet kulor som ska hittas.
	public static Point [] findPositions(int antal)
	{
		//Koordinaterna.
		Point [] positions = new Point [antal];

		//Index som håller reda på var vi ska spara dem.
		int index = 0;

		for(int i = 0; i<50; i++) //y
		{
			for(int j = 0; j<50; j++) //x
			{
				//Om vi hittat en kula.
				if(spelplan[i][j])
				{
					//Så sparar vi dess position.
					positions[index] = new Point(j, i);
					index++;
				}
			}
		}

		return positions;
	}

	//Talar om huruvida draget är tillåtet eller ej.
	//p: Punkten vi ska flytta kulan ifrån.
	//type: Vilken typ av förflyttning det rör sig om.
	//      1 = upp, 2 = höger, 3 = ner, 4 = vänster.
	public static boolean isValid(Point p, int type)
	{
		int x = p.x;
		int y = p.y;

		if(type==1) //Upp
		{
			return (spelplan[y+1][x] && !spelplan[y+2][x]);
		}
		else if(type==2) //Höger
		{
			return (spelplan[y][x+1] && !spelplan[y][x+2]);
		}
		else if(type==3) //Ner
		{
			return (spelplan[y-1][x] && !spelplan[y-2][x]);
		}
		else //Vänster
		{
			return (spelplan[y][x-1] && !spelplan[y][x-2]);
		}
	}

	//Flyttar kulan från positionen p med det av type angivna draget.
	public static void move(Point p, int type)
	{
		int x = p.x;
		int y = p.y;

		if(type==1) //Upp
		{
			//Gropen vår kula lämnar.
			spelplan[y][x] = false;

			//Kulan som vi hoppar över försvinner.
			spelplan[y+1][x] = false;

			//Gropen där vi landar hamnar vår kula.
			spelplan[y+2][x] = true;
		}
		else if(type==2) //Höger
		{
			spelplan[y][x] = false;
			spelplan[y][x+1] = false;
			spelplan[y][x+2] = true;
		}
		else if(type==3) //Ner
		{
			spelplan[y][x] = false;
			spelplan[y-1][x] = false;
			spelplan[y-2][x] = true;
		}
		else //Vänster
		{
			spelplan[y][x] = false;
			spelplan[y][x-1] = false;
			spelplan[y][x-2] = true;
		}
	}

	//Nollställer en viss handling som skedde från punkten p av slaget type.
	public static void undoMove(Point p, int type)
	{
		int x = p.x;
		int y = p.y;

		if(type==1) //Upp
		{
			//Härifrån flyttade vi kulan. Vi flyttar tillbaks dit.
			spelplan[y][x] = true;

			//Kulan som vi hoppade över kommer tillbaka.
			spelplan[y+1][x] = true;

			//Gropen vi hoppade till lämnar vi.
			spelplan[y+2][x] = false;
		}
		else if(type==2) //Höger
		{
			spelplan[y][x] = true;
			spelplan[y][x+1] = true;
			spelplan[y][x+2] = false;
		}
		else if(type==3) //Ner
		{
			spelplan[y][x] = true;
			spelplan[y-1][x] = true;
			spelplan[y-2][x] = false;
		}
		else //Vänster
		{
			spelplan[y][x] = true;
			spelplan[y][x-1] = true;
			spelplan[y][x-2] = false;
		}
	}

	//Orka fånga exceptions. Vi är lata och säkra på vår sak.
	public static void main(String [] klein) throws FileNotFoundException
	{
		//Vi ska läsa av filen solitar.dat i mappen/katalogen data.
		Scanner scan = new Scanner(new File("data\\solitar.dat"));

		//Vår spelplan, 50x50 räcker gott och väl som storlek.
		spelplan = new boolean [50][50];

		//Antalet kulor.
		int antal = scan.nextInt();

		//Läser in vardera kulas koordinater.
		for(int i = 0; i<antal; i++)
		{
			int x = scan.nextInt();
			int y = scan.nextInt();

			//Om vi ska ha ett obegränsat rutnät och koordinaten
			// från början är t.ex. (0,0) och vi vill flytta kulan
			// åt vänster, så ska vi ju kunna det. Därför får vi
			// flytta allas position ungefär till mitten av spelplanen.
			// Kulornas relativa position sinsemellan kommer dock vara densamma.
			spelplan[y+20][x+20] = true;
		}

		//Nu ska vi hitta svaret.
		rek(antal);

		//Skriver ut svaret.
		System.out.println("Minsta antalet kulor: " + min);
	}
}

Lösning i Haskell.

-- Solitär
module Main where
import IO
import Data.List

main = do {
	ih <- openFile "solitar.dat" ReadMode;
	content <- hGetContents ih;
	
	points <- return $ map ((\[x,y] -> (x,y)).(map read).words) $ tail $ lines content;
	
	putStrLn $ "Minsta antal kulor: " ++ (show $ play points);
	
	hClose(ih)
}

play :: [(Int,Int)] -> Int
play set = if (new==[]) then (length set) else (minimum $ map play new)
	where
	new = mv1++mv2++mv3++mv4
	mv1 = [(a+2,b):(delete (a+1,b) (delete x set)) | x@(a,b) <- set, elem (a+1,b) set, notElem (a+2,b) set]
	mv2 = [(a-2,b):(delete (a-1,b) (delete x set)) | x@(a,b) <- set, elem (a-1,b) set, notElem (a-2,b) set]
	mv3 = [(a,b+2):(delete (a,b+1) (delete x set)) | x@(a,b) <- set, elem (a,b+1) set, notElem (a,b+2) set]
	mv4 = [(a,b-2):(delete (a,b-1) (delete x set)) | x@(a,b) <- set, elem (a,b-1) set, notElem (a,b-2) set]