Tävlingsprogrammering/Uppgifter/Sokoban
Sokoban
I spelet Sokoban rör du dig i ett lagerrum indelat i rutor och ska flytta ett antal lå-
dor (som upptar exakt en ruta) från sina startpositioner (S) till sina målpositioner (M).
Följande regler gäller:
- Du (D) kan bara röra sig vänster, höger, upp eller ned i rutnätet, alltså inte diagonalt.
- Du kan flytta en låda endast genom att skjuta den framför dig.
- Endast en låda i taget kan flyttas.
- Du kan inte gå genom lådor eller väggar (#) och inte heller skjuta en låda genom vägg eller annan låda.
- Spelet är löst när alla lådor hamnat på målpositioner. Det spelar ingen roll vilken låda som hamnar på vilken målposition.
Du ska skriva ett program som spelar Sokoban. Programmet ska fråga efter antal rader (högst 5) och antal kolumner (högst 5) och sedan läsa in en karta över lagerrummet där ’.’ betyder tom ruta, ’#’ betyder blockerad ruta (vägg), ’S’ betyder startposition för låda, ’M’ betyder målposition för låda och ’D’ betyder din startposition. Det finns alltid lika många S som M (högst 5 stycken) och det finns alltid exakt ett D. Programmet ska skriva ut en rad med tecken (högst 1000) som beskriver hur du ska röra dig för att uppnå målet (H=höger, V=vänster, U=upp, N=ner). Programmet behöver inte hitta den kortaste dragföljden. I alla testfall kommer det att finnas en dragföljd med högst 20 drag.
Körningsexempel 1
Antal rader: 1 Antal kolumner: 4 Rad 1 ? #MSD Dragföljd: V
Körningsexempel 2
Antal rader: 4 Antal kolumner: 3 Rad 1 ? #.. Rad 2 ? .SD Rad 3 ? .#M Rad 4 ? ... Dragföljd: NNVVUUHUHN
Körningsexempel 3
Antal rader: 3 Antal kolumner: 4 Rad 1 ? .S.M Rad 2 ? ..SD Rad 3 ? MMS. Dragföljd: NVVUVUHHNHNV
Lösning
redigeraSokoban är ett välkänt problem som har bevisats vara NP-svårt. Att det är NP-svårt innebär att det med allra största sannolikhet inte går att skriva en polynomisk lösning till Sokoban, utan man får nöja sig med exponentiella lösningar. Med tanke på detta så passar det ypperligt att indata i detta problem är så pass litet, vi hinner lösa pusslet med en brute force lösning.
Det här problemet är alltså tänkt att vara en övning i brute force-lösningar. Det handlar helt enkelt om att prova alla möjligheter. Man kan se det som att man bygger upp ett träd, där en nod är en spelställning och varje drag leder till en ny nod, barn till den tidigare noden. Det blir snabbt många kombinationer, men indata är litet. Andra sökstrategier som man kan använda:
- Bredden-först-sökning (BFS). Garanterar att man hittar kortaste vägen, vilket inte var ett krav för denna uppgift.
- Djupet-först-sökning (DFS). Vill man lösa pusslet med DFS så passar det nog bra att begränsa sökdjupet till maximallängden på lösningssträngen som var given i uppgiften.
- Iterative deepening DFS. Sök djupare och djupare tills du hittar en lösning. Garanterar att lösningen vi hittar är den kortaste.
Här ger vi några exempel på hur detta problem kan lösas i diverse programmeringsspråk.
Lösning i Python (möjligen något långsam):
import sys
def sqr_id(x):
return x[0]*5 + x[1]
def hash(player,boxes):
hashval = 0
power = 0
retval = sqr_id(player)
for b in boxes:
power = power + 1
retval = retval + sqr_id(b)*(26**power)
return retval
def pointInside(grid,r,c):
return r >= 0 and r < len(grid) and c >= 0 and c < len(grid[0])
# returns tuple (player pos, boxes list)
def getNext(grid,player,boxes,goals,dr,dc):
newR = player[0] + dr;
newC = player[1] + dc;
if not pointInside(grid,newR,newC):
return (player, boxes)
if grid[newR][newC] == '#':
return (player, boxes)
# trying to move into a box, check that square after that is free.
if (newR,newC) in boxes and (newR+dr,newC+dc) not in boxes and pointInside(grid,newR+dr,newC+dc) and grid[newR+dr][newC+dc] == '.':
# ok, move the box!
newBoxes = boxes[:]
newBoxes.remove((newR,newC))
nextBoxPos = (newR+dr,newC+dc)
newBoxes.append(nextBoxPos)
return ((newR,newC),newBoxes)
elif grid[newR][newC] == '.' and (newR,newC) not in boxes:
# empty, just move
return ((newR,newC), boxes[:])
return (player,boxes)
def isDone(boxes, goals):
for b in boxes:
if b not in goals:
return False
return True
def dfs(grid,player, boxes, goals, moves, vis, maxd):
if len(moves) > maxd:
return False
if isDone(boxes,goals):
print moves
return True
if hash(player,boxes) in vis:
return False
vis.add(hash(player,boxes))
#print "now at ", moves
# right
N = getNext(grid,player,boxes,goals,1,0)
H = getNext(grid,player,boxes,goals,0,1)
U = getNext(grid,player,boxes,goals,-1,0)
V = getNext(grid,player,boxes,goals,0,-1)
if dfs(grid, U[0],U[1],goals,moves+"U",vis,maxd): return True
if dfs(grid, N[0],N[1],goals,moves+"N",vis,maxd): return True
if dfs(grid, H[0],H[1],goals,moves+"H",vis,maxd): return True
if dfs(grid, V[0],V[1],goals,moves+"V",vis,maxd): return True
vis.remove(hash(player,boxes))
return False
def solve():
nRows = int(sys.stdin.readline())
nCols = int(sys.stdin.readline())
grid = []
player = (0,0)
boxes = []
goals = []
for i in xrange(nRows):
row = []
line = sys.stdin.readline().strip()
for j in xrange(len(line)):
if line[j] == 'S':
boxes.append((i,j))
if line[j] == 'M':
goals.append((i,j))
if line[j] == 'D':
player = (i,j)
if line[j] == '#':
row.append('#')
else: row.append('.')
grid.append(row)
visited = set()
for i in xrange(20):
if dfs(grid, player, boxes, goals, "", visited, i+1):
break
if __name__ == "__main__":
solve()
En lösning i Java:
package kval13;
import java.util.*;
public class uppg6 {
static int r, c, goalCount;
static boolean[] goals;
static boolean[] blocked;
static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
static char[] mvs = {'U', 'N', 'V', 'H'};
static class Struct {
Integer hashCode = null;
int[] pos;
int me;
char move;
Struct prev = null;
public Struct() {
pos = new int[goalCount];
}
public boolean win() {
for (int i = 0; i < goalCount; i++) if (!goals[pos[i]]) return false;
return true;
}
public List<Struct> moves() {
int rr = me/c;
int cc = me%c;
List<Struct> structs = new ArrayList<>(4);
for (int i = 0; i < 4; i++) {
int nr = rr + dx[i];
int nc = cc + dy[i];
int pr = rr + 2*dx[i];
int pc = cc + 2*dy[i];
if(nr < 0 || nc < 0 || nr >= r || nc >= c) continue;
if(blocked[nr *c + nc]) continue;
int push1 = -1;
boolean push2 = false;
for(int j = 0; j<goalCount; j++){
int hr = pos[j]/c;
int hc = pos[j]%c;
if(hr == pr && hc == pc) push2 = true;
if(hr == nr && hc == nc) push1 = j;
}
if(push1 != -1 && push2) continue;
if(push1 != -1 && (pr < 0 || pc < 0 || pr >= r || pc >= c || blocked[pr * c + pc])) continue;
Struct nstruct = new Struct();
nstruct.prev = this;
nstruct.move = mvs[i];
nstruct.me = nr * c + nc;
for(int j = 0; j<goalCount; j++) nstruct.pos[j] = pos[j];
if(push1 != -1){
nstruct.pos[push1] = pr * c + pc;
Arrays.sort(nstruct.pos);
}
structs.add(nstruct);
}
return structs;
}
@Override
public int hashCode() {
return hashCode != null ? hashCode : (hashCode = 53 * (53 * 5 + Arrays.hashCode(this.pos)) + this.me);
}
@Override
public boolean equals(Object obj) {
final Struct other = (Struct) obj;
if (!Arrays.equals(this.pos, other.pos) || this.me != other.me) return false;
return true;
}
}
static HashMap<Struct, Integer> dist = new HashMap<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
r = sc.nextInt();
c = sc.nextInt();
String[] map = new String[r];
int mypos = -1;
List<Integer> goalss = new ArrayList<Integer>();
blocked = new boolean[r*c];
goals = new boolean[r*c];
for (int i = 0; i < r; i++) {
map[i] = sc.next();
for (int j = 0; j < c; j++) {
char ch = map[i].charAt(j);
if (ch == '#') blocked[i * c + j] = true;
if (ch == 'M') goals[i * c + j] = true;
if (ch == 'D') mypos = i * c + j;
if (ch == 'S') {
goalss.add(i * c + j);
goalCount++;
}
}
}
Struct base = new Struct();
base.me = mypos;
for (int i = 0; i < goalCount; i++) base.pos[i] = goalss.get(i);
Queue<Struct> structs = new LinkedList<>();
structs.add(base);
dist.put(base, 0);
while(!structs.isEmpty()){
Struct next = structs.poll();
int d = dist.get(next);
if(next.win()){
System.out.println("Hittade i "+d+" drag");
StringBuffer ans = new StringBuffer();
while(next != null){
ans.append(next.move);
next = next.prev;
}
System.out.println(ans.reverse().toString());
break;
}
for(Struct move : next.moves()){
if(!dist.containsKey(move)){
structs.add(move);
dist.put(move, d + 1);
}
}
}
}
}