function [ p_shapes, d, r_shape, p_num ] = LPmake_Problem71_Golo ( )

%*****************************************************************************80
%
%% LPmake_Problem71_Golo() sets up an LP version of Golomb's problem 71.
%
%  Discussion:
%
%    This function considers problem 71, page 143 of the second edition
%    of Golomb's book "Polyominoes".  It reformulates the problem as a 
%    kind of linear programming instance, and writes the information to
%    a standard LP file.  Up to 6 colours are used for the generalized 
%    colouring approach.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    14 February 2023
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Solomon Golomb,
%    Polyominoes: Puzzles, Patterns, Problems, and Packings,
%    Revised and expanded second edition,
%    Princeton University Press, 1996,
%    ISBN: 9780691024448
%
%  Output:
%
%    integer p_shapes(10,10,p_num): p_num arrays of 0's and 1's which 
%    define the shape of each polyomino to be used in the tiling.
%
%    integer d(12): specifies how many copies of each polyomino we use.
%
%    integer r_shape(10,10): an array of 0's and 1's which defines the
%    shape of the region to be tiled.
%
%    integer p_num: the number of polyomino shapes.
%
  p_num = 12;
%
%  Create the binary matrices for the polyominoes and pack them into P_SHAPES.
%
  for page = 1 : p_num
    p_shapes(:,:,page) = zeros(10,10);
  end
  
  p_shapes(1:5,1,1) = [1;1;1;1;1];
  p_shapes(1:3,1:3,2) = [0 1 1;1 1 0;0 1 0];
  p_shapes(1:4,1:2,3) = [1 0;1 0;1 0;1 1];
  p_shapes(1:3,1:2,4) = [1 1;1 1;0 1];
  p_shapes(1:4,1:2,5) = [0 1;0 1;1 1;1 0];
  p_shapes(1:3,1:3,6) = [1 1 1;0 1 0;0 1 0];
  p_shapes(1:2,1:3,7) = [1 0 1;1 1 1];
  p_shapes(1:3,1:3,8) = [0 0 1;0 0 1;1 1 1];
  p_shapes(1:3,1:3,9) = [0 0 1;0 1 1;1 1 0];
  p_shapes(1:3,1:3,10) = [0 1 0;1 1 1;0 1 0];
  p_shapes(1:4,1:2,11) = [1 0;1 1;1 0;1 0];
  p_shapes(1:3,1:3,12) = [1 1 0;0 1 0;0 1 1];
%
%  Create the binary matrix for the region.
%
  r_shape = ones(10,10);  
  r_shape(1:3,1:3) = 0;
  r_shape(1:3,8:10) = 0;
  r_shape(8:10,1:3) = 0;
  r_shape(8:10,8:10) = 0;
  r_shape(5:6,5:6) = 0; 
%
%  D specifies how many copies of each polyomino we use.
%
  d = ones ( 1, 12 ); 
%
%  C specifies how many colours we use (excluding white, which we use for holes).
%
%   C = 2;   % CPLEX found 660 solutions
%   C = 3;   % CPLEX found 20790 solutions
%   C = 4;  % CPLEX found 77805 solutions
   C = 5;  % Integer infeasible.
%   C = 6;  % CPLEX found 114550 solutions
%
%  Set up the linear system A*x=b for the tiling problem.
%
  [ A, b ] = splitting_multihedral_matrix ( r_shape, p_num, p_shapes, d, C );
%
%  Create the LP file for submission to an optimizer.
%
  filename = 'Problem71_Golo.lp';

  variants_lp_write ( filename, '\ Problem71_Golo LP', A, b, p_num, d );

  fprintf ( 1, '\n' );
  fprintf ( 1, '  LPmake_Problem71_Golo created the LP file "%s"\n', filename );

  return
end  
