Statistical Methods?

Cowz · Posted: Fri Aug 26, 2005 2:09 am Post subject: Statistical Methods?

Clearly, after reading these forums fairly extensively, I am out of my league. However, to my understanding, all of the methods on this board (Nishio, Fishy, Bowman's Bingo, X-Wing, etc.) all rely on a core algorithm that guides the placement of numbers.

My question is: has anyone looked into statisitcal methods (like gathering common frequencies and weighting them) in order to set/solve a Sudoku? I imagine that with enough "known good" inputs and solutions, that it might be possible to at least enhance the decision making for more complex algorithms.

I wish I had something more to offer on this front but I wouldn't know where to start. Mathematics are NOT my strong point.

dukuso · Posted: Fri Aug 26, 2005 2:14 pm Post subject:

what might qualify as statistical methods here ?
Maybe: use the symbol which was already used
most often !
Or : select the variable with the minimum domain size and then select
the value which occurs the fewest times in the domains of the
variables of the rows and the columns of the selected variable

Or compute some data from the sudoku, like number of clues,
number of clues for a row,col,symbol and then branch
to several solving methods, depending on the result

Howard · Posted: Fri Aug 26, 2005 7:31 pm Post subject: Simple statistical observation

I wonder if there's something in this... I notice that when solving, I'm most likely to make progress on removing candidates and placing values for numbers which are already common on the board.

For instance, if I have 6 boxes out of the 9 already containing a 7, then (when solving by hand) I'll tend to look to put the 7's in the remaining boxes.

In terms of solving sudoku by computer by applying the various techniques (which is how my engine works) - and of course the solver being the main part of the builder - it occurs to me that I tend to often do a "for n=1 to 9, apply technique for n" kind of approach.

Perhaps it might be faster if I could usefully order my searches in the order in which they are most likely to lead to a result.

For instance, if my grid contains 6 7s, 5 4s, 5 9s, 4 8s, 4 4s, 3 5s, 2 2s 2 3s and 2 1s, then would I be better applying the value based techniques in the order 7,4,9,8,4,5,1,2,3, since I'd be more likely to get a result earlier in the test.
My gut feeling is that even if there's a good correlation between frequency and ability to use the technique, then at most I'm going to optimise my solver by about 5%, and likely much less. Perhaps the overhead of counting and sorting the values could be more than it saves - but it seems like something worthy of a trial Smile

If it helps, I'll post a result here. (There's also the fact that optimisations like this tend to obfuscate code, which isn't a good thing.)

Just thinking about candidate removals, you're most likely to make progress removing a candidate if there aren't many of that candidate on the board - which is likely to correlate well with the number of finalised placements for that value on the board Wink

.
( Reasoning here - if there's only 2 candidates for 7 on the board, then any candidate removal for 7 will lead to effective progress, while removing a candidate for a common value is less likely to help. )

Another quick observation, so obvious that I completely missed it... If you've already placed all of the 7s on the board, don't bother doing any of your technique tests for 7s! (why didn't I think of this earlier? *kicks self*)
_________________
Howard Tomlinson, Developer, Astraware. (howard at astraware dot com)

Howard · Posted: Sun Aug 28, 2005 2:37 pm Post subject: Results / Success!

I tried the proposed optimisation, and it helped.

For a particlar range of builds, my generator averaged 165 time units (+-2) to create the puzzles, which included testing for techniques up to Swordfish-4 and simple forcing chains.

After the optimisation, the generator averaged 157(+-2) time units to do the same.

The end puzzles were the same, although it may have chosen to do a range of single available position tests in a different order internally.

The key points:
The simple optimisation of not performing the tests for a value if all instances of that value have already been placed made about half of the difference.

Ordering the tests so that they were done in order of most already placed down to least already placed, helped by the other half.

Observation : It made much more difference to the simpler tests - single available position and the various line/block intersection tests, than it did to Swordfish 2/3/4. I'm not convinced that it actually made a noticeable difference in my tests on looking for Swordfish, but I'll leave the code in, because its so small. Your Mileage May Vary!

So, in essence about a 5% speed improvement - can't complain! (For 1 hour of work, this is pretty good value Smile

)

Howard.
_________________
Howard Tomlinson, Developer, Astraware. (howard at astraware dot com)