Best way to start this problem guys?

[nomi]

Main Question or Discussion Point

http://img207.imageshack.us/img207/8952/neatoteeheesu5.jpg [Broken]











thx

 

[Diffy]

Do you have any thoughts?

And How can you pick 15 squares from a 12x12 array so that no two selected squares are in the same row or column?

 

[nomi]

thats what i dont understand

 

[Diffy]

That needs to be clarified, if you assume that there was a typo and they meant to say 12, not 15, then the problem makes sense. If you assume they meant 15 then either the table array needs to be bigger, or the rules have to change.

Please clarify with your teacher/professor, and let us know.

 

[Diffy]

Well anyway, lets go ahead and assume that you have to just pick 12.

Have you ever heard of the travelling salesman problem? As wikipedia states
Given a number of cities and the costs of traveling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?

One method of solving this problem (again according to wikipedia) is:

Constructive heuristics
The nearest neighbour (NN) algorithm (the so-called the greedy algorithm is similar, but slightly different) lets the salesman start from any one city and choose the nearest city not visited yet to be his next visit. This algorithm quickly yields an effectively short route.

Do you see how you can apply this to your problem?
Hint: think of column one as a city, and all the rows in column one as different routes to the next column. Of course here you want to maximize, not minimize, but the general principal is the same.

 

[Tedjn]

Since there are only 12! possible choices of numbers, the first thing I would do is brute force it. The simple program I made is probably the ugliest piece of C++ programming ever, but with less than 480 million trials, it took under 5 minutes. The minimum, seems to be 143 by picking 7, 18, 24, 5, 11, 9, 11, 14, 6, 5, 21, 12 in each row respectively. You should be able to find the maximum just as easily.

Then, you may want to look up what Diffy posted or consider better mathematical and algorithmic approaches to the problem.

 

[nomi]

thanks guys

 

[LukeD]

Use the Hungarian Algorithm. (It's an algorithm designed specifically for that problem)

 

[uart]

The minimum, seems to be 143 by picking 7, 18, 24, 5, 11, 9, 11, 14, 6, 5, 21, 12 in each row respectively. You should be able to find the maximum just as easily.

Just wondering what CPU that was run on Tedjn?

BTW. I'm also a fan of brute force when you can get away with it, it must be the Engineer in me :). My exhaustive search ran in under 30 sec written/compiled in Borland Delphi 7 (pascal) and run on an Athlon64-3800+. I got the same answer as you when I set it to find a minimum. The actual problem here is to find a maximum however but of course that's a trivial program change. I wont post the solution since I think the OP is still working on it.

 

[Tedjn]

I ran it on a Turion64 X2. It doesn't seem to account for maybe a 4 minute difference, so my program was probably very inefficient (I used a bunch of loops).

 

[uart]

No I just used 12 nested loops too. I know that looks ugly but it's actually a pretty efficient way to do it when the size of the problem (12 in this case) is a compile time constant. More likely the differences were in the way we each took care of the "index set" for enumerating all the combinations without choosing the same row or column twice.