Problem 45415. Find an optimal placement of coolers on a grid

In a certain chemical plant, 6 new pieces of cooling equipment (coolers) are to be installed in a vacant space. This vacant space was divided into a grid of 6 cells by 6 cells. Your task is to assign the 6 coolers to 6 cells in this grid with the following requirements:

1. There must be one cooler for every column in the grid.
2. If you decide to install a cooler at row R, column C, then the cooler at column C+1 must be installed either on row R-1, R, or R+1 only. This is done to ease the connection of coolers by piping.
3. The total installation cost for the 6 coolers must be minimum.

For this problem, you are given a cost matrix (COST) in relation to the third requirement above. COST is a 6 x 6 matrix where the r,c-th element is the cost of assigning any cooler to row r, column c (All the coolers are identical). Write a function that accepts the matrix COST, and output the value of the minimum cost of installation. You are ensured that all elements of COST are integers in the range [1,1000].

In the sample test case below, the optimal placement is at the following rows: 4,3,3,2,2,2.

>> COST = [695   766   710   119   752   548;
           318   796   755   499   256   139;
           951   187   277   960   506   150;
            35   490   680   341   700   258;
           439   446   656   586   891   841;
           382   647   163   224   960   255];
>> coolers(COST)
ans = 
      1393

Meanwhile, the optimal placement for the case below is at rows: 5,6,5,6,5,6

>> COST = [815   617   918    76   569   312;
           244   474   286    54   470   529;
           930   352   758   531   455   988;
           350   831   754   780    12   602;
           197   586   381   935   163   263;
           252   550   568   130   795   100];
>> coolers(COST)
ans = 
      1521