Computer analysis on Consecutive Neighbors

A quick recap of what “Consecutive Neighbors” is: I’ve been writing sudoku puzzles and invented a variant with a global restriction.

Every number must share a side with at least one other consecutive number. For example, 2 must share a side with either a 1 or a 3 (possibly both).

This is a very limiting restriction, and the grid is very sensitive to initial conditions (i.e. initial digits placed). Placing just one digit can break the puzzle 30 steps later, so I have to know early when things don’t work out. I’d like to programmatically check that a solution is valid, and moreover, when I’ve hit a dead end and need to backtrack or slightly adjust the structure of the puzzle.

Obviously, there’s intention behind the puzzles: the initial clues I set up usually include 1/2’s or 8/9’s to use the condition, and after the initial setup I typically have an idea what the rest of the 12 and 89 pairs will look like. But I’d like to know what givens work and where stuff would break, in order to get a working solution (which is really, really hard). But this sort of computer analysis helps to get through dead ends much quicker.

Anyway, here’s the code I wrote to check 81 digits (inputted as chars, cast as ints):

#include <iostream>
using namespace std;

int main() {
    char input[81];
    for (int i=0; i<81; ++i) {
        cin >> input[i];
    }
    int grid[9][9];
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            grid[i][j] = input[9*i+j] - 48;
        }
    }

    // Perform neighbor check on each cell
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            // We set to true as soon as there is a neighbor.
            bool has_neighbor = false;
            for (int x=max(0,i-1); x<=min(8,i+1); ++x) {
                for (int y=max(0,j-1); y<=min(8,j+1); ++y) {
                    if ((x == i || y == j) && (grid[x][y] - grid[i][j] == -1 || grid[x][y] - grid[i][j] == 1)) {
                        has_neighbor = true;
                    }
                }
            }
            if (!has_neighbor) {
                return 0;
            }
        }
    }
    
    // Spit the grid back out; we're going to be doing this in batch
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            cout << grid[i][j];
        }
        cout << '\n';
    }
    return 0;
}

This helps to confirm a solution is correct. But if I want to find a solution given some set of givens, there’s a somewhat hacky way:

• after doing an initial analysis, input the digits I know for sure into sudoku-solutions.com,
• use the “Check” option (which will definitely fail) and download all the possible solutions as a text file
• use sed to fix newlines (rn looks like the script was meant for Windows)
• read line-by-line and input each solution into the constraint checker (code shown above)
• see outputted solutions, if any, and either use it or backtrack.

This is the code I used to pipe every solution into the constraint checker:

while IFS= read -r line; do
    echo $line | ./close-checker
done < close-solutions

(close-solutions is the file which I move the downloaded solutions into. close-checker is the file the constraint checker is stored in.)

I plan to improve it later by actually programming a solver that uses this condition to narrow things down much faster, but for now, this was the quickest thing to hack up.

This is easily generalizable to Dutch Neighbors, and it will be really helpful for writing my puzzle book. Though this variant is still difficult to set, at least it will be a little quicker.