Is brute force not interesting anymore?

tomker

I've noticed that on this board, brute force solutions are frowned upon, but I was wondering if it's because they solve the puzzles so easily that they're not interesting?

I wrote a brute force solver earlier this afternoon. Every time I made an improvement, I ran into the occasional puzzle that would take 20 seconds, a minute, or longer (hours?) for the solver to figure out. But with my latest improvement, I can't find a puzzle that takes the solver longer than 20 milliseconds.

I think the approach I'm using is somewhat clever but I don't know if other brute force solvers perform just as well...?

Also, if anybody wants to post a problem to try to stump my program, I'd be interested...

-Tom

70Bang! · Posted: Tue Jun 07, 2005 4:23 am Post subject:

I suppose the diplomatic answer is that it's not so much that it's not interesting, but there are other, more fun ways to slice it apart. Just like it is with every new toy that comes along.

You provided evidence it wasn't completely interesting. You had a brute force solution (which worked) but couldn't leave well-enough alone, eh? As soon as you tweaked, it was no longer brute force, was it? I suppose you could say it was "optimized brute force", then "re-optimized brute force", then "re-re-optimized brute force", etc.

Seriously: at what point did you decide to quit tinkering? What solution time was considered acceptible? If there was some method of assigning a metric to everyone's work[1] and your solution registered a "48" and someone else registered a "46", how much time & effort would you invest to beat that "46"?

It's like the inverse of juggling. No one is impressed that any of us could juggle five, six, or seven balls. They always want to know if we can juggle "one more".

Isn't that point of algorithms? a game of one-upmanship in a friendly sort of way when presenting answers.
___________________________

[1] Because computing environments are likely to be as unique as fingerprints, there would have to be some method of creating a metric for comparing solutions. It would be nearly impossible to define one, but aside from the rhetorical situation, it would be interesting to know if we could find a metric to determine efficiency.

MadOverlord

milt boyd · Posted: Tue Sep 13, 2005 1:15 pm Post subject: brute force versus ??

I guess part of the question is "why try to solve a puzzle?"
If your goal is to "get the answer" then brute force certainly works. I had fun programming a BF algorithm that just methodically kept applying the rules to find the unique value for each cell, and the unique cell for each value, and it worked (fairly quickly too) (available on request).

But if your goal is to figure how the pieces fit together, or to figure out and apply clever methods, then you may explore more "deductive" approaches, which use the clues efficiently.

A lot depends on your situation: in industry, with a one time problem, BF may be highly favored; with a problem that comes up often, then other techniques may be worth exploring. And of course, in academe, clever counts for much.