[jkaptur]

I didn't quite follow how you can actually prove that you've solved a sudoku via reduction to graph coloring. If I understand correctly, an important part of the graph coloring protocol is that the prover permutes the colors between each round (otherwise the verifier can just iteratively learn the color of every node).

But all sudoku puzzles have the same graph structure - a puzzle instance is a partial assignment of colors to nodes.

So can't a verifier can gain knowledge about the prover's solution by asking for edges that correspond to known values?

(I found a different ZKP protocol for sudoku, but I don't think it relates to the graph coloring protocol: https://www.wisdom.weizmann.ac.il/~naor/PAPERS/SUDOKU_DEMO/)

[benediktwerner]

The way the conversion is done here, different sudokus produce different graphs. Besides the regular sudoku graph structure, there are nine additional nodes, each corresponding to one number. They are all connected to each other to ensure they must be different and each one is connected to each cell where the corresponding number is present as a clue from the start. This way, the graph doesn't need any pre-coloring to still encode the sudoku including the given clues.

[jkaptur]

Ah ha! Thank you for explaining.

[tdb7893]

I haven't read this particular blog but the solution I remember seeing is you randomly swap the colors each edge verification so each is independent. All the edges are numbers that are required to be different so when you verify they are different you gain no information.

[jkaptur]

How does the verifier gain confidence that the prover has solved a particular instance of a sudoku puzzle?

[heinrich5991]

They can ask whether the pre-filled fields have the correct equal/unequal relationship by testing two of them at a time.