function [ x_num, x ] = i4mat_rref_solve_binary ( m, n, a, b )

%*****************************************************************************80
%
%% I4MAT_RREF_SOLVE_BINARY seeks binary solutions of an IRREF system.
%
%  Discussion:
%
%    An MxN linear system A*x = b is considered.
%
%    The matrix A and right hand side B are assumed to have been converted
%    to integer row-reduced echelon form (IRREF).
%
%    In order to solve a particular combinatorial problem, only binary
%    solutions x are of interest; that is, each entry of x is either 0 or 1.
%
%    The solution procedure involves two steps:
%    * assign each free variable a value of 0 or 1;
%    * solve for the dependent variables.
%
%    We consider every possible assignment of free variables, and we save
%    the solutions in which all the variables take on only 0 or 1 values.
%    
%  Licensing:
%
%    This code is distributed under the GNU LGPL license.
%
%  Modified:
%
%   09 September 2018
%
%  Author:
%
%    John Burkardt
%
%  Parameters:
%
%    Input, integer M, N, the number of rows and columns of
%    the IRREF matrix A.
%
%    Input, integer A(M,N), the IRREF matrix to be analyzed. 
%
%    Input, integer B(M), the IRREF right hand side.
%
%    Output, integer X_NUM, the number of binary solutions.
%    Note that there may be no binary solutions at all.
%
%    Output, integer X(N,X_NUM), the binary solutions that were found.
%

%
%  Augment the original linear system to the NxN system A2 x = B2.
%
  [ a2, b2, incon, freedom_num, freedom ] = i4mat_rref_system ( m, n, a, b );
%
%  Initialize the list of solutions.
%
  x_num = 0;
  x = [];
%
%  If FREEDOM_NUM < 0, then the system is overdetermined and cannot be solved.
%
  if ( freedom_num < 0 )
    return
  end
%
%  The indeterminate variables have a simple equation 
%    x(i) = b(i) = 0 or 1
%  Set up and solve every variation of this system.
%  If a solution is binary, accept it.
%
  binary = zeros ( freedom_num, 1 );

  while ( true )

    b3 = b2;
    for k = 1 : freedom_num
      i = freedom(k);
      b3(i) = binary(k);
    end

    y = i4mat_u_solve ( n, a2, b3 );

    if ( i4vec_is_binary ( n, y ) ) 
      x_num = x_num + 1;
      x(1:n,x_num) = y(1:n,1);
    end

    binary = i4vec_binary_next ( freedom_num, binary );

    if ( sum ( binary ) == 0 )
      break
    end

  end

  return
end

