Kein-diagonaler-Nachfolger Sudoku

[surbier]

Habe eine Frage,

Kennt jemand diagonale non-consecutive Sudokus,
also Sudokus ohne Puenktchen und Balken, bei denen
in den diagonal benachbarten Zellen keine Nachfolger
stehen duerfen?

Ich habe mir ein paar Loesungsmethoden ueberlegt
und wollte die mal vergleichen.
Auf sachsentext, auf den Links dort und anderswo wurde ich nicht fuendig.

Danke

[surbier]

Ich meine z.B. sowas:

Code:

094000530500103008200050004400000001300000009010000040005000100000501000000070000

. 9 4 . . . 5 3 .
5 . . 1 . 3 . . 8
2 . . . 5 . . . 4
4 . . . . . . . 1
3 . . . . . . . 9
. 1 . . . . . 4 .
. . 5 . . . 1 . .
. . . 5 . 1 . . .
. . . . 7 . . . .

Code:

194286537576143928283957614452398761367412859819765243745639182938521476621874395                    

1 9 4 2 8 6 5 3 7
5 7 6 1 4 3 9 2 8
2 8 3 9 5 7 6 1 4
4 5 2 3 9 8 7 6 1
3 6 7 4 1 2 8 5 9
8 1 9 7 6 5 2 4 3
7 4 5 6 3 9 1 8 2
9 3 8 5 2 1 4 7 6
6 2 1 8 7 4 3 9 5

Ich denk mir, diese Sudokuvariante muss es doch bereits geben.

[Pyrrhon]

Diesen Typ hat bisher wohl keiner versucht. Allerdings gibt es ähnliche Varianten:

Touchy
http://www.logicmastersindia.com/4875E02...ctions.pdf

Fill in the grid from 1 through 9 so that every row, every column and every outlined region contains distinct digits. Each digit has at least one consecutive adjacent (sharing edges) neighbor.

Triads
http://www.fed-sudoku.eu/sudokuplay/0062en.swf

Fill in the grid with the digits from 1 - 9 so that each 3x3 box contains each number exactly once. (The sudoku rules for rows and columns are not required.) The digits 2,5,8 appear in coloured cells only. There a greater-less signs between adjazent some cells. Every marked digit contains exactly two adjacent cells with consecutive numbers. All other cells have at most one consecutive neighbour.

Wenn Du nach Techniken für die Variante suchst, bekommst Du vielleicht unter

http://www.djape.net/sudoku/forum/viewto...47&start=5

Anregungen.

Uwe

[euklid]

Ich kenne nur non-consecutive sudokus, dort gilt die Regel, dass benachbarte Zahlen NIE nebeneinander stehen duerfen (weder waagrecht, senkrecht, noch diagonal).

Siehe z.B.
*) Fed-Sudoku: http://www.fed-sudoku.eu/enindex.php?co=
*) Sudoku Champions Canada: http://www.sudoku-champions.ca/ (nur Mittwochs)

LG, Stefan

[surbier]

Danke fuer die schnelle Suche.

Ich sollte vielleicht noch als Hintergrund sagen, dass ich mich letztens mit normalen non-consecutives beschaeftigt
habe und mir dazu ein paar Tricks ueberlegt habe. Irgendwann stiess ich auf die djape Seite und fand, dass ich mir die
meiste Muehe haette sparen koennen. Ich habe die Tricks programmiert und kann mir nun schoene NC Sudokus
mit vorgegebener Schwierigkeit erzeugen.

Dabei kam mir die Idee mit diagonal-NC. Ich (mein Programm) kann wie oben gezeigt eindeutige diagonal-NCs erzeugen,
zum Loesen braucht man dann doch die speziellen Tricks. Ich dachte ich koennte mir diesmal
die Muehe sparen, aber wenn's diese Variante nicht gibt oder nicht bekannt ist, muss ich auf die
Ausschlussmoeglichkeiten zurueckgreifen die ich mir bist jetzt ueberlegt habe.
Vielleicht sollte ich die mal posten.

Sudokus mit der NC Regel in waagrecht/senkrecht und diagonaler Richting wird
es wohl nur mit Zusatzbedingung geben, denn fuer die Zahl in der Mitte eines Blocks geht das so nicht;
da muessen doch immer die anderen 8 Ziffern drumherumstehen, wovon mindestens eine benachbart sein muss.

