  We formulate the algebraic Bethe ansatz solution of the SU(N) vertex models
with rather general non-diagonal toroidal boundary conditions. The reference
states needed in the Bethe ansatz construction are found by performing gauge
transformations on the Boltzmann weights in the manner of Baxter [1]. The
structure of the transfer matrix eigenvectors consists of multi-particle states
over such pseudovacuums and the corresponding eigenvalues depend crucially on
the boundary matrix eigenvalues. We also discuss for N=2 the peculiar case of
twisted boundaries associated to singular matrices.
