private boolean dfs(char[][] board, int pos)
    {
        int n = board.length;
        if (pos == n*n)
        {
            return true;
        }
        int x = pos / n;
        int y = pos % n;
        if (board[x][y] == '.')
        {
            for (char c='1'; c<='9'; ++c)
            {
                board[x][y] = c;
                if (validate(board, x, y) && dfs(board, pos+1))
                {
                    return true;
                }
                board[x][y] = '.';
            }
        }
        else
        {
            if (dfs(board, pos+1))
            {
                return true;
            }
        }
        return false;
    }