My students (Matvey Borodin, Eric Chen, Aidan Duncan, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, Michael Voigt) and I recently wrote a paper connecting the stable marriage problem and Sudoku. I just blogged about it. By the way, my students are in grades 7-9.
On the way, we invented a new type of Sudoku, which we call joint-groups Sudoku. This type is in contrast to a famous type of Sudoku, called disjoint-groups Sudoku. In a disjoint-groups Sudoku, in a particular place in a 3 by 3 box, all the digits are distinct across all the boxes. For example, the top-left corners of nine boxes have all the digits 1 thought 9. This creates nine additional disconnected regions (depending on the placements inside a 3 by 3 box) to add to columns, rows, and boxes that have to contain distinct digits.
For our new type, we wanted the digits in a particular place in each box, instead of being different, to be the same as much as possible. How much of sameness is possible? The first row contains three top-left corners. Thus, by Sudoku rules, these top-left corners have to be distinct. Thus, the top-left corners in all nine boxes have to contain at least three distinct digits. So here is the rule for the joint-groups Sudoku: the nine digits in a particular place in a 3 by 3 box contain not more than three distinct digits. It is easy to see that it means they contain exactly 3 distinct digits, each of them three times.
Here are two Sudoku puzzles from our paper. Each puzzle, when completed, forms a joint-groups Sudoku.