In diagnostic classification models (DCMs), the Q matrix encodes in which attributes are required for each item. The Q matrix is usually predetermined by the researcher but may in practice be misspecified which yields incorrect statistical inference. Instead of using a predetermined Q matrix, it is possible to estimate it simultaneously with the item and structural parameters of the DCM. Unfortunately, current methods are computationally intensive when there are many attributes and items. In addition, the identification constraints necessary for DCMs are not always enforced in the estimation algorithms which can lead to non-identified models being considered. We address these problems by simultaneously estimating the item, structural and Q matrix parameters of the Deterministic Input Noisy “And” gate model using a constrained Metropolis–Hastings Robbins–Monro algorithm. Simulations show that the new method is computationally efficient and can outperform previously proposed Bayesian Markov chain Monte-Carlo algorithms in terms of Q matrix recovery, and item and structural parameter estimation. We also illustrate our approach using Tatsuoka’s fraction–subtraction data and Certificate of Proficiency in English data.