The problem sudoku : Tips , solve , calculations , illusion

The data of 16 digits in a Sudoku is insufficient for solving the problem is unique. To prove this, it was necessary to list all the grids, using tips to shorten the calculations

It is an illusion to believe that the power of the machines dispense us from thinking. About the problem of minimum data sudoku, we will see that the limits of feasible soon reached, and that for the push, it takes ingenuity, mathematics and still a lot of patience.

Remember the rules of Sudoku and fix some terms. A "complete Sudoku" is a square table 9 March 9 = 81 squares, each containing a number from 1 to 9 and such that:

(A) each row and each column contains each digit exactly once;

(B) each subarray 3 3 3 (result of the cutting of the gate into nine squares of nine squares) contains each digit exactly once.

A partial grid is a "correct sudoku problem" if there is a unique way to complete the grid in a complete Sudoku, which is the goal of the game.

Specify that sudoku, the computer wins on humans: there are many programs that allow the computer to beat the best human speed. Good programs are the solution to a problem, as difficult as it is, in less than a millisecond. So we play for fun exercise.

When looking to make a statement, if you specify too few cases, partial grid is not correct the problem (that is obvious if one retains only one), as several solutions are possible. In newspapers, the proposed grids have about 25 boxes filled. It is known however that there are correct grids sudoku with only 17 data.

The problem of minimum data is: What is the smallest number of data a correct sudoku problem?

Example 17 shows that data that minimum is 17 or less. It has long sought, unsuccessfully, to 16 problems correct data; so we conjectured that 17 is the answer.

At least 16 or 17 boxes?

The problem remained open until, in December 2011, the answer is provided by Gary McGuire, of the University of Dublin, and his team. Following a spread calculation on a year corresponding to 800 years of computing a single processor, the conclusion was that there are no correct grid sudoku data 16 and thus the minimum number of data a correct sudoku problem is 17.

This is a mathematical theorem, and since this is the mathematical question concerning the sudoku that required the most effort, will be called "The theorem sudoku". The work that led to the state is a demonstration. As now occurs increasingly often, it is a proof with a computer. The detailed steps in the calculation has not been published because it would give a document of colossal length. The article reporting the evidence is therefore that the description of the method used, including, among others, statements and demonstrations purely mathematical propositions helpful, but not enough information so that we can verify the theorem without any reprogramming and recalculate.

Preliminary versions of the article had been available for a while, but it was published in its final form June 12, 2014, in the journal Experimental Mathematics. Despite this official publication, essential for a result to be considered ...