/* Lost at Sea problem (PuzzlOr) in Picat. http://puzzlor.editme.com/lostatsea2 """ Searching for a lost ship at sea is a time sensitive task that requires skill and urgency. Finding a lost ship quickly means the difference between life and death. 3,0,0,3,2,4,2,3, 3,3,3,1,2,4,1,4, 0,4,0,1,2,3,4,0, 1,1,0,3,4,1,1,0, 1,1,3,3,1,2,2,4, 0,2,3,3,3,0,2,4, 2,3,2,4,2,4,1,1, 2,1,2,2,2,4,1,3, The map in Figure 1 shows a section of ocean divided into 64 cells. Somewhere in this grid, a ship has been lost. Each cell has a number that represents the probability of finding the lost ship when that cell is searched (based on last known position, ocean currents, and debris sightings). For example, if you searched cell A1, you would have a 2 chance of finding the lost ship there. As the leader of the search and rescue team, your goal is to find the ship with all survivors. Unfortunately it takes you 1 day to search a cell and the lost sailors have only enough food and water to survive for 10 days. This allows you to search a total of 10 cells before the lost sailors perish. You may start your search in any of the 64 cells. You are only allowed to move to adjacent cells (you cannot move diagonally) and you are not allowed to revisit any cells. Add up the percentages in the 10 cells you have searched to get the probability of finding the lost ship. Question: What is the greatest probability of finding the lost ship? """ There are 8 optimal solutions, with sumPoints = 32. Here is one of them. x = [1,1,2,3,3,4,4,5,6,7] y = [5,6,6,6,5,5,4,4,4,4] path = [5,6,14,22,21,29,28,36,44,52] points = [2,4,4,3,2,4,3,3,3,4] sumPoints = 32 Solution: path(points): _(3) _(0) _(0) _(3) 1(2) 2(4) _(2) _(3) _(3) _(3) _(3) _(1) _(2) 3(4) _(1) _(4) _(0) _(4) _(0) _(1) 5(2) 4(3) _(4) _(0) _(1) _(1) _(0) 7(3) 6(4) _(1) _(1) _(0) _(1) _(1) _(3) 8(3) _(1) _(2) _(2) _(4) _(0) _(2) _(3) 9(3) _(3) _(0) _(2) _(4) _(2) _(3) _(2) 10(4) _(2) _(4) _(1) _(1) _(2) _(1) _(2) _(2) _(2) _(4) _(1) _(3) The path is shown with (points). Here are all the 8 optimal paths: Solution: path(points): _(3) _(0) _(0) _(3) 1(2) 2(4) _(2) _(3) _(3) _(3) _(3) _(1) _(2) 3(4) _(1) _(4) _(0) _(4) _(0) _(1) 5(2) 4(3) _(4) _(0) _(1) _(1) _(0) 7(3) 6(4) _(1) _(1) _(0) _(1) _(1) _(3) 8(3) _(1) _(2) _(2) _(4) _(0) _(2) _(3) 9(3) _(3) _(0) _(2) _(4) _(2) _(3) _(2) 10(4) _(2) _(4) _(1) _(1) _(2) _(1) _(2) _(2) _(2) _(4) _(1) _(3) Solution: path(points): _(3) _(0) _(0) _(3) _(2) 1(4) _(2) _(3) _(3) _(3) _(3) _(1) _(2) 2(4) _(1) _(4) _(0) _(4) _(0) _(1) 4(2) 3(3) _(4) _(0) _(1) _(1) _(0) 6(3) 5(4) _(1) _(1) _(0) _(1) _(1) 8(3) 7(3) _(1) _(2) _(2) _(4) _(0) _(2) 9(3) 10(3) _(3) _(0) _(2) _(4) _(2) _(3) _(2) _(4) _(2) _(4) _(1) _(1) _(2) _(1) _(2) _(2) _(2) _(4) _(1) _(3) Solution: path(points): _(3) _(0) _(0) _(3) _(2) 1(4) _(2) _(3) _(3) _(3) _(3) _(1) _(2) 2(4) _(1) _(4) _(0) _(4) _(0) _(1) 4(2) 3(3) _(4) _(0) _(1) _(1) _(0) 6(3) 5(4) _(1) _(1) _(0) _(1) _(1) 10(3) 7(3) _(1) _(2) _(2) _(4) _(0) _(2) 9(3) 8(3) _(3) _(0) _(2) _(4) _(2) _(3) _(2) _(4) _(2) _(4) _(1) _(1) _(2) _(1) _(2) _(2) _(2) _(4) _(1) _(3) Solution: path(points): _(3) _(0) _(0) _(3) _(2) 1(4) _(2) _(3) _(3) _(3) _(3) _(1) _(2) 2(4) _(1) _(4) _(0) _(4) _(0) _(1) 4(2) 3(3) _(4) _(0) _(1) _(1) _(0) 6(3) 5(4) _(1) _(1) _(0) _(1) _(1) _(3) 7(3) _(1) _(2) _(2) _(4) _(0) _(2) _(3) 8(3) _(3) _(0) _(2) _(4) _(2) _(3) 10(2) 9(4) _(2) _(4) _(1) _(1) _(2) _(1) _(2) _(2) _(2) _(4) _(1) _(3) Solution: path(points): _(3) _(0) _(0) _(3) _(2) 1(4) _(2) _(3) _(3) _(3) _(3) _(1) _(2) 2(4) _(1) _(4) _(0) _(4) _(0) _(1) 4(2) 3(3) _(4) _(0) _(1) _(1) _(0) 6(3) 5(4) _(1) _(1) _(0) _(1) _(1) _(3) 7(3) _(1) _(2) _(2) _(4) _(0) _(2) _(3) 8(3) _(3) _(0) _(2) _(4) _(2) _(3) _(2) 9(4) 10(2) _(4) _(1) _(1) _(2) _(1) _(2) _(2) _(2) _(4) _(1) _(3) Solution: path(points): _(3) _(0) _(0) _(3) _(2) 1(4) _(2) _(3) _(3) _(3) _(3) _(1) _(2) 2(4) _(1) _(4) _(0) _(4) _(0) _(1) 4(2) 3(3) _(4) _(0) _(1) _(1) _(0) 6(3) 5(4) _(1) _(1) _(0) _(1) _(1) _(3) 7(3) _(1) _(2) _(2) _(4) _(0) _(2) _(3) 8(3) _(3) _(0) _(2) _(4) _(2) _(3) _(2) 9(4) _(2) _(4) _(1) _(1) _(2) _(1) _(2) 10(2) _(2) _(4) _(1) _(3) Solution: path(points): _(3) _(0) _(0) _(3) _(2) _(4) _(2) _(3) _(3) _(3) _(3) _(1) _(2) 1(4) _(1) _(4) _(0) _(4) _(0) _(1) 3(2) 2(3) _(4) _(0) _(1) _(1) _(0) 5(3) 4(4) _(1) _(1) _(0) _(1) _(1) 7(3) 6(3) _(1) _(2) _(2) _(4) _(0) _(2) 8(3) 9(3) _(3) _(0) _(2) _(4) _(2) _(3) _(2) 10(4) _(2) _(4) _(1) _(1) _(2) _(1) _(2) _(2) _(2) _(4) _(1) _(3) Solution: path(points): _(3) _(0) _(0) _(3) _(2) _(4) _(2) _(3) _(3) _(3) _(3) _(1) _(2) 1(4) _(1) _(4) _(0) _(4) _(0) _(1) 3(2) 2(3) _(4) _(0) _(1) _(1) _(0) 5(3) 4(4) _(1) _(1) _(0) _(1) _(1) _(3) 6(3) _(1) _(2) _(2) _(4) _(0) _(2) _(3) 7(3) _(3) _(0) _(2) _(4) _(2) _(3) _(2) 8(4) 9(2) 10(4) _(1) _(1) _(2) _(1) _(2) _(2) _(2) _(4) _(1) _(3) This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. main => go. go ?=> % define the problem Rows = 8, Cols = 8, MaxSteps = 10, % max length of the loop Problem = {{3,0,0,3,2,4,2,3}, {3,3,3,1,2,4,1,4}, {0,4,0,1,2,3,4,0}, {1,1,0,3,4,1,1,0}, {1,1,3,3,1,2,2,4}, {0,2,3,3,3,0,2,4}, {2,3,2,4,2,4,1,1}, {2,1,2,2,2,4,1,3}}, % The valid connections (for table_in/2) ValidConnections = [{(I1-1)*Cols+J1,(I2-1)*Cols+J2} : I1 in 1..Rows, J1 in 1..Cols, I2 in 1..Rows, J2 in 1..Cols, ((abs(J1-J2) == 1, I1 == I2); (abs(I1-I2) == 1, J1 mod Cols == J2 mod Cols) ) ], % decision variables % the coordinates in the path X = new_list(MaxSteps), X :: 1..Rows, Y = new_list(MaxSteps), Y :: 1..Cols, Path = new_list(MaxSteps), Path :: 1..Rows*Cols, % the collected points MaxPoint = max([Problem[I,J] : I in 1..Rows, J in 1..Cols]), Points = new_list(MaxSteps), Points :: 0..MaxPoint, % objective: sum of points in the path MaxSum = sum([Problem[I,J] : I in 1..Rows, J in 1..Cols, Problem[I,J] > 0]), println(maxSum=MaxSum), SumPoints :: 0..MaxSum, % % channel between path (integer representation) and % the coordinate representation in (x, y) % foreach(I in 1..MaxSteps) Path[I] #= (X[I]-1)*Cols + Y[I] end, % all coordinates must be unique (first approach) % Note: Sometimes it's faster if this is also active. % foreach(S in 1..MaxSteps, T in S+1..MaxSteps) % X[S] #!= X[T] #\/ Y[S] #!= Y[T] % end, % all coordinates must be unique % using alldifferent instead all_different(Path), % calculate the points (to maximize) foreach(S in 1..MaxSteps) % Points[S] #= Problem[X[S], Y[S]] matrix_element(Problem,X[S],Y[S],Points[S]) end, SumPoints #= sum(Points), % % Get the path (coordinates) % foreach(S in 1..MaxSteps-1) abs(X[S] - X[S+1]) + abs(Y[S] - Y[S+1]) #= 1 end, % % Only valid connections, using table/2. % foreach(S in 1..MaxSteps-1) table_in({Path[S], Path[S+1]}, ValidConnections) end, % % Symmetry breaking 1: % the cell with lowest coordinates should be in the first step. % foreach(I in 2..MaxSteps) Path[1] #< Path[I] end, % Symmetry breaking: % Second step should be larger than the first step Path[1] #< Path[2], % SumPoints #= 32, % for showing all solutions Vars = Path ++ Points ++ X ++ Y, solve($[max(SumPoints),split],Vars), % Optimal value % solve($[split],Vars), % all optimal solutions println(x=X), println(y=Y), println(path=Path), println(points=Points), println(sumPoints=SumPoints), println("Solution: path(points):"), Sol = new_array(Rows,Cols), bind_vars(Sol,0), SolPoints = new_array(Rows,Cols), bind_vars(SolPoints,0), foreach(I in 1..MaxSteps) Sol[X[I],Y[I]] := I, SolPoints[X[I],Y[I]] := Points[I] end, foreach(I in 1..Rows) foreach(J in 1..Cols) if Sol[I,J] > 0 then printf("%2d(%d) ",Sol[I,J],Problem[I,J]) else printf(" _(%d) ",Problem[I,J]) end end, nl end, nl, fail, nl. go => true.