Continuing the series on solving puzzles using SV constraints, This post is about no-three-in-line puzzle. From Wiki,

The no-three-in-line problem in discrete geometry asks how many points can be placed in the NxN grid so that no three points lie on the same line.

It’s nice problem because it’s more complicated than n-queen. Why more complicated? mainly because we need to include more than just 2 cells in the constraints. Let’s start with the easy ones first.

constraint 1 - cells Link to heading

we need random value for each cell. So, this one is obvious.

constraint a01 {foreach(grid[i][j]) grid[i][j] inside {[0:1]}}

constraint 2 - row Link to heading

Number of full cells in each row between [0:2]

constraint rows {foreach(grid[i][j]) grid[i].sum() inside {[0:2]};}

The problem Link to heading

Here where it gets interesting! I was stuck because i can’t think of clean way to iterate over columns. Then it hit me! why not define another grid and transpose the old into new grid and use the same constraints above the new grid.

// Here the magic
constraint grid_tmp {
        foreach(grid[i][j]) {
            grid[i][j] == tmp[j][i]
    }
}

constraint a0_tmp {foreach(tmp[i][j]) tmp[i][j] inside {[0:1]}}
constraint rows_tmp {foreach(tmp[i][j]) tmp[i].sum() inside {[0:2]};}

And it worked! I think!