logoalt Hacker News

lightamulet • 11/04/2025 • 1 reply • view on HN

Trying to represent sudoku as an integer program leads to a natural way to represent the board: a 9x9x9 boolean grid where x and y are the board dimensions and z is the number in each square.

You end up with three symmetric constraints + the box constraint:

- The sum along any x, y, or z row is 1 (one of each number per row, one of each number per column, and one number per square)

- The sum of each 3x3x1 box slice is 1 (one of each number per box)

I really like the symmetry between the row sum constraints here. And it does pretty neatly align with the way many people solve Sudoku by writing little numbers in the squares to represent possible values before pruning impossible ones.

Replies

mzl • 11/04/2025

That representation of a Sudoku is elegant, but I think it is not the most natural representation. The base constraint programming style will use a variable per square with domain 1-9, and then 27 all_different constraints. This representation is a lot closer to how people talk about the rules of Sudoku, which in my mind makes it more natural.

A full MiniZinc program would look like this

    int: n = 3;
    int: s = n*n;
    set of int: S = 1..s;
    
    array[S, S] of opt S: puzzle;
    
    array[S, S] of var S: board;
    
    % Sudoku constraints
    constraint forall(row in S) ( all_different(board[row, ..]) );
    constraint forall(col in S) ( all_different(board[.., col]) );
    constraint forall(r, c in {1, 4, 7}) (
        all_different(board[r..<r+n, c..<c+n])
    );
    
    % Set up puzzle
    constraint forall (r, c in S where occurs(puzzle[r, c])) (
        board[r, c] = puzzle[r, c]
    );
    
    solve satisfy;
And an instance file looks like this

    puzzle = [|
         9, <>,  8,   1, <>, <>,  <>, <>,  4 |
         1,  2, <>,  <>,  8,  6,  <>,  5, <> |
        <>, <>,  7,  <>, <>, <>,  <>,  1, <> |
    
        <>,  8,  3,  <>, <>, <>,  <>,  6,  9 |
         7, <>,  6,   8, <>,  3,  <>, <>, <> |
        <>, <>, <>,   4,  6, <>,  <>,  8, <> |
    
        <>, <>, <>,  <>, <>,  1,  <>, <>, <> |
        <>, <>, <>,  <>, <>,  4,   5, <>,  1 |
         5,  4,  1,   9,  3,  8,  <>, <>, <>
    |];