A search for charged Higgs bosons (H±) decaying into a top and a bottom quark in the all-jet final state is presented. The analysis uses LHC proton-proton collision data recorded with the CMS detector in 2016 at 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± 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± 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± 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. [Figure not available: see fulltext.].