Tävlingsprogrammering/Uppgifter/Nokiaspel
Nokiaspel
FIGUR 4. Till vänster ser vi en av många startmöjligheter. I mitten visas hur de fyra 2 × 2-
kvadraterna kan roteras. Till höger visas målet.
I flera av Nokias mobiltelefoner finns detta förströelsespel eller pussel. Pusslet går ut på att från ett givet utgångsläge, som till exempel till vänster i figur 4, nå fram till ordning och reda som till höger. I varje ställning finns åtta möjliga drag. Varje liten 2 × 2-kvadrat kan vridas 90◦ medurs eller moturs i taget. Om man skulle göra fyra drag i följd med samma kvadrat i samma riktning skulle man vara tillbaka vid utgångsställningen.
Vi har undersökt att det aldrig behövs fler än 11 drag för att nå målet från vilken utgångsställning som helst. Din uppgift är att skriva ett program som tar emot en ställning och som bestämmer hur många drag den minst kräver för att nå målet. Ställningen (avläst rad för rad) ges till programmet som en sträng innehållande varje siffra i intervallet 1...9 exakt en gång.
Körningsexempel:
Ställning ? 123456897 Denna ställning kräver 6 drag
Bedömning: En effektiv lösning av denna uppgift kan ge tre poäng (övriga uppgifter ger maximalt två poäng). En lösning som klarar alla ställningar vilka kräver högst 8 drag belönas med två poäng.
Lösning
redigeraDetta är ett typiskt "sökningsproblem", ganska vanligt förekommande på programmeringsolympiaden. Typiskt så finns det en startposition och en slutposition som det gäller att uppnå med så få "drag" som möjligt. Hur svårt ett sökningsproblem är beror inte så mycket på hur dragen ser ut, utan i första hand på hur många "tillstånd" som finns, d.v.s. hur många olika spelpositioner som kan uppstå totalt. Om antalet tillstånd är mindre än vad man får plats med i minnet (i storleksordningen en miljon), går det alltid att lösa problemet effektivt med s.k. bredden-först-sökning (BFS). Denna sökning bygger på två principer, dels att man aldrig går till samma tillstånd flera gånger (man sparar var man har varit), och dels att man besöker tillstånden i "avståndsordning", d.v.s. först besöker man alla tillstånd som kan nås med ett drag från startpositionen, därefter alla med två drag o.s.v. Detta görs genom att lägga varje nyhittad position sist i en kö, medan man behandlar positionerna i kön framifrån. Genom denna procedur är man garanterad att hitta den kortaste vägen till slutpositionen, och tidsåtgången är jämförbar med antalet tillstånd.
Antalet tillstånd i detta problem är 9! = 362880, så det bör gå att lösa med BFS. Det som krånglar till saken är att man för att använda BFS måste kunna översätta varje position till ett heltal för att spara om man har varit där innan. Om man, vilket ofta är smidigt, också vill använda detta heltal för att beskriva positionerna i kön behövs även den omvända funktionen som omvandlar från heltalet till positionen. I detta problem kan ju varje position beskrivas med nio tal i intervallet 1..9. Det enklaste vore därför att välja en funktion som betraktar talen som siffror i ett nio-siffrigt tal i basen nio och bara översätter det till ett vanligt tal. Tyvärr spänner funktionsvärdena då över ett intervall på 9^9 = 387 miljoner, vilket är för mycket för att ha i en vanlig array, och dessutom väldigt onödigt eftersom endast ungefär en tusendel av dessa värden motsvarar giltiga positioner. Visserligen finns det i många språk inbyggda datastrukturer för att hantera sådana bekymmer (t.ex. map i C++), men det kan ändå vara trevligt att se hur man löser det för hand.
Anledningen till att den enkla funktionen är ineffektiv är lätt att förstå. Den första rutan kan ju innehålla vilken som helst av 9 siffror, så där finns ingenting att spara in på. Men den andra rutan kan ju bara innehålla en av 8 siffror, eftersom den inte kan innehålla samma siffra som den andra. Därför kan man skapa en ny positionsbeskrivning (pp i lösningen nedan) där man för varje siffra sparar dess (0-baserade) placering bland de siffror som ännu inte har använts. Detta gör att pp[0] kan anta värden i intervallet 0..8, pp[0] i intervallet 0..7, o.s.v. ända till pp[8] som alltid är 0 eftersom det inte finns några alternativ för vad den sista rutan ska innehålla. Denna pp-array (eller snarare i omvänd ordning) kan därför betraktas som ett tal där sista siffran som vanligt står för 1, näst sista för 9 (som i 9-basen), nästa för 8*9, nästa för 7*8*9 o.s.v. Fördelen med detta är att alla funktionsvärdena ligger i intervallet 0..362879, så man har inte slösat någon plats alls. Det finns många olika sätt att implementera det hela, det viktiga är att den omvända funktionen omvandlar tillbaka till precis samma position.
#include <stdio.h>
int D[4][4]={{0,1,4,3},{1,2,5,4},{3,4,7,6},{4,5,8,7}};
int p[9];
int moves[362880],q[362880];
void move(int m){
int i,k;
if(m<4){
k=p[D[m][0]];
for(i=0;i<3;i++) p[D[m][i]]=p[D[m][i+1]];
p[D[m][3]]=k;
}
else {
m%=4;
k=p[D[m][3]];
for(i=3;i>0;i--) p[D[m][i]]=p[D[m][i-1]];
p[D[m][0]]=k;
}
}
int getpos(){
int tagen[9],pp[9],i,j,pos;
for(i=0;i<9;i++) tagen[i]=0;
for(i=0;i<9;i++) {
for(j=0,pp[i]=0;j<p[i];j++) if(!tagen[j]) pp[i]++;
tagen[p[i]]=1;
}
pos=0;
for(i=8;i>=0;i--) pos=pos*(9-i)+pp[i];
return pos;
}
void setpos(int pos){
int tagen[9],pp[9],i,j;
for(i=0;i<9;i++) {
pp[i]=pos%(9-i);
pos/=(9-i);
}
for(i=0;i<9;i++) tagen[i]=0;
for(i=0;i<9;i++) {
for(j=0;pp[i]>0 || tagen[j];j++) if(!tagen[j]) pp[i]--;
p[i]=j;
tagen[p[i]]=1;
}
}
int main(){
char s[10];
int i,now,next,j,pos;
printf("Ställning ? ");
scanf("%s", s);
for(i=0;i<9;i++){
p[i]=s[i]-'1';
}
for(i=0;i<362880;i++) moves[i]=-1;
q[0]=getpos();
moves[q[0]]=0;
now=0;
next=1;
while(now<next){
setpos(q[now]);
for(i=0;i<9;i++) if(p[i]!=i) break;
if(i==9) {
printf("Denna ställning kräver %d drag.\n",moves[q[now]]);
return 0;
}
for(j=0;j<8;j++) {
move(j);
pos=getpos();
if(moves[pos]==-1){
moves[pos]=moves[q[now]]+1;
q[next++]=pos;
}
move((j+4)%8);
}
now++;
}
return 0;
}
Vill man undvika krånglet med numrering av tillstånden, kan man tillgripa den andra generella sökningsmetoden, djupet-först-sökning (DFS), ofta kallad backtracking. Från en viss ställning gör en rekursiv funktion alla tänkbara drag, och för varje drag anropar den sig själv med den nya ställningen. Resultatet blir att man utforskar alla fortsättningar på ett visst förstadrag innan man utför nästa förstadrag, man söker alltså på djupet istället för på bredden. Då är man naturligtvis inte längre garanterad att hitta den kortaste dragserien till slutpositionen först, utan man måste söka igenom alla olika alternativ och hela tiden hålla reda på det bästa resultatet. Däremot bör man naturligtvis aldrig fortsätta framåt i en dragserie som redan har fler drag än det bästa resultatet hittills. Därför är det viktigt att ha en övre gräns på antalet drag, eftersom man annars kan börja gå runt i loopar och aldrig komma fram till slutpositionen. Om man inte vet någon övre gräns kan man alltid, som i lösningsexemplet nedan, chansa på en övre gräns, köra DFS-lösningen och, om ingen lösning hittas, öka gränsen och köra igen.
I detta fall har man en övre gräns given (11 drag), men utan särskilda optimeringar blir programmet ändå för långsamt. Med vetskapen om att två poäng erhålls om programmet klarar alla fall upp till 8 drag kan man dock helt fräckt sätta ner gränsen till 8 vilket ger ett mycket snabbare program.
#include <stdio.h>
int D[4][4]={{0,1,4,3},{1,2,5,4},{3,4,7,6},{4,5,8,7}};
int p[9],min;
void move(int m){
int i,k;
if(m<4){
k=p[D[m][0]];
for(i=0;i<3;i++) p[D[m][i]]=p[D[m][i+1]];
p[D[m][3]]=k;
}
else {
m%=4;
k=p[D[m][3]];
for(i=3;i>0;i--) p[D[m][i]]=p[D[m][i-1]];
p[D[m][0]]=k;
}
}
void MLX(int nr, int back){
int i,q,pos;
for(i=0;i<9;i++) if(p[i]!=i) break;
if(i==9) min=nr;
if(nr<min-1){
for(q=0;q<8;q++) if(q!=back) {
move(q);
MLX(nr+1,(q+4)%8);
move((q+4)%8);
}
}
}
int main(){
char s[10];
int i;
scanf("%s", s);
for(i=0;i<9;i++){
p[i]=s[i]-'1';
}
min=8;
MLX(0,-1);
printf("Min: %d\n",min);
return 0;
}
Samma program som det innan fast i C#, möjligen lite lättare att läsa Programmet skulle kanske bli lite snabbare om man bytte ut alla byte mot int, men bara den som provar och jämför kommer att få veta. Det varierar nog beroende på vilken processor och CLR man har.
using System;
class Program
{
static byte[,] översättningsmatris = {{0,1,4,3},{1,2,5,4},{3,4,7,6},{4,5,8,7}};
static byte[] spelfält = new byte[9];
static int minsta_rekursion;
static void Flytta(int m)
{
byte i, k;
if(m < 4)
{
k = spelfält[översättningsmatris[m, 0]];
for(i = 0; i < 3; i++)
{
spelfält[översättningsmatris[m,i]] = spelfält[översättningsmatris[m,i+1]];
}
spelfält[översättningsmatris[m,3]] = k;
}
else
{
m %= 4;
k = spelfält[översättningsmatris[m,3]];
for(i = 3; i > 0; i--)
{
spelfält[översättningsmatris[m,i]] = spelfält[översättningsmatris[m,i-1]];
}
spelfält[översättningsmatris[m,0]] = k;
}
}
static void Testa(int rekursionsnivå, int backtrack)
{
byte i, q;
for(i = 0; i < 9; i++)
{
if(spelfält[i] != i) break;
}
if(i == 9)
{
minsta_rekursion = rekursionsnivå;
}
if(rekursionsnivå < minsta_rekursion -1)
{
for(q = 0; q < 8; q++)
{
if(q != backtrack)
{
Flytta(q);
Testa(rekursionsnivå+1, (q+4)%8);
Flytta((q + 4) % 8);
}
}
}
}
static void Main(string[] args)
{
string s = Console.ReadLine();
for (int i = 0; i < 9; i++)
{
spelfält[i] = (byte)(Convert.ToByte(s[i].ToString()) - 1);
}
minsta_rekursion = 8;
Testa(0, 255);
Console.WriteLine("Min: " + minsta_rekursion);
}
}
Om kan vara lättare att skriva, men tänk på att (3 ... 0).each {|n| puts n} kommer inte att skriva något, så se upp i loop nummer två.
#!/usr/bin/env ruby
@translate = [[0,1,4,3],[1,2,5,4],[3,4,7,6],[4,5,8,7]]
@field = Array.new
@n = 8
def test(level, backtrack)
i = 0
for i in 0 ... 9
break unless @field[i] == i
end
@n = level if i == 8
if level < @n - 1
for q in 0 ... 8
unless q == backtrack
move(q)
test(level + 1, (q + 4) % 8)
move((q + 4) % 8)
end
end
end
end
def move(m)
if m < 4
k = @field[@translate[m][0]]
for i in 0 ... 3
@field[@translate[m][i]] = @field[@translate[m][i + 1]]
end
@field[@translate[m][3]] = k
else
m %= 4
k = @field[@translate[m][3]]
for i in 0 ... 3
@field[@translate[m][3 - i]] = @field[@translate[m][ 2 - i]]
end
@field[@translate[m][0]] = k
end
end
s = gets
for i in 0 ... 9
@field[i] = s[i,1].to_i - 1
end
test(0, -1)
puts "Min: #{@n}"
En lösning i Pascal, programmet allokerar minnet för de besökta ställningarna allt eftersom, vilket ledar till hanteringen tar tid och programmet är knappt på gränsen för att klara de högre djupen. Det är även en iterativ djupet först sökning där den lagrar besökta ställningar, vilket innebär att den kommer 'ungefär' besöka ställningarna i samma ordning som en bredden först sökning.
Man kan dra som slutsats att det inte var klokt att allokera minnet allt eftersom. För vi kan anta att varje dator har 32MB i minne, och det finns 9! ställningar. 32'000'000>>362'880. Plus att programmet kommer allokera alla ställningar ifall den får söka fullt ut. Så då har den till och med allokerat mer minne än en lösning med statiskt allokerat minne.
program NokiaSpel;
uses math;
type
TSifferArray = array['1'..'9'] of pointer;
PSifferArray = ^TSifferArray;
TSlut = integer;
PSlut = ^TSlut;
var
SifferArray: TSifferArray;
AtSifferArray:PSifferArray;
Stallning: string[9];
tempstallning:string[9];
djup:integer;
djupforsok:integer;
procedure nollstall(var SA:TSifferArray);
var
a:char;
begin
for a:='1' to '9' do
SA[a]:=nil;
end;
procedure expandera(var p:PSifferArray);
begin
new(p);
nollstall(p^);
end;
function besok(d:integer; var PSA:PSifferArray):integer;
begin
if d<9 then begin
if (PSA=nil) then
expandera(PSA);
result:=besok(d+1,PSA^[Stallning[d]])
end
else begin //ifall d=9
if (PSA=nil) then begin
new(PSlut(PSA));
PSlut(PSA)^:=-100;
end;
result:= PSlut(PSA)^;
PSlut(PSA)^:=max(PSlut(PSA)^,djupforsok-djup); //Antal drag man minst "ska" ha över att söka med
end;
end;
procedure flytta(drag:integer); //mellan 0..7
var
x,y:integer;
ch:char;
begin
x:=drag mod 2;
y:=(drag div 2) mod 2;
if drag<4 then begin //medsols
ch:=Stallning[x+y*3+1];
Stallning[x+y*3+1]:=Stallning[x+(y+1)*3+1];
Stallning[x+(y+1)*3+1]:=Stallning[(x+1)+(y+1)*3+1];
Stallning[(x+1)+(y+1)*3+1]:=Stallning[(x+1)+y*3+1];
Stallning[(x+1)+y*3+1]:=ch;
end
else begin
ch:=Stallning[x+y*3+1];
Stallning[x+y*3+1]:=Stallning[(x+1)+y*3+1];
Stallning[(x+1)+y*3+1]:=Stallning[(x+1)+(y+1)*3+1];
Stallning[(x+1)+(y+1)*3+1]:=Stallning[x+(y+1)*3+1];
Stallning[x+(y+1)*3+1]:=ch;
end;
end;
procedure sok;
var a:integer;
begin
a:=besok(1,AtSifferArray);
if a>=(djupforsok-djup) then
begin
exit; //Ifall man har redan sökt nuvarande ställning med minst samma antal drag kvar att söka med
end;
if (djup)<djupforsok then begin
inc(djup);
for a:=0 to 7 do begin
flytta(a); // flytta
sok; //rekursera
flytta((a+4) mod 8); //flytta tillbaka (backtracking)
end;
dec(djup);
end;
end;
begin
write('Ställning ? ');
readln(stallning);
nollstall(SifferArray);
tempstallning:=Stallning;
AtSifferArray:=@SifferArray;
for djupforsok:=1 to 11 do begin
djup:=0;
sok;
Stallning:='123456789'; //Vi kollar ifall vi råkat stöta på den rätta lösningen
djup:=+100; //så att man inte sabbar strukturen (se slutet av funktionen besok)
if besok(1,AtSifferArray)>=0 then begin
writeln('Denna ställning kräver ',djupforsok,' drag');
break;
end;
Stallning:=tempstallning;
end;
readln;
end.
En lösning i Java som använder sig av bredden-först-sökning. Programmet beskriver spelplanen med en char-array där index 0 svarar mot platsen där siffran 1 normalt ska befinna sig, index 1 svarar mot 2, index 2 mot 3, index 3 mot 4, osv. Sedan använder sig programmet av en hjälpklass State. Programmet är inte helt optimerat t.ex. görs massa konverteringar mellan en char-array och en String för att enkelt kunna markera en position som besökt i ett HashSet. Men det gör inte så mycket när vi ändå klarar exempel som kräver 11 drag på ca 4 sek på en modern dator.
import java.util.*;
public class Nokia
{
//Metod för att rotera de fyra rutorna i ett givet hörn.
/*
state: Spelplanen i vilken vi ska rotera rutor.
corner: Vilket hörn i vilka de fyra rutorna ska rotera.
1=övre vänstra, 2=övre högra, 3=nedre vänstra, osv
clockwise: Om vi ska rotera medsols eller motsols.
*/
public static void rotate(char [] state, int corner, boolean clockwise)
{
//Bara en temporär mellanlagrings variabel.
char tmp;
//Indexet för vardera fyr-rutas övre vänstra hörn/ruta.
int i;
if(corner==1) i = 0;
else if(corner==2) i = 1;
else if(corner==3) i = 3;
else i = 4;
if(clockwise)
{
tmp = state[i];
state[i] = state[i+3];
state[i+3] = state[i+4];
state[i+4] = state[i+1];
state[i+1] = tmp;
}
else
{
tmp = state[i];
state[i] = state[i+1];
state[i+1] = state[i+4];
state[i+4] = state[i+3];
state[i+3] = tmp;
}
}
public static void main(String [] klein)
{
/*** Inläsning ***/
Scanner scan = new Scanner(System.in);
System.out.print("Ställning: ");
String start = scan.next();
char [] starter = start.toCharArray();
//Dit vi vill nå.
String goal = "123456789";
char [] goaler = goal.toCharArray();
/******************/
//Antalet drag som krävs.
int requiredMoves = 0;
//Kön som vi ska använda för vår bredden-först-sökning.
LinkedList <State> bfs = new LinkedList <State> ();
//Sparar de ställningar vi redan besökt.
//Vi får använda String istället för char[], eftersom den senare
// inte fungerar så bra tillsammans med HashSet.
HashSet <String> visited = new HashSet <String> ();
//Lägger till startpositionen på kön och markerar den som besökt.
bfs.add( new State(starter, 0) );
visited.add( new String(starter) );
//Vi kör på tills jag säger stopp (vilket jag gör när lösning är funnen).
solve: while(true)
{
State current = bfs.remove();
//Roterar medsols.
for(int i = 1; i<=4; i++)
{
//Vanlig tilldelning skulle bara ge en referens, vi vill ha en kopia av ställningen.
char [] copy = Arrays.copyOfRange(current.state, 0, 9);
//Roterar ett givet hörn.
rotate(copy, i, true);
//Skapar en ny spelställning med information om den.
State newState = new State(copy, current.moves+1);
//Om den är likadan som vårt mål, så kan vi avsluta.
if(Arrays.equals(newState.state, goaler))
{
requiredMoves = newState.moves;
//Ja det är otroligt fult att använda etiketter.
break solve; //Vi hoppar ut ur while-loopen.
}
else //Annars lägger vi den på kön.
{
//Skapar en sträng av vår char-array.
String s = new String(newState.state);
//Om vi redan besökt ställningen så är vi inne på fel spår.
if(!visited.contains(s))
{
bfs.add(newState);
visited.add(s);
}
}
}
//Roterar motsols.
for(int i = 1; i<=4; i++)
{
//Vanlig tilldelning skulle bara ge en referens, vi vill ha en kopia av ställningen.
char [] copy = Arrays.copyOfRange(current.state, 0, 9);
//Roterar ett givet hörn.
rotate(copy, i, false);
//Skapar en ny spelställning med information om den.
State newState = new State(copy, current.moves+1);
//Om den är likadan som vårt mål, så kan vi avsluta.
if(Arrays.equals(newState.state, goaler))
{
requiredMoves = newState.moves;
//Ja det är otroligt fult att använda etiketter.
break solve; //Vi hoppar ut ur while-loopen.
}
else //Annars lägger vi den på kön.
{
String s = new String(newState.state);
//Om vi redan besökt ställningen så är vi inne på fel spår.
if(!visited.contains(s))
{
bfs.add(newState);
visited.add(s);
}
}
}
}
System.out.println("Denna ställning kräver " + requiredMoves + " drag");
}
}
class State
{
//Antalet drag som gjorts.
int moves;
//Hur "spelplanen" ser ut.
char [] state;
public State(char [] state, int moves)
{
this.state = state;
this.moves = moves;
}
}
Här är i stort sett samma program i Java, fast med en djupet-först-sökning. Lösningsexemplet använder sig av en HashMap för att markera uppnådda positioner/ställningar samt hur många drag det tog att nå dem. Denna lösning må vara mer skonsam för datorns minne än ovanstående, men den tar drygt 1 sek mer tid på sig för att lösa exempel som kräver 11 drag på en modern dator.
import java.util.*;
public class NokiaSpel
{
//Antalet drag som krävs.
static int requiredMoves = 12;
//Dit vi vill nå.
static char [] goaler = {'1','2','3','4','5','6','7','8','9'};
//Sparar positioner vi uppnått och hur många drag det tog.
static HashMap <String, Integer> visited = new HashMap <String, Integer> ();
//Vår rekursvia metod som testar alla drag.
/*
current: Hur spelplanen ser ut nu.
moves: Vilket drag vi är på.
*/
public static void rek(char [] current, int moves)
{
//Onödigt att fortsätta.
if(moves>=requiredMoves) return;
//Roterar medsols.
for(int i = 1; i<=4; i++)
{
//Roterar ett givet hörn.
rotate(current, i, true);
//En sträng-representation av char-arrayen.
String s = new String(current);
//Hur många drag som det har krävts att uppnå denna ställning tidigare.
//null om ställningen aldrig tidigare har uppnåtts.
Integer p = visited.get(s);
//Om den är likadan som vårt mål, så kan vi avbryta.
if(Arrays.equals(current, goaler))
{
//Nu är detta antalet minsta drag.
requiredMoves = moves;
//Dock får vi inte glömma att rotera tillbaka, nollställa vår handling.
rotate(current, i, false);
//Avbryt.
return;
}
else if(p!=null && moves>=p) //Om vi redan nått ställningen snabbare.
{
//Egentligen behöver man inte göra någonting här, men detta
// symboliserar bra vad som händer.
//Roterar tillbaka.
rotate(current, i, false);
//Testar nästa hörn istället. (Nästa varv i loopen.)
continue;
}
else
{
//Markerar ställningen som besökt.
visited.put(s, moves);
//Gör nästa drag på ställningen.
rek(current, moves+1);
}
//Vi får inte glömma att nollställa vår handling.
//Eftersom vi denna gång inte jobbar med en kopia,
// utan en referens.
rotate(current, i, false);
}
//Roterar motsols. (Samma gäller här som ovan.)
for(int i = 1; i<=4; i++)
{
//Roterar ett givet hörn.
rotate(current, i, false);
String s = new String(current);
Integer p = visited.get(s);
//Om den är likadan som vårt mål, så kan vi avbryta.
if(Arrays.equals(current, goaler))
{
requiredMoves = moves;
rotate(current, i, true);
return;
}
else if(p!=null && moves>=p)
{
rotate(current, i, true);
continue;
}
else
{
visited.put(s, moves);
rek(current, moves+1);
}
rotate(current, i, true);
}
}
//Metod för att rotera de fyra rutorna i ett givet hörn.
/*
state: Spelplanen i vilken vi ska rotera rutor.
corner: Vilket hörn i vilka de fyra rutorna ska rotera.
1=övre vänstra, 2=övre högra, 3=nedre vänstra, osv
clockwise: Om vi ska rotera medsols eller motsols.
*/
public static void rotate(char [] state, int corner, boolean clockwise)
{
//Bara en temporär mellanlagrings variabel.
char tmp;
//Indexet för vardera fyr-rutas övre vänstra hörn/ruta.
int i;
if(corner==1) i = 0;
else if(corner==2) i = 1;
else if(corner==3) i = 3;
else i = 4;
if(clockwise)
{
tmp = state[i];
state[i] = state[i+3];
state[i+3] = state[i+4];
state[i+4] = state[i+1];
state[i+1] = tmp;
}
else
{
tmp = state[i];
state[i] = state[i+1];
state[i+1] = state[i+4];
state[i+4] = state[i+3];
state[i+3] = tmp;
}
}
public static void main(String [] klein)
{
/*** Inläsning ***/
Scanner scan = new Scanner(System.in);
System.out.print("Ställning: ");
String start = scan.next();
char [] starter = start.toCharArray();
/******************/
//Markerar startpositionen som besökt.
visited.put(start, 0);
//Ifall lösningen skulle kräva 0 drag.
if(Arrays.equals(starter, goaler)) requiredMoves = 0;
//Dags att finna svaret. Vi börjar med drag 1.
rek(starter, 1);
System.out.println("Denna ställning kräver " + requiredMoves + " drag");
}
}