How to compare distributions of values by the way they cluster along a line?

Question

This is an optimization problem in Sudoku. I use a very fast brute force recursive fill-and-backtrack algorithm to count the number of solutions. This proceeds from the top-left to the bottom-right and the 9x9 grid can be put in an 81 character line in that order. But how the Sudoku is rotated gives very different computational time because if the clues are clustered in the bottom-right the back-tracker can take 1000x more calls to complete. It is much faster if there are more numbers (or less longer gaps) in the top-left. I need a quick and dirty way to assess which rotation (or orginal) is the best to use before running the solution count.

The actual numbers are irrelevent, so 1=a clue, dot is a gap. For example, this is a puzzle and its three 90 degree rotations. The function calls represent the cost.

.......1......1..1.1.1..1........1.1..1.111...11.11.....1...11111..1..1...1...... -> 1069004 calls
.1.1..1..1.....11...111.1...1..11.......11.1...1..........111.1..1..1.1........1. -> 6680 calls *BEST
......1...1..1..11111...1.....11.11...111.1..1.1........1..1.1.1..1......1....... -> 12169 calls
.1........1.1..1..1.111..........1...1.11.......11..1...1.111...11.....1..1..1.1. -> 1292473 calls

I've tried merely weighting (and summing) the gaps from very high (left side) to very low (right side) but not getting good results. The gains from a good assessor will be huge over large numbers of puzzles being processed.

Answer 1

Clustering won't help you much there, because what patterns would it find, and how would you use them?

You better approach it with some math. A gap early on means you'll need to do everything below about 9 times. A digit early on means you'll need to consider only one option. A gap in the last cell likely is cheap - 8 of the 9 options can easily be ruled out. Now on average it won't be 9:1 in cost difference, but you could experimentally or empirically assign a cost factor to gaps. Then check which ordering has the largest cost.

If you consider your data to be 81 points of (x,y) where x = order positions 1 to 81 and y=1 if a gap, and 0 if filled, you could easily train a predictive model of the form sum(a x y)+c to estimate your cost at least to de degree of predicting which order is best.

In addition to the rotations, you'll also need to consider the flipped versions, with rows and columns swapped! And in fact, you may also permute rows and columns within each group of 3 and the three groups. So there is likely 6*6*6*6*2 equivalent versions of the same sudoku, not just 4.

On a more advanced level - can't you reorder the cells arbitrarily in your processing order? Put all filled cells first, then order the gaps by the number of filled neighbors they have (row+column+block) descending.