Danke nochmal,
surbier

[Pyrrhon]

Ich dachte ich koennte mir diesmal
die Muehe sparen, aber wenn's diese Variante nicht gibt oder nicht bekannt ist, muss ich auf die
Ausschlussmoeglichkeiten zurueckgreifen die ich mir bist jetzt ueberlegt habe.
Vielleicht sollte ich die mal posten.

Ja, poste sie bitte, Lösungstricks sind doch immer spannend.


Uwe

[CHalb]

Vielleicht sollte ich die mal posten.

@Surbier: Oder stell solch ein Rätsel mal ins Portal. Genug Erfahrung habt ihr beiden (also dein PC und du) ja wahrscheinlich.

[euklid]

Korrektur: In meinem obigen Beispiel meinte ich natuerlich ganz normale non-consecutives, also keine +-1 Nachbarn waagrecht und senkrecht. Wie surbier schon schrieb ist es kontraproduktiv, non-consecutives auf waagrecht, senkrecht UND diagonal auszuweiten... :-)

LG,
Stefan

[surbier]

Also dann hier die Loesungstricks:

@ Pyrrhon: Die meisten sind sowieso Tricks von dir, aus dem djape thread 2006, die ich hier fuer die Diagonal-Regel adaptiert habe.

Ich habe die Tricks nicht ausfuehrlich erklaert. Man kann sich aber jeden Ausschluss mit einer kleinen
Fallunterscheidung klarmachen. Die Ein-Ziffer Block Regeln kann man auch mit einem Satz zusammenfassen,
aber fuer einen Spieler sind diese griffigen Muster besser; denk ich mir.


DiagnonalNachbar Regel (= Definition)
======================================

Steht in einer Zelle bereits eine Ziffer a koennen in den direkten
diagonalen Nacharzellen weder a+1 noch a-1 stehen:

Code:

-4,-6  .   -4,-6

  .    5     .

-4,-6  .   -4,-6

Ein-Ziffer Regeln
=================

Ein-Ziffer Regel Diagonale:
---------------------------

Die folgenden AusschlussRegeln (bekannt fuer normale waagrecht/senkrecht
non-consecutive Sudokus) gibt es nicht fuer die Diagonale:

Zwei Direkte Nachbarn Regel
Zwei Getrennte Nachbarn Regel
Drei Nachbarn Regel

Der Grund hierfuer ist, dass in einer Reihe eine Zahl immer nur einmal
stehen muss; entlang einer Diagonalen aber kann eine Ziffer aber 0 mal,
1 mal oder mehrmals stehen.

Ein-Ziffer Regel Reihe
-----------------------

Steht ein Kandidat genau zweimal in einer Reihe durch eine Zelle getrennt,
koennen a+1 und a-1 aus den beiden gemeinsamen diagonalen Nachbarzellen
gestrichen werden.

Code:

. -4,-6 .

5   .   5

. -4,-6 .

Ein-Ziffer Regel Block
----------------------

Fuenf Regel

Code:

a    .    a

.   -a    .

a    .    a

Steht ein Kandidat in dieser Anordnung genau fuenf mal innerhalb eines Blocks
koennen a+1 und a-1 in der Mitte gestrichen werden.

Alle weiteren Block Stellungen lassen sich als Teilbelegung
der Fuenf Regel ableiten:


Vier Regel:
Steht ein Kandidat in dieser Anordnung genau vier mal innerhalb eines Blocks
koennen a+1 und a-1 in der Mitte gestrichen werden.

Code:

a    .    a

.    -    .

a    .    a

Drei Regel:
Steht ein Kandidat in dieser Anordnung genau drei mal innerhalb eines Blocks
koennen a+1 und a-1 im Angelpunkt gestrichen werden. Drehung und Verschiebung
der Anordung innerhalb des Blocks erlaubt.

Code:

a    .    .

.   -a    .

a    .    .

Zwei:

Code:

a    .    .

.    -    .

a    .    .

Das ist bereits die getrennte Nachbarn in Reihe Regel. Auch diese
Stellung kann als zwei mal 'Getrennte Nachbarn in Reihe' Regel ansehen.

