-
Notifications
You must be signed in to change notification settings - Fork 0
/
HiddenTripletsStrategy.cs
122 lines (114 loc) · 4.91 KB
/
HiddenTripletsStrategy.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
using System;
using System.Collections.Generic;
using System.Linq;
using SudokuBrain.Services;
public class HiddenTripletsStrategy : IStrategy
{
private readonly IMessageLogger _logger;
public HiddenTripletsStrategy(IMessageLogger logger)
{
_logger = logger;
}
public string Name => "Hidden Triplets Strategy";
public int SkillLevel => 7;
private int _searchCombos = 0;
public bool Apply(Puzzle puzzle)
{
bool progress = false;
_searchCombos = 0;
// Iterate each row, column and box, looking for 3 candidates that are only in 3 cells
for (int num = 1; num < 10; num++)
{
var group = puzzle.GetRow(num);
progress = CheckGroup(group) || progress;
group = puzzle.GetColumn(num);
progress = CheckGroup(group) || progress;
group = puzzle.GetBox(num);
progress = CheckGroup(group) || progress;
}
_logger.Log(Name, $"Searched {_searchCombos} group/triplet combos");
return progress;
}
private bool CheckGroup(Group group)
{
bool progress = false;
var candidatesList = new List<char>(group.Candidates);
if (candidatesList.Count >= 3)
{
// Iterate all triples of possible candidates
int combos = Helpers.Factorial(candidatesList.Count) / (Helpers.Factorial(3) * Helpers.Factorial(candidatesList.Count-3));
_searchCombos += combos;
_logger.Log(Name, $"Searching in {group.Description} with {combos} triplet combos");
for (var i=0; i<candidatesList.Count-2; i++)
{
var candidate1 = candidatesList[i];
for (var j=i+1; j<candidatesList.Count-1; j++)
{
var candidate2 = candidatesList[j];
for (var k=j+1; k<candidatesList.Count; k++)
{
var candidate3 = candidatesList[k];
// Find all cells containing 2 or 3 of the candidates
var permutation = new char[] { candidate1, candidate2, candidate3 };
var rejected = false;
var inCells = new List<int>();
for (int cell = 1; cell <= 9; cell++)
{
var cellData = group.GetCell(cell);
if (cellData.Given || cellData.Filled)
{
continue;
}
var foundCandidates = new HashSet<char>(cellData.Candidates);
foundCandidates.IntersectWith(permutation);
if (foundCandidates.Count == 1)
{
rejected = true;
break;
}
if (foundCandidates.Count > 3)
{
throw new Exception("makes no sense");
}
if (foundCandidates.Count > 1)
{
if (inCells.Count >= 3)
{
// This triplet is in too many cells
rejected = true;
break;
}
inCells.Add(cell);
}
}
if (rejected)
{
continue;
}
if (inCells.Count == 3)
{
_logger.Log(Name, $"Found {candidate1}{candidate2}{candidate3} in {group.Description}", SudokuBrain.Models.LogItemLevel.Debug);
// We found a triplet! If it is hidden, expose it
bool exposeProgress = false;
var tripleValues = new char[] {candidate1, candidate2, candidate3};
foreach (var cellNum in inCells)
{
var cellData = group.GetCell(cellNum);
if (cellData.SetOnlyCandidates(tripleValues, Name))
{
exposeProgress = true;
}
}
if (exposeProgress)
{
_logger.Log(Name, $"{candidate1}{candidate2}{candidate3} in {group.Description}");
progress = true;
}
}
}
}
}
}
return progress;
}
}