Here's a deterministic zero-knowledge proof of sorts, if there are any logic gaps please let me know!:
This zero knowledge proof involves proving you have a solution to three-colouring a map.
The common zero knowledge proof for this scenario (Hats & Crayons for example)involves the Prover tries to convince the Verifier that you have found a solution by only showing pairs of countries chosen by the Verifier, then repeatedly recolouring the entire map to allow the Verifier to check another pair. After a huge number of checks, the Verifier is satisfied that it is highly unlikely that the Prover does not really have a genuine solution, and considers the proof good enough to have confidence in it.
However, here is a set up for an deterministic zero knowledge proof:
You set out the huge blank uncoloured map on, say, a warehouse floor.
The Prover presents the Verifier with a set of cards and explains that each card has the label of a particular country of the map on one side and the other side is blue, red, or yellow. There are also three extra cards which are blank on the label side and have one of each colour on the flip side. The Verifier can examine the label side of the labelled cards to ensure there are no duplicates or country omissions, but is not allowed to check that all the cards have one of the three colours on the back (if the Verifier was allowed to do this, he would get some information about the overall proportion of the three colours: unlikely to be useful information, but knowledge all the same, zero knowledge is a requirement).
The Prover then places the cards on the corresponding countries label-side up and allows the Verifier to check that each card is placed on its correct country. The Prover also allows the Verifier to check the three extra cards have no labels, and contain the set of extra colours on their flip side.
The Prover then allows the Verifier to choose either 2 countries sharing a border (or 3 countries which each share a border with the other two).
Once chosen, the Prover takes the chosen 2 cards, adds one of the extra cards (if the Verifier has only chosen 2 countries, if not this step is skipped) taking care to add the extra card with the one colour not already present on the colour-side of the Verifier's chosen cards (he does not, of course, show the banker which colour he has added to the chosen 2). The Prover then thoroughly shuffles these three cards (which, remember are either two chosen by the Verifier plus an extra chosen by the Prover, or three chosen by the Verifier) and presents them to the Verifier colour-side up. The Verifier will always see three cards showing one of each of the colours. This proves to the Verifier that the 2 or 3 countries he picked do indeed have different colours (and these colours are from the allowed set of three colours).
Once checked, the Prover then shuffles the three cards again and places the labelled cards back on their countries (again, label side up). The Verifier is therefore satisfied that the Prover has reset the map as it was before.
This process repeats, enabling the Verifier to check that every single pair of connected countries have different coloured cards. With each verification cycle the Verifier will always only ever see three cards with the three allowed different colours, gaining no knowledge of what particular colour is on any particular country.
Not only is the Verifier able to check (very quickly) that there are no flaws in the solution, they also can see that the cards are not being changed with each verification cycle, so no room for the Prover to just be getting lucky each time.
As soon all the pairs (or trios) are checked once (the Verifier is allowed to check each pair more than once, does not need to), the Verifier is absolutely sure the solution is correct. But with each cycle, the Verifier has only ever seen the exact same answer: three different coloured cards (always showing the three chosen colours).
The Verifier has checked with absolute certainty that the solution is not flawed, but he has gained absolutely no useable knowledge about which colours go where, as he has only ever seen sets of the three chosen colours over and over again.
And to illustrate that the Verifier truly has zero knowledge after full verification of a true solution, if the Prover were to somehow be able to cheat by substituting colour cards during verification cycles, he would still only ever show the same three colours with each cycle.
The absence of re-setting the map takes away the possibility of the Prover just being lucky, while the addition of the blank extra cards does not allow the Verifier to gain any useful information, hence a non-probabilistic zero-knowledge proof.