TDP Part 1IntroductionAs announced in my previous article on the forum, I present here the method of solving sudoku grids (puzzle) that I call "Technical of tracks", TDP in short (TDP = "Technique Des Pistes" in French).

This method is inspired by "Forcing chains" but differs from it by the fact that it treats the puzzle in a global way, and allows to develop a theory with its definitions, its properties and its theorems. It is a global approach to resolution in the same way as that of Allan Barker, or that of Denis Berthier.

From a practical point of view, it allows the sudokist to memorize only one way of doing things, which is simpler than knowing different advanced techniques that are not always easy to implement. In France, where I published a book and developed a website (

http://www.assistant-sudoku.com), many sudokists use this method.

The purpose of this article, and the following ones, is to present the TDP and its arguments in as simple a way as possible. A complete document on this method can be found on my website, but alas in French.

What I present in the 4-part forum is gathered in this PDF :

http://www.assistant-sudoku.com/Pdf/TDP-anglais.pdfBasic techniquesThe TDP uses basic techniques (TB) for its implementation, so I specify here what I consider to be basic techniques. These are the ones that every sudokist knows in principle: unique candidates (singles), closed sets (pairs, triples, etc...) and alignments (pointing, box line).

We can eventually add X-wing for its simplicity, but nothing prevents those who want to add other techniques that they master well like fishs.

Anti-trackLet's start with the notion of anti-track and its definition.

Definition :E = {Ai, i=1,2,...,n} being a set of n candidates Ai of the puzzle G, an anti-track P'(E) = {Bj, j=1,2,...,m} is the set of m candidates Bj that would be placed with the basic techniques (TB) in the cells of G as (true) solution IF the candidates of E were eliminated (false) from G.

It is said that E generates P'(E).Of course, by doing this, three situations can occur:

- or, the placement of candidates Bi encounters a contradiction (no candidate Bj possible in a box, two candidates Bj in the same area, etc...). It is then said that P'(E) is

invalid.

- or, the candidates of P'(E) are all solution candidates. It is said that P'(E) is

valid. We'll see later when this situation occurs.

- or, nothing can be concluded at this stage on the status of P'(E), because it cannot be proven that P'(E) is valid or invalid.

An obvious first property to be used is as follows:

Property (P1):If P'(E) is invalid, then at least one candidate Ai of E is a solution in his box.

Let us give other definitions that will make it possible to establish a first interesting theorem to illustrate the use that can be made of anti-tracks.

K1, K2,... the boxes that contain the candidates Ai of any set E={{Ai, i=1,p} and by Ei the set of candidates of E contained in Ki. We have E=UEi. E'i refers to the complementary set of Ei in Ki.

The Ei sets are called the components of E. The E'i sets are called the counter-components of E.

Definition: An anti-track P'(E) is said to contain a set of candidates E1={B1j, j=1,2,...} when a candidate of each component E1i of E1 is necessarily a candidate belonging to P'(E).Let us then demonstrate the following theorem.

Theorem 1 :In the same zone Z (block, row or column), E1 and E2 are two distinct sets with two components each consisting only of candidates of occurrence a and b.

If any of the conditions H1, H2 or H3 below are met, then all candidates of occurrence a or b that are not contained in E1UE2 can be eliminated from zone Z.

- (H1) : P'(E1) and P'(E2) are invalid.

- (H2) : P'(E2) is invalid and P'(E1) contains E2.

- (H3) : P'(E1) contains E2 and P'(E2) contains E1.Demonstration :

1)- According to H1 and the property (P1), E1 and E2 each contain a solution candidate, so the two candidates of Z of occurrence a and b are in E1UE2 => elimination of candidates of Z of occurrence a or b who are not in E1UE2 .

2)- According to H2 and the property (P1), E2 contains at least one candidate solution and two cases are possible:

- P'(E1) valid => E2 contains two solution candidates, one of which is occurrence to the other of occurrence b => elimination of candidates from Z of occurrence a or b who are not in E1UE2.

- P'(E1) invalid and this returns to case 1) => elimination of candidates from Z of occurrence a or b who are not in E1UE2.

3- According to H3, four cases are possible:

- P'(E1) valid => E2 contains two solution candidates, one of which is occurrence to the other of occurrence b => elimination of candidates from Z of occurrence a or b who are not in E1UE2.

- P'(E1) invalidates which leads to case 2) => elimination of candidates from Z of occurrence a or b who are not in E1UE2.

- Same reasoning and conclusion with P'(E2) depending on whether it is valid or invalid.

In all possible cases of H1, H2 and H3 candidates from Z of occurrence a or b that are not in E1UE2 are eliminated.

Here is an example on the famous Easter Monster puzzle of an application of all this.

G = 1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1

Let's take E1={38r2c13} and E2={38r2c79}.

P'(E1) ={2r2c1, 7r2c1, 1r7c2, 6r9c2, 2r8c7, 7r8c9, 1r3c8, 6r1c8, ...} => P'(E1) contains E2.

P'(E2) ={1r2c7, 6r2c9, 2r7c8, 7r9c8, 1r8c3, 6r8c1, 7r1c2, 2r3c2 ...} => P'(E2) contains E1.

According to the theorem, 38r2c5 and 8r2c6 can be eliminated.

It is understood that the theorem also applies following the sets of type E1 and E2 which constitute the well-known Sk-loop of this puzzle and all eliminations are deduced from it.

But this theorem also applies to puzzles that do not count SK-loop, for partial eliminations.

On the practical side, the representation of an anti-track is easier to do by marking the candidates on the puzzle in colour than in the form of an abstract set. This can be done as below, for example with the Hodoku application or the application of my website.

These are in blue the candidates of P'(E1) studied previously. We see that if we continue the marking we obtain a contradiction in the r5c8 box, so P'(E1) is invalid.

I will stop there for this first article, but the TDP has many other aspects that I will present gradually.

Thank you for your possible remarks and excuse me for my approximate English.

Robert