Lösen von nackten Dreiecken in Sudoku

Question

Ich wünschte, ich hätte mehr Aufmerksamkeit auf die Mathe-Klassen zurück in Uni. :)

Wie implementiere ich diese mathematische Formel für nackte Tripel?

Naked Triples
Nehmen drei Zellen C = {c1, c2, c3}, die eine Einheit U. drei Zahlen Nehmen teilen N = {n1, n2, n3}. Wenn jede Zelle in C ihre Kandidaten ci ∈ N hat, dann können wir alle ni ∈ N aus den anderen Zellen in U entfernen. **

Ich habe eine Methode, die eine Unit (zB eine Box, eine Zeile oder eine Spalte) als Parameter. Die Einheit enthält 9 Zellen, daher muss ich alle Kombinationen von 3 Zellen zu einer Zeit, die aus der Box, vielleicht in einen Stapel oder Sammlung für die weitere Berechnung.

Nächster Schritt wäre, diese 3-Zellen-Kombinationen nacheinander zu nehmen und ihre Kandidaten mit 3 Zahlen zu vergleichen. Wieder können diese 3 Zahlen jede mögliche Kombination von 1 bis 9 sein. Das ist alles was ich brauche.

Aber wie würde ich das tun? Wie viele Kombinationen würde ich bekommen? Bekomme ich 3 x 9 = 27 Kombinationen für Zellen und dann dasselbe für Zahlen (N)?

Wie würden Sie das in klassischen C# Loops lösen? Kein Lambda Ausdruck bitte ich bin schon genug verwirrt :)

Code: Ich habe die Klassen kurz geschnitten um sie hier darzustellen.

public class Cell : INotifyPropertyChanged 
    { 

public ObservableCollection<ObservableCollection<Candidate>> CandidateActual {...} 

public int Id { ... } 

//Position of the Cell inside a box if applicable 
public int CellBoxPositionX { get; private set; } 
public int CellBoxPositionY { get; private set; } 

//Position of the Cell inside the game board 
public int CellBoardPositionX { get; private set; } 
public int CellBoardPositionY { get; private set; } 

//Position of the Box inside the game board 
public int BoxPositionX { get; private set; } 
public int BoxPositionY { get; private set; } 

public int CountCandidates { ... }  
public int? Value { ...} 

public Candidate this[int number] 
     { 
      get 
      { 
       if (number < 1 || number > PossibleValues.Count) 
       { 
        throw new ArgumentOutOfRangeException("number", number, "Invalid Number Index"); 
       } 

       switch (number) 
       { 
        case 1: 
         return CandidateActual[0][0]; 
        case 2: 
         return CandidateActual[0][1]; 
        case 3: 
         return CandidateActual[0][2]; 
        case 4: 
         return CandidateActual[1][0]; 
        case 5: 
         return CandidateActual[1][1]; 
        case 6: 
         return CandidateActual[1][2]; 
        case 7: 
         return CandidateActual[2][0]; 
        case 8: 
         return CandidateActual[2][1]; 
        case 9: 
         return CandidateActual[2][2]; 
        default: 
         return null; 
       } 
      } 
     } 
} 

Candidate

public class Candidate : INotifyPropertyChanged 
    { 

     private int? _value; 

     public int? Value { ... } 

    } 

Box:

public class Box : INotifyPropertyChanged 
    { 

public ObservableCollection<ObservableCollection<Cell>> BoxActual { ... } 

public Cell this[int row, int column] 
     { 
      get 
      { 
       if(row < 0 || row >= BoxActual.Count) 
       { 
        throw new ArgumentOutOfRangeException("row", row, "Invalid Row Index"); 
       } 
       if(column < 0 || column >= BoxActual.Count) 
       { 
        throw new ArgumentOutOfRangeException("column", column, "Invalid Column Index"); 
       } 
       return BoxActual[row][column]; 
      } 
     } 
} 

Vorstand

public class Board : INotifyPropertyChanged 
    { 

public ObservableCollection<ObservableCollection<Box>> GameBoard {...} 

public Cell this[int boardRowPosition, int boardColumnPosition] 
     { 
      get 
      { 
       int totalSize = GameBoard.Count*GameBoard.Count(); 
       if (boardRowPosition < 0 || boardRowPosition >= totalSize) 
        throw new ArgumentOutOfRangeException("boardRowPosition", boardRowPosition, "Invalid boardRowPosition index"); 
       if (boardColumnPosition < 0 || boardColumnPosition >= totalSize) 
        throw new ArgumentOutOfRangeException("boardColumnPosition", boardColumnPosition, "Invalid boardColumnPosition index"); 
       return 
        GameBoard[boardRowPosition/GameBoard.Count][boardColumnPosition/GameBoard.Count][ 
         boardRowPosition%GameBoard.Count, boardColumnPosition%GameBoard.Count]; 
      } 
     } 



     public Box this[int boardRowPosition, int boardColumnPosition, bool b] 
     { 
      get 
      { 
       int totalSize = GameBoard.Count * GameBoard.Count(); 
       if (boardRowPosition < 0 || boardRowPosition >= totalSize) 
        throw new ArgumentOutOfRangeException("boardRowPosition", boardRowPosition, "Invalid boardRowPosition index"); 
       if (boardColumnPosition < 0 || boardColumnPosition >= totalSize) 
        throw new ArgumentOutOfRangeException("boardColumnPosition", boardColumnPosition, "Invalid boardColumnPosition index"); 
       return 
        GameBoard[boardRowPosition/GameBoard.Count][boardColumnPosition/GameBoard.Count]; 
      } 
     } 
} 

Vielen Dank für jede Hilfe,

Answer 1

Psuedo-Code-Algorithmus; mein C ist ein bisschen eingerostet.

Ich empfehle, alle möglichen Drei-Zahlen-Kombinationen aus Ihren Kandidatenwerten zu finden. Es kann zwischen 6 und 504 solcher Kombinationen geben, abhängig davon, wie viele Kandidaten Sie haben (gegeben durch n!/(3! * (N-3)!)).

Wechseln Sie für jeden Zyklus durch alle Zellen in der Einheit und sehen Sie, ob sie mit der Bedingung übereinstimmen, dass sie keine Zahlen haben, die nicht in Ihrer Kombination enthalten sind. Wenn eine bestimmte Kombination drei oder mehr hat, können Sie sie anwenden.

combos = (array containing 3-long combination of candidates) 
for each combo in combos     # iterate through every combo 
    matches = new array     # initialize a blank array 
    for each cell in unit 
    if (cell does not contain candidates other than the ones in your current combo) 
     matches.add(cell)     # this is a match! 
    end 
    end 

    if matches.size >= 3     # naked triple found! (three matches for given combo) 
    for each cell in unit 
     if (cell is not in matches) 
     (delete every candidate in current combo in this cell) 
     end 
    end 
    end 
    delete matches       # clear up memory 
end 

hoffe, das hilft! Ich werde diesen Code c-ify, wenn Sie es brauchen; Ich wollte sowieso mein C auffrischen.

Wenn Sie es noch nicht wissen, gibt es eine viel einfachere Möglichkeit, Sudoku-Rätsel mit Computern zu lösen, die keine manuelle Programmierung in irgendeiner Logik erfordern. Aber ich denke, die Art, wie Sie es versuchen, ist ziemlich edel.

---

Erzeugen eines Array aller möglichen Kombinationen

Es gibt viele Möglichkeiten, dies zu tun, und es könnte eine beste sein; Ich habe selbst keine ernsthaften Nachforschungen darüber angestellt. Ich würde empfehlen, google: combination algorithm ... Ich fand tatsächlich one solution in C mich.

Stellen Sie sicher, dass Sie eine Überprüfung durchführen, um sicherzustellen, dass Ihre Anzahl an Bewerbern angemessen ist. Für n = 3 gibt es nur eine mögliche Kandidatenkombination, und Ihr Algorithmus sollte sie für Sie finden. Für n = 1 und n = 2 gilt Naked Triples nicht einmal.