Difficulty in solving a “bridge” Sudoku (with a minisat solver)

A while ago, we formulated a variant of Sudoku called the “bridge” Sudoku. We were curious on how it compared to solving a typical Sudoku in terms of difficulty. We encode bridge Sudoku based on the minimal encoding scheme. The statistics given by the minisat solver are used to comment on the difficulty of solving the Sudoku. We found that considering the above statistics, it is easier to solve a bridge Sudoku against solving the corresponding standard Sudokus.

Definition and Problem Formulation

Figure shows a “bridge” Sudoku with a M x N overlap

SAT Encoding for the ‘bridge’ Sudoku

Datasets and SAT solver

Results

Table shows the Pearson correlation coefficient and the log of Bayes factor in favor of the alternative hypothesis for the various statistics considered with the overlap area
Number of conflicts, propagations, conflict literals and decisions plotted against overlap area. Orange points belong to the set of bridge sudokus and the blue points belong to the corresponding standard sudokus. Note that there are lesser conflicts while solving the bridge Sudokus.

References

Artificial Intelligence Researcher | Developer