You are given a partially filledin 9x9 grid, grouped into a 3x3 grid of 3x3 blocks, where each square is to be filled with a digit from 1 to 9, subject to the requirement that each row, column, and block must contain each digit exactly once.

Sudoku can be viewed as a binary constraint satisfaction problem.

(a) What are the variables of this CSP?

(b) What are their domains?

(c) How would you translate the requirement that no two of the same digit mayoccur in the same row, column, or block into binary constraints?

uploaded image



Detailed answers to tough
homework problems