Code:

a    .    .

.    -    .

a    .    a

Steht eine Kandidat genau zweimal innerhalb eines Blocks,
diagonal benachbart:

Code:

.    .   -a

.   -a    .

.    .    .

kann a-1 und a+1 in !!beiden!! Zellen ausgeschlossen werden.
Diese Regel entspricht der 'Direkte Nachbar Regel' bei NC Sudokus.

Steht eine Kandidat genau dreimal innerhalb eines Blocks,
diagonal benachbart:

Code:

.    .    a

.   -a    .

a    .    .

kann a-1 und a+1 in beiden Zellen ausgeschlossen werden.
Diese Regel entspricht der 'Drei Nachbar Regel' bei NC Sudokus.

Steht ein Kandidat genau zweimal innerhalb eines Blocks,
diagonal gegenueber, eine Zelle dazwischen:

Code:

.    .    a

.    -    .

a    .    .

kann a-1 und a+1 in der Zelle dazwischen ausgeschlossen werden.
Diese Regel entspricht der 'Getrennte Nachbar Regel' bei NC Sudokus.


Mehr-Kandidaten Regeln
======================

Eine Zelle
----------

Stehen in einer Zelle nur zwei Ziffern a-1 und a+1, (z.B. [46]),
kann in den vier diagonalen Nachbarn der Kandidat a gestrichen werden.

(Anders als beim senkr./waagr NC Sudoku ergeben die Kombinationen [a,a+1]
und [a-1,a,a+1] keine Ausschluesse.)

Zwei Zellen
-----------

Die folgenden beiden Stellungen
innerhalb eines Block sind verboten:

Code:

[45] []
[]   [45]

Zwei diagonal benachbarte Zwei-Kandidaten-Zellen
mit benachbarten Kandidaten.

Code:

[456] []    []
[]    [456] []
[]    []    [456]

Drei diagonal benachbarte Drei-Kandidaten-Zellen mit drei benachbarten
Kandidaten.

Deshalb bindet die folgende Stellung

Code:

[a,a+1] []         []
[]      [a,a+1,b]  []
[]      []         []

den Kandidaten b an die beiden Zellen.
Der Kandidat b kann ueberall sonst im Block gestrichen werden.
(Auf der Diagonalen ausserhalb des Blocks kann er noch stehen.)


ebenso

Code:

[a-1,a,a+1] []          []
[]          [a-1,a,a+1] []
[]          []          [a-1,a,a+1,b]

Sowie deren Teilbelegungen, also z.B.

Code:

[a,a+1] []        []
[]      [a-1,a+1] []
[]      []        [a-1,a,b]

_O_

Ich hoffe ich habe mich nigendwo vertan. Gruesse surbier

[Pyrrhon]

Naja die meisten der Regeln auf der verlinkten Seite sind nicht von mir. udosuk und jcbonsai haben mindestens ebensoviel beigetragen. Die Regeln gelten, wenn man ihren Gehalt korrekt formuliert alle weiter. Sie gelten dann z. B. auch für Kropki & Co. Fügt man noch die Neuerungen von surbier (Teil der Regeln 7, 8 und die Regel 9) in der allgemeinen Form hinzu, ergibt sich die folgende Liste von Techniken:

Zur Erläuterung:

• starker Link zwischen zwei Zellen mit dem Wert a, heißt genau eine der beiden Zellen muß a enthalten
  
• zwei Zellen sind Buddies (= sie sehen einander), wenn sie nicht denselben Wert haben dürfen (das kann heißen sie sind in derselben Zeile, Spalte, Box, Diagonale, Summe, Extraregion, ...).
  
• zwei Zellen sind nicht-konsekutive Nachbarn, wenn sie nicht konsekutiv sein dürfen. (ihre Differenz nicht 1 sein darf)
  

Im Falle

• von Kropki sind das Zellen zwischen denen sich kein Punkt befindet, oder Zellen zwischen denen sich ein schwarzer Punkt befindet und aus irgendeinem Grund die Kombination 1 - 2 ausgeschlossen ist.
  
• von konsekutiven Sudoku, Hochhäusern ... sind das Felder zwischen denen kein Zeichen steht.
  
• von nicht-konsekutiven Sudoku sind das orthogonal benachbarte Zellen
  
• in der hier diskutierten Variante sind das diagonal benachbarte Zellen
  
• von Differenzsudoku sind das Felder zwischen denen eine Differenz > 1 steht.
  
• von Bruchsudoku sind das Felder zwischen denen ein Bruch steht, der nicht n/(n+1) ist (nach dem Kürzen)
  

Nun zu den Techniken:

1. Nachbarregel: Wenn eine Zelle den Wert a enthält, kann kein nicht-konsekutiver Nachbar die Werte a-1 oder a+1 enthalten
   
2. Wenn eine Zelle die Werte {a-1,a+1} enthält, dann kann kein nicht-konsekutiver Nachbar den Wert a enthalten.
   
3. Wenn eine Zelle die Werte {a,a+1} enthält, kann kein nicht-konsekutiver Nachbar, der Buddie der Zelle ist, diese Werte enthalten.
   
4. Wenn eine Zelle die Werte {a-1,a,a+1} enthält, kann kein nicht-konsekutiver Nachbar, der Buddie der Zelle ist, den Wert a enthalten.
   
5. Wenn ein Paar von nichtkonsekutiv benachbarten Zellen einen bestimmten Kandidaten a enthalten muss (starker Link), dann können diese beiden Zellen a -1 und a + 1 nicht enthalten
   
6. Wenn ein Paar von Zellen einen bestimmten Kandidaten a enthalten muss (starker Link), dann können alle Zellen, die nicht-konsekutiver Nachbar von beiden Zellen sind, a -1 und a + 1 nicht enthalten
   
7. Wenn ein Triple von Zellen einen bestimmten Kandidaten a enthalten muss, dann können alle Zellen, die nicht-konsekutiver Nachbar von all diesen Zellen sind, a -1 und a + 1 nicht enthalten. Dies gilt auch für eine Zelle der Triples, wenn sie nicht-konsekutiver Nachbar der anderen beiden Zellen des Triples ist.
   
8. Wenn ein Quad von Zellen einen bestimmten Kandidaten a enthalten muss, dann können alle Zellen, die nicht-konsekutiver Nachbar von all diesen Zellen sind, a -1 und a + 1 nicht enthalten. Dies gilt auch für eine Zelle des Quads, wenn sie nicht-konsekutiver Nachbar der anderen drei Zellen des Quads ist.
   
9. Wenn ein Quintett von Zellen einen bestimmten Kandidaten a enthalten muss, dann können alle Zellen, die nicht-konsekutiver Nachbar von all diesen Zellen sind, a -1 und a + 1 nicht enthalten. Dies gilt auch für eine Zelle des Quintetts, wenn sie nicht-konsekutiver Nachbar der anderen vier Zellen des Quintetts ist.
   
10. Wenn zwei nicht-konsekutive Nachbarn nur die Werte {a, a+1, b} und {a, a+1,b} (oder eine Teilmenge davon, die b einschließt) enthalten können, dann können alle Zellen die Buddie von beiden sind, den Wert b nicht enthalten (oder allgemeiner dann besteht ein starker Link bezüglich von b zwischen diesen Zellen).
    
11. Wenn zwei nicht-konsekutive Nachbarn, die Buddies sind, nur die Werte {a-1,a,a+1,b} und {a,b} enthalten, dann können alle Zellen die Buddie von beiden sind, den Wert b nicht enthalten (oder allgemeiner dann besteht ein starker Link bezüglich von b zwischen diesen Zellen).
    
12. Wenn drei Zellen z1={a,b,c}, z2 = {a-1,a,a+1,b,c}, z3={a,b,c} mit z2 ist nicht-konsekutiver Nachbar zu z1 und z3, und z1, z2, z3 sind paarweise Buddies, dann können b und c in keiner Zelle stehen, die von allen drei Zellen gesehen wird. Dies gilt auch für Teilmengen in z1, z2, z3, wenn mindestens eine Zell b und mindestens eine Zelle c enthält.
    
13. Wenn drei Zellen z1, z2, z3 = {a-1,a,a+1,b} mit z2 ist nicht-konsekutiver Nachbar zu z1 und z3, und z1, z2, z3 sind paarweise Buddies, dann kann b in keiner Zelle stehen, die von allen drei Zellen gesehen wird. Dies gilt auch für Teilmengen in z1, z2, z3, wenn mindestens eine Zell b enthält.
    
14. Wenn drei Zellen z1, z2, z3 mit z2 ist nicht-konsekutiver Nachbar zu z1 und z3, und z1, z2, z3 sind paarweise Buddies. Wenn zu dem 2 der Werte {a-1,a,a+1} in diesen drei Zellen vorkommen müssen, dann kann der dritte Wert nicht vorkommen.
    
15. Non Cons Naked Pair (Variante a)
    • Wenn drei Zellen z1 = {a,a+1,a+2,a+3}, z2 = {a,a+1,a+2,a+3}, z3 = {a+2,a+3} mit z2 ist nicht-konsekutiver Nachbar zu z1 und z3, und z1, z2, z3 sind paarweise Buddies, dann kann a+2 und a+3 in keiner Zelle stehen, die von allen drei Zellen gesehen wird. Dies gilt auch für Teilmengen in z1, z2, z3.
      
    • Wenn drei Zellen z1 = {a, a+1,a+2,a+3}, z2 = {a,a+1,a+2,a+3}, z3 = {a,a+1} mit z2 ist nicht-konsekutiver Nachbar zu z1 und z3, und z1, z2, z3 sind paarweise Buddies, dann kann a und a+1 in keiner Zelle stehen, die von allen drei Zellen gesehen wird. Dies gilt auch für Teilmengen in z1, z2, z3.
      
16. Non Cons Naked Pair (Variante b)
    • Wenn vier Zellen z1 = {a, a+1,a+2,a+3}, z2 = {a, a+1, a+2,a+3}, z3 = {a+2,a+3,b,b+1}, z4 = {a+2,a+3,b,b+1} mit z1 und z2 sind nicht-konsekutive Nachbarn, z3 und z4 sind nicht-konsekutive Nachbarn und z1, z2, z3,z4 sind paarweise Buddies, dann kann a+2 und a+3 in keiner Zelle stehen, die von allen drei Zellen gesehen wird. Dies gilt auch für Teilmengen in z1, z2, z3,z4.
      
    • Wenn vier Zellen z1 = {a, a+1,a+2,a+3}, z2 = {a, a+1, a+2,a+3}, z3 = {a,a+1,b,b+1}, z4 = {a,a+1,b,b+1} mit z1 und z2 sind nicht-konsekutive Nachbarn, z3 und z4 sind nicht-konsekutive Nachbarn und z1, z2, z3,z4 sind paarweise Buddies, dann kann a und a+1 in keiner Zelle stehen, die von allen drei Zellen gesehen wird. Dies gilt auch für Teilmengen in z1, z2, z3,z4.
      
17. Spezialfall Unmögliche Kombination
    
    1. Wenn drei Zellen z1 = {a, a+1,a+2,a+3}, z2 = {a,a+1,a+2,a+3}, z3 = {a+1,a+3} mit z1 und z2 sind nicht-konsekutive Nachbarn, und z1, z2, z3 sind paarweise Buddies, dann kann a in keiner Zelle stehen, die von z1 und z2 gesehen wird. Dies gilt auch für Teilmengen in z1, z2, z3.
       
    2. Wenn drei Zellen z1 = {a, a+1,a+2,a+3}, z2 = {a,a+1,a+2,a+3}, z3 = {a,a+2} mit z1 und z2 sind nicht-konsekutive Nachbarn, und z1, z2, z3 sind paarweise Buddies, dann kann a+3 in keiner Zelle stehen, die von z1 und z2 gesehen wird. Dies gilt auch für Teilmengen in z1, z2, z3.
18. Wenn drei Zellen z1, z2, z3 sowohl den a als auch den Wert a+1 enthalten müssen und z1, z2, z3 paarweise Buddies sowie z1 und z2 nicht-konsekutiv benachbart sind, dann kann z3 nur die Werte {a, a+1} enthalten und keine anderen.

Die anderen Fälle der unmöglichen Kombination sowie die Wings ... lasse ich hier mal weg.

Uwe