Generalized methods

Advanced methods and approaches for solving Sudoku puzzles

Generalized methods

Postby Hajime » Mon Aug 24, 2020 2:01 pm

This story is about Sudoku Intersections of houses.
A house is a collection of 9 cells that must hold all digits 1 to 9 exactly once.
When 2 or more houses intersect, they share one or more cells.
The most well known intersection of 2 houses is the row (or column) intersection with a box.
GI.png
GI.png (32.8 KiB) Viewed 1170 times

In the picture above and the examples below all candidates are a "1" and cells where no "1" is present are noted as "/".
Cells with a candidate "1" that are not possible to have a "1", will be striked through.
Cells with no value (empty cells) are irrelevant to the subject, but may even contain a candidate 1.

Example 1 pointing or box-line reduction
A candidate 1 of a cell is the possible digit 1 can be the solution of that cell.

In above example in box 1 there are 2 cells with possible candidate 1 in row 3.
Because nowhere else in the box 1 can be a solution one of the 2 cells must be a 1.
And that leads to the conclusion that everywhere else in row 3 all cells with candidate 1 can eliminate 1, except for the 2 cells in common.

Example 2 claiming or line-box reduction
Also the other way around when 2 or 3 cells in row 7 AND box 9 have candidate 1 and no other cell in row 7 holds a 1, all other cells outside the intersection of box 2 can eliminate candidate 1.

Because a intersection between a row and a column is just 1 cell, than if eg the row holds only candidate k in that intersection cell, it would be the only candidate k in that row, and it would be a hidden or naked single.
In a normal Sudoku with rows, columns and boxes the above 2 methods to eliminate candidates are the only possible intersection methods.
In stead of 2 cells in the intersection between a box and a column or row may also be 3 cells with candidate k.

In a Windoku, Asterisk, SudokuX, etc more intersection methods are possible.

General rule:
If a house H has all cells with candidate k trapped/locked in the intersections with other houses then all cells outside H that 'see' all cells with k of H can eliminate k.
A common cell in ALL the houses of a collection is not necessary, but each house needs intersection with each other house.

Example 3 Windoku: Wbox to row
Wbox 2 has candidate 1 in row 3 and nowhere else. So row 3 can eliminate all other candidates 1 outside W2.

Example 4 Asterisk: asterisk to row
Row 3 has all its candidates in Asterisk. All other cells in Asterisk can eliminate candidate 1.

Above all intersections deals with intersections of 2 houses,
but with 3 or more houses we have to deal with 'Generalized Intersections'

An Asterisk, Girandola or CenterDots holds 1 extra house.
A SudokuX holds 2 extra houses, the diagonals.
A Windoku or SudokuP holds 9 extra houses (see picture between example 3 and 5).

Example 5 a row a column and a diagonal
Row 3 says 'all my candidates 1 are within a column and a diagonal'.
There is no cell that is part of all 3 houses. This is not necessary.
We can eliminate candidate 1 from cells that are part of column and diagonal that 'see' all 2 candidates of row 3.
So r6c6<>1.

The houses must intersect to each other. If some houses do not intersect you can split up the houses in 2 separate problems.
Split up non-intersecting houses picture between example 4 and 6.

Row 4 and row 6 do intersect with box 4 but do not intersect with each other.
You can split up "the problem" with 2 smaller problems: 1: row 4 with box 4 and 2: row 6 with box 4.

It is not necessary that there is 1 common same cell in all the houses. see example 5 and 6.

Example 6 two diagonals and 1 row
The first diagonal says 'that all my candidates 1 are in the intersections of the other diagonal and row 3'.
Now the cell that 'sees' those two cells and is outside the first diagonal can eliminate candidate 1.
So r3c7<>1.

Example 7 hidden W, box and column
This is an encountered example, described in http://forum.enjoysudoku.com/windoku-and-xy-chain-t37966.html
Box 1 has all its candidates 1 locked in intersections with W5 and c3.
r5c3 'sees' all these cells with candidate 1 and cannot have a 1.
So r5c3<>1.

Example 8 row, column and Asterisk
The Asterisk says that all its cells with candidate 1 are in row 2 and column 2.
r3c2 'sees' all those cells and cannot be a 1.
So r3c2 <> 1.

Example 9 Asterisk, Windoku and Diagonal
Another example with a Diagonal and an Asterisk and Windoku-box 1.
The \-diagonal says that all its candidate 1 cells are in the intersections with W1 and A.
All cells in W1 and A that see those locked cells are r2c5 and r5c2, which can not hold candidate 1.

All locked cells are in W1 but also in b1 (normal box 1), but it is not a 4-houses problem.
You have 2 solutions for the same situation, the W1 of b1 variant, both are a 3-houses problem.

Above several intersections with 3 houses, but it can be even 4 or more.

Example 10 with 4 intersecting houses.
An Asterisk, Diagonal, a row and a column.
The Asterisk says 'all my candidates 1 are locked in cells within intersections of r2, c8 and the /-diagonal'.
Cell r2c8 'sees' all the 4 locked Asterisk cells with candidates 1, so this r2c8 cannot hold candidate 1.

Creation of a 4-house intersection problem is not that simple. So I appreciate if other examples of 4 (and 5) intersecting houses will be posted.
User avatar
Hajime
 
Posts: 1348
Joined: 20 April 2018
Location: Fryslân

Re: Generalized methods

Postby Hajime » Sun Sep 06, 2020 3:05 pm

Above is explained the Generalized Intersection method.
But there is more, like Generalized 2-string Kite

Gen_Kite.png
Gen_Kite.png (19.24 KiB) Viewed 1124 times


In the picture the "/" (not a "1") are not shown. Please read the conditions below.

Example 1 describes the standard 2-string Kite method:
A row and a column do intersect, but the intersection does not hold candidate k.
The box B around the intersection-cell does hold a lot of candidate k, but at least 1 in the row and column.
The row AND the column holds exactly 1 candidate k outside box B, at position 6 respectively 7.
Now the cell r7c6 cannot hold candidate k. Note the swap for 6 and 7. Because r7c6 "sees" both candidate-cells.

Example 2 holds an Asterisk. Not Box B but the Asterisk holds all candidates k, except 1 per row and column.
Row 3 at position 8 and Column 2 a position 9 holds the candidate "1" outside the Asterisk.
Now the cell r9c8 cannot hold candidate "1". r9c8 "sees" both candidate-cells.

Example 3 holds an extra diagonal of an SudokuX.
Both cells r8c8 and r2c8 "sees" the 2 candidate-cells of row 3 and column 2 outside the Asterisk.
r8c8 and r2c8 can eliminate candidate "1".

Above 3 examples all deal with a row and a column that intersect in some other house.
But it is not necessary that it is a row or a column. It can be any other house.
If appreciated I can try to show an example.

Other examples are welcome.
User avatar
Hajime
 
Posts: 1348
Joined: 20 April 2018
Location: Fryslân

Postby Pat » Wed Apr 19, 2023 6:38 am

Hajime wrote:
Example 5 a row a column and a diagonal

We can eliminate candidate 1 from cells {outside r3}
that 'see' all candidates of row 3.
So r6c6<>1.



Example 6

{diagonal \}

So r3c7<>1.



examples 5-6

interaction between a line and a cell
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Re:

Postby Hajime » Thu Apr 20, 2023 7:51 am

Pat wrote:examples 5-6
interaction between a line and a cell

Yes, you are right!
User avatar
Hajime
 
Posts: 1348
Joined: 20 April 2018
Location: Fryslân

Re: Generalized methods

Postby denis_berthier » Sat Apr 22, 2023 5:37 am

.
All this can be summarised in one sentence, the whips[1] theorem: when a candidate "sees" (i.e. is linked by a direct contradiction to) all the remaining candidates for a CSP-Variable, then it can be eliminated. (The proof is obvious.)
You can see this as "generalised intersections" but it is clear from a theoretical POV that the concept of intersection is not the right one.

Examples for Sudoku were everywhere in [HLS 2007] (there was also a detailed proof that whips[1] are equivalent to "claiming" + "pointing").
Examples mixing rows, columns and diagonals have been given in the 1st edition of [CRT 2011] for N-Queens and in [BUM 2021] for Pandiagonal Latin Squares.
Still more varied examples of this rule for different logic puzzles appeared in [PBCS 2012]. The most striking ones are probably for Kakuro (where the theory of g-labels is far from obvious.)

The existence of whips[1] in a logic puzzle amounts to the existence of g-candidates. It is thus a fundamental property. (An example that doesn't have whips[1] is Latin Squares.)
.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris


Return to Advanced solving techniques

cron