(UVA) 11195 - Another n-Queen Problem - Solução

Esta solução resolve o problema, mas excede o tempo limite estabelecido.
Não foi aceito por exceder o tempo limite.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main processando = new Main();
        processando.processa();
       
        System.exit(0);
    }

    int funcao (int[][] matriz, int tamanho, int coluna, int[] vetorConfereLinha, int[] vetorConfereColuna, int[] vetorDiagonal1, int[] vetorDiagonal2) {
        if (coluna == tamanho) { // viu tudo - conseguiu colocar rainha em todas as colunas
            return 1;
        }
       
        int resposta = 0;

        for (int i = 0; i < tamanho; i++) {
            int indice1 = i+coluna;
            int indice2 = i+tamanho-coluna-1;
            if (vetorConfereLinha[i] > 0 || vetorConfereColuna[coluna] > 0 || vetorDiagonal1[indice1] > 0 || vetorDiagonal2[indice2] > 0 || matriz[i][coluna] > 0) {
                continue;
            }
           
            vetorConfereLinha[i] += 1;
            vetorConfereColuna[coluna] += 1;
            vetorDiagonal1[indice1] += 1;
            vetorDiagonal2[indice2] += 1;
           
            resposta += funcao(matriz, tamanho, coluna+1, vetorConfereLinha, vetorConfereColuna, vetorDiagonal1, vetorDiagonal2);
           
            vetorConfereLinha[i] -= 1;
            vetorConfereColuna[coluna] -= 1;
            vetorDiagonal1[indice1] -= 1;
            vetorDiagonal2[indice2] -= 1;
        }
               
        return resposta;
    }
   
    void processa() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = "";
        line = br.readLine();
        StringTokenizer tokenizer = new StringTokenizer(line);
        int tamanho = Integer.valueOf(tokenizer.nextToken());
       
        int contaCasos = 0;
        while (tamanho != 0) {
            contaCasos++;
           
            int[][] matriz = new int[tamanho][tamanho];

            for (int i = 0; i < tamanho; i++) {
                line = br.readLine();
                for (int j = 0; j < tamanho; j++) {
                    char lido = line.charAt(j);
                    if (lido == '*') {
                        matriz[i][j] = 1;
                    }
                    else if (lido == '.') {
                        matriz[i][j] = 0;
                    }
                }
            }
           
            int[] vetorLinha = new int[tamanho];
            int[] vetorColuna = new int[tamanho];
            int[] vetorDiagonal1 = new int[2*tamanho];
            int[] vetorDiagonal2 = new int[2*tamanho];
            int resposta = funcao(matriz, tamanho, 0, vetorLinha, vetorColuna, vetorDiagonal1, vetorDiagonal2);
                   
            bw.write("Case " + contaCasos + ": " + resposta + "\n");
           
            line = br.readLine();
            tokenizer = new StringTokenizer(line);
            tamanho = Integer.valueOf(tokenizer.nextToken());
        }
       
        bw.flush();
        bw.close();           
        return;
    }
}