I've found that a very effective way of solving Sudoku's is to translate them into a satisfiability problem in conjunctive normal form, and then apply "SAT solving" techniques. I've found, empirically, that a linear time method -- called hyperresolution with equality propagation can solve at least 95% of the Sudoku's that I find -- including the "very hard" one that stumped the champion in the recent contest. This method doesn't involve any backtracking at all. It is global though -- to solve it it needs to construct a labeled digraph and find the strongly connected components. -- Victor S. Miller | " ... Meanwhile, those of us who can compute can hardly victor@idaccr.org | be expected to keep writing papers saying 'I can do the CCR, Princeton, NJ | following useless calculation in 2 seconds', and indeed 08540 USA | what editor would publish them?" -- Oliver Atkin