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
%
% Input:
%
% integer M, N, the number of rows and columns of
% the IRREF matrix A.
%
% integer A(M,N), the IRREF matrix to be analyzed.
%
% 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.
%
% 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