Sokoban: Difference between revisions

=={{header|Java}}==

Translation of [[Sokoban#C++|C++]] via [[Sokoban#D|D]]

{{works with|Java|7}}

<lang java>package sokoban;

import java.util.*;

public class Sokoban {

String destBoard, currBoard;

int playerX, playerY, nCols;

Sokoban(String[] board) {

nCols = board[0].length();

StringBuilder destBuf = new StringBuilder();

StringBuilder currBuf = new StringBuilder();

for (int r = 0; r < board.length; r++) {

for (int c = 0; c < nCols; c++) {

char ch = board[r].charAt(c);

destBuf.append(ch != '$' && ch != '@' ? ch : ' ');

currBuf.append(ch != '.' ? ch : ' ');

if (ch == '@') {

this.playerX = c;

this.playerY = r;

}

}

}

destBoard = destBuf.toString();

currBoard = currBuf.toString();

}

String move(int x, int y, int dx, int dy, String trialBoard) {

int idx = (y + dy) * nCols + x + dx;

if (trialBoard.charAt(idx) != ' ')

return null;

char[] tmp = trialBoard.toCharArray();

tmp[y * nCols + x] = ' ';

tmp[idx] = '@';

return new String(tmp);

}

String push(int x, int y, int dx, int dy, String trialBoard) {

int idx = (y + 2 * dy) * nCols + x + 2 * dx;

if (trialBoard.charAt(idx) != ' ')

return null;

char[] tmp = trialBoard.toCharArray();

tmp[y * nCols + x] = ' '; // where the player was

tmp[(y + dy) * nCols + x + dx] = '@'; // where the player is now

tmp[idx] = '$'; // box has moved

return new String(tmp);

}

boolean isSolved(String trialBoard) {

for (int i = 0; i < trialBoard.length(); i++)

if ((destBoard.charAt(i) == '.') // goal

!= (trialBoard.charAt(i) == '$'))

return false;

return true;

}

String solve() {

class Board {

String cur, sol;

int x, y;

Board(String s1, String s2, int px, int py) {

cur = s1;

sol = s2;

x = px;

y = py;

}

}

char[][] dirLabels = {{'u', 'U'}, {'r', 'R'}, {'d', 'D'}, {'l', 'L'}};

int[][] dirs = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

Set<String> history = new HashSet<>();

LinkedList<Board> open = new LinkedList<>();

history.add(currBoard);

open.add(new Board(currBoard, "", playerX, playerY));

while (!open.isEmpty()) {

Board item = open.poll();

String cur = item.cur;

String sol = item.sol;

int x = item.x;

int y = item.y;

for (int i = 0; i < dirs.length; i++) {

String tmp = cur;

int dx = dirs[i][0];

int dy = dirs[i][1];

// are we standing next to a box?

if (tmp.charAt((y + dy) * nCols + x + dx) == '$') {

// let's see if we can push it

if ((tmp = push(x, y, dx, dy, tmp)) != null) {

// or did we already try this one?

if (!history.contains(tmp)) {

String newSol = sol + dirLabels[i][1];

if (isSolved(tmp))

return newSol;

open.add(new Board(tmp, newSol, x + dx, y + dy));

history.add(tmp);

}

}

// otherwise try change position

} else if ((tmp = move(x, y, dx, dy, tmp)) != null) {

if (!history.contains(tmp)) {

String newSol = sol + dirLabels[i][0];

open.add(new Board(tmp, newSol, x + dx, y + dy));

history.add(tmp);

}

}

}

}

return "No solution";

}

public static void main(String[] a) {

String level = "#######,# #,# #,#. # #,#. $$ #,"

+ "#.$$ #,#.# @#,#######";

System.out.println(new Sokoban(level.split(",")).solve());

}

}</lang>

<pre>ulULLulDDurrrddlULrruLLrrUruLLLulD</pre>