We propose a new description of the SU(N) Yang-Mills theory on a lattice, which enables one to explain quark confinement based on the dual superconductivity picture in a gauge independent way. We apply this fomulation to the SU(3) Yang-Mills theory on a lattice. We give preliminary numerical results showing the dominance of the non-Abelian magnetic monopole in the string tension obtained from the Wilson loop in the fundamental representation.