A search for charged Higgs bosons (H$^\pm$) decaying into a top and a bottom quark in the all-jet final states is presented. The analysis uses LHC proton-proton collision data recorded with the CMS detector in 2016 at $\sqrt{s} =$ 13 TeV, corresponding to an integrated luminosity of 35.9 fb$^{-1}$. No significant excess is observed above the expected background. Model-independent upper limits at 95% confidence level are set on the product of the H$^\pm$ production cross section and branching fraction in two scenarios. For production in association with a top quark, limits of 21.3 to 0.007 pb are obtained for H$^\pm$ masses in the range of 0.2 to 3 TeV. Combining this with a search in leptonic final states results in improved limits of 9.25 to 0.005 pb. The complementary $s$-channel production of an H$^\pm$ is investigated in the mass range of 0.8 to 3 TeV and the corresponding upper limits are 4.5 to 0.023 pb. These results are interpreted using different minimal supersymmetric extensions of the standard model.