Yes, you can! The one caveat is that whenever you have the characters use magic to solve a problem, as opposed to having characters having to solve problems caused by magic, you risk writing a deus ex machina.
Like Cort Ammon's answer, I'm going to recommend reading Sanderson's First Law of Magic. However, I disagree strongly with Cort Ammon's claim, "Sanderson's First Law of Magic suggests it is remarkably difficult to use such a rule-less magic in a book."
If you read the article on Sanderson's First Law, Brandon Sanderson writes most emphatically that magic systems without rules can be effective! He does give some advice on how to use them in your storytelling, though. In particular, he says that such magic systems should be used primarily in one way: to make it very clear that the main characters have little control over their worlds. To quote some of the article (emphasis mine):
I [developed] my first law as a way to include magic systems that don’t follow very strict rules, but which also don’t undermine their plots. [...]
This leaves room for those who want to preserve the sense of wonder in their books. [...] Books that focus on this use of magic tend to want to indicate that men are a small, small part of the eternal and mystical workings of the universe. This gives the reader a sense of tension as they’re never certain what dangers—or wonders—the characters will encounter.
Sanderson continues in his article to say that the major weakness of a magic system with few rules is that, in most cases, resolving conflicts with this magic cheapens the story. As I wrote above, there is great risk that it will come off as a deus ex machina. This is because, since magic cannot be understood, any time it helps out the main characters greatly, it can break suspension of belief. Sandrerson writes:
The really good writers of [magic systems without rules] very, very rarely use their magic to solve problems in their books. Magic creates problems, then people solve those problems on their own without much magic. [...]
So, if you want to write soft magic systems, I suggest you hold yourself to NOT letting your magic solve problems for your characters. If the characters try to use the magic, it shouldn’t do what they expect it to—as the reader doesn’t know what to expect either. Use the magic [...] to screw up things for the characters.
Looking at your original question, I noticed that you wrote, "[T]he story will focus on the main characters trying to make rules the magic will follow." This is very much in the spirit of Sanderson's first law! I believe that you can create a successful world with strong narrative potential based on your goals.