Solving Naked Triples in Sudoku

Question

I wished I paid more attention to the math classes back in Uni. :)

How do I implement this math formula for naked triples?

Naked Triples
Take three cells C = {c1, c2, c3} that share a unit U. Take three numbers N = {n1, n2, n3}. If each cell in C has as its candidates ci ⊆ N then we can remove all ni ∈ N from the other cells in U.**

I have a method that takes a Unit (e.g. a Box, a row or a column) as parameter. The unit contains 9 cells, therefore I need to compare all combinations of 3 cells at a time that from the box, perhaps put them into a stack or collection for further calculation.

Next step would be taking these 3-cell-combinations one by one and compare their candidates against 3 numbers. Again these 3 numbers can be any possible combination from 1 to 9. Thats all I need.

But how would I do that? How many combinations would I get? Do I get 3 x 9 = 27 combinations for cells and then the same for numbers (N)?

How would you solve this in classic C# loops? No Lambda expression please I am already confused enough :)

Code: I had to cut the classes short in order to represent them here.

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];
            }
        }
}

Board

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];
            }
        }
}

Many Thanks for any help,

Answer 1

Psuedo-Code algorithm; my C is a bit rusty.

I recommend finding all of the possible three-number combinations from your candidate values. There can be anywhere from 6 to 504 such combinations, depending on how many candidates you have (given by n!/(3!*(n-3)!) ).

For each one, cycle through all of the cells in the unit and see if they match the condition that they don't have any numbers not in your combination. If a certain combination has three or more, then you can apply it.

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

Hope this helps! I'll C-ify this code if you need it; I've been meaning to brush up on my C anyways.

Also, in case you didn't already know, there's a much simpler way to solve Sudoku puzzles using computers that doesn't involve manually programming in any logic. But I think the way you're trying to do it is quite noble.

---

Generating an array of all possible combos

There are many ways to do this, and there might be a best one; I haven't done any serious research on it myself. I'd recommend google: combination algorithm... I actually found one solution in C myself.

Be sure to include a check to make sure that your number of candidates is appropriate. For n=3, there is only one possible candidate combination, and your algorithm should find it for you. For n=1 and n=2, Naked Triples doesn't even apply.