Recursive backtracking in Java for solving a crossword, Java

Language: Layout:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Rextester {
    List<Set<String>> words;

public static void main(String[] args) throws IOException {
        Rextester r = new Rextester();
        r.run();
    }

public void run() throws IOException {
        InputStreamReader r = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(r);
        String line = in.readLine();
        int t = Integer.parseInt(line);
        for (int k = 1; k <= t; k++) {
            line = in.readLine();
            String[] parts = line.split(" ");
            int x = Integer.parseInt(parts[0]);
            int y = Integer.parseInt(parts[1]);
            int amount = Integer.parseInt(parts[2]);

char[][] c = new char[y+2][x+2];
            for (int i = 1; i <= y; i++) {
                line = "+" + in.readLine() + "+";
                c[i] = line.toCharArray();
            }
            for (int i = 0; i <= x+1; i++) {
                c[0][i] = '+';
                c[y+1][i] = '+';
            }

words = new ArrayList<>();
            for (int i = 2; i <= 250; i++)
                words.add(new HashSet<String>());
            for (int i = 0; i < amount; i++) {
                line = in.readLine();
                words.get(line.length()).add(line);
            }
            in.readLine();

Stack<Placeholder> placeholders = new Stack<>();
            for (int i = 1; i <= y; i++)
                for (int j = 1; j <= x; j++)
                    if (c[i][j-1] == '+' && c[i][j] == '_' && c[i][j+1] == '_') {
                        int xx = j; int ll = 0;
                        while (c[i][j] == '_') {
                            ll++;
                            j++;
                        }
                        placeholders.push(new Placeholder(xx, i, ll, true));
                    }

for (int j = 1; j <= x; j++)
                for (int i = 1; i <= y; i++)
                    if (c[i-1][j] == '+' && c[i][j] == '_' && c[i+1][j] == '_') {
                        int yy = i; int ll = 0;
                        while (c[i][j] == '_') {
                            ll++;
                            i++;
                        }
                        placeholders.push(new Placeholder(j, yy, ll, false));
                    }

c = solve(c, placeholders);
            System.out.println("Case #" + k + ":");
            for (int i = 1; i <= y; i++) {
                for (int j = 1; j <= x; j++)
                    System.out.print(c[i][j]);
                System.out.println();
            }
            if (k!=t)
                System.out.println();
        }
    }

char[][] solve (char[][] c, Stack<Placeholder> placeholders) {
        if (placeholders.isEmpty())
            return c;

Placeholder pl = placeholders.pop();
        for (String word : words.get(pl.l)) {
            char[][] possibleC = fill(c, word, pl);
            if (possibleC != null) {
                char[][] ret = solve(possibleC, placeholders);
                if (ret != null)
                    return ret;
            }
        }
        return null;
    }

char[][] fill (char[][] c, String word, Placeholder pl) {

if (pl.h) {
            for (int i = pl.x; i < pl.x + pl.l; i++)
                if (c[pl.y][i] != '_' && c[pl.y][i] != word.charAt(i - pl.x))
                    return null;
            for (int i = pl.x; i < pl.x + pl.l; i++)
                c[pl.y][i] = word.charAt(i - pl.x);
            return c;

} else {
            for (int i = pl.y; i < pl.y + pl.l; i++)
                if (c[i][pl.x] != '_' && c[i][pl.x] != word.charAt(i - pl.y))
                    return null;
            for (int i = pl.y; i < pl.y + pl.l; i++)
                c[i][pl.x] = word.charAt(i - pl.y);
            return c;
        }
    }
}

class Placeholder {
    int x, y, l;
    boolean h;
    public Placeholder(int x, int y, int l, boolean h) {
        this.x = x;
        this.y = y;
        this.l = l;
        this.h = h;
    }
}

[ + ] Show input
Compilation time: 0.62 sec, absolute running time: 10.04 sec, cpu time: 0 sec, memory peak: 0 Mb, absolute service time: 10,67 sec