import java.util.*;
class Solution {
int answer = 0;
public int solution(int n) {
for(int i = 0; i < n; i++){
int[][] board = new int[n][n];
dfs(board, 0, i);
}
return answer;
}
void dfs(int[][] board, int row, int col){
for(int i = 0; i < row; i++){
if(board[i][col]!=0) {
return;
}else if(col-(row-i)>=0 && board[i][col-(row-i)]!= 0){
return;
}else if(col+(row-i)<board.length &&board[i][col+(row-i)] != 0){
return;
}
}
if(row==board.length-1){
answer++;
return;
}
for(int i = 0; i < board.length; i++){
if(i!=col && i!=col+1 && i!=col-1){
board[row][col] = 1;
dfs(board, row+1, i);
board[row][col] = 0;
}
}
}
}