Sudoku comes from the Latin Square, invented in middle age, Leonhard Euler. But Sudoku related to the Colouring Problem, how do you colour each node in a pentagram/star so none have a neighbour the same colour. Think of Sudoku numbers as colours, each square must be different to its neighbour.
Solving sudoku for all sizes – it’s not just 9 x 9 – is an NP-complete problem, i.e “damn hard”!
How many solutions does Sudoku have? For 4 x 4 Latin Square, 576 versions, and for 9 x 9… there are lots and lots, i.e. 6 x 10 ^ 21. Without symetries, Russell & Frazer found 5.4bn solutions if you take out the symmetries.
Sudoku puzzles require clues to define a unique solution. With 4 clues, it might not have a unique solution. So what is the minimum number of clues that will provide a unique solution. Minimum found now is 17. But is there a 16 clue puzzle? Need a sudoku-checker programme to see if any 16 clue puzzles have unique solutions.
If can check for each solution in 1 second, need to spend 173 years to check all the options, but 1 second to search is not feasible.
Fastest checker will still take 2417 CPU years. Volunteer computing can help. Each solution can be checked independently.
Asia@home is promoting volunteer computing in SE Asia.
Future plans include earthquake hazard maps and medicine design simulations.