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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
use crate::core::SolvePath;
use super::{TechniquePropagator, TechniqueRule, units};
/// Jellyfish technique implementation.
///
/// A Jellyfish is a generalization of Swordfish from 3 defining lines to 4.
/// For a candidate digit, if it appears in at most 4 positions across exactly
/// 4 rows, and those positions collectively span exactly 4 columns, then that
/// candidate can be eliminated from those 4 columns in all other rows.
/// The same logic applies symmetrically for columns → rows.
pub struct Jellyfish;
impl Jellyfish {
fn find_row_based_jellyfish(
prop: &mut TechniquePropagator,
candidate_bit: u16,
path: &mut SolvePath,
flags: crate::core::TechniqueFlags,
) -> bool {
let eligible_rows = Self::find_eligible_units(prop, candidate_bit, units::UnitType::Row);
let mut eliminations_made = false;
for i in 0..eligible_rows.len() {
for j in (i + 1)..eligible_rows.len() {
for k in (j + 1)..eligible_rows.len() {
for l in (k + 1)..eligible_rows.len() {
let (r1, ref cols1) = eligible_rows[i];
let (r2, ref cols2) = eligible_rows[j];
let (r3, ref cols3) = eligible_rows[k];
let (r4, ref cols4) = eligible_rows[l];
let mut col_set: u16 = 0;
for &c in cols1
.iter()
.chain(cols2.iter())
.chain(cols3.iter())
.chain(cols4.iter())
{
col_set |= 1 << c;
}
if col_set.count_ones() == 4 {
let defining_rows = [r1, r2, r3, r4];
let cols: Vec<usize> =
(0..9).filter(|&c| col_set & (1 << c) != 0).collect();
for &col in &cols {
for row in 0..9 {
if !defining_rows.contains(&row)
&& prop.board.is_empty(row, col)
&& (prop.candidates.get(row, col) & candidate_bit) != 0
{
eliminations_made |= prop.eliminate_candidate(
row,
col,
candidate_bit,
flags,
path,
);
}
}
}
}
}
}
}
}
eliminations_made
}
fn find_column_based_jellyfish(
prop: &mut TechniquePropagator,
candidate_bit: u16,
path: &mut SolvePath,
flags: crate::core::TechniqueFlags,
) -> bool {
let eligible_cols = Self::find_eligible_units(prop, candidate_bit, units::UnitType::Column);
let mut eliminations_made = false;
for i in 0..eligible_cols.len() {
for j in (i + 1)..eligible_cols.len() {
for k in (j + 1)..eligible_cols.len() {
for l in (k + 1)..eligible_cols.len() {
let (c1, ref rows1) = eligible_cols[i];
let (c2, ref rows2) = eligible_cols[j];
let (c3, ref rows3) = eligible_cols[k];
let (c4, ref rows4) = eligible_cols[l];
let mut row_set: u16 = 0;
for &r in rows1
.iter()
.chain(rows2.iter())
.chain(rows3.iter())
.chain(rows4.iter())
{
row_set |= 1 << r;
}
if row_set.count_ones() == 4 {
let defining_cols = [c1, c2, c3, c4];
let rows: Vec<usize> =
(0..9).filter(|&r| row_set & (1 << r) != 0).collect();
for &row in &rows {
for col in 0..9 {
if !defining_cols.contains(&col)
&& prop.board.is_empty(row, col)
&& (prop.candidates.get(row, col) & candidate_bit) != 0
{
eliminations_made |= prop.eliminate_candidate(
row,
col,
candidate_bit,
flags,
path,
);
}
}
}
}
}
}
}
}
eliminations_made
}
fn find_eligible_units(
prop: &TechniquePropagator,
candidate_bit: u16,
unit_type: units::UnitType,
) -> Vec<(usize, Vec<usize>)> {
let mut result = Vec::new();
for unit_idx in 0..9 {
let unit_cells = match unit_type {
units::UnitType::Row => units::row_cells(unit_idx),
units::UnitType::Column => units::col_cells(unit_idx),
};
let positions: Vec<usize> = unit_cells
.iter()
.enumerate()
.filter(|&(_, &(r, c))| {
prop.board.is_empty(r, c) && (prop.candidates.get(r, c) & candidate_bit) != 0
})
.map(|(pos, _)| pos)
.collect();
if positions.len() >= 2 && positions.len() <= 4 {
result.push((unit_idx, positions));
}
}
result
}
}
impl TechniqueRule for Jellyfish {
fn apply(&self, prop: &mut TechniquePropagator, path: &mut SolvePath) -> bool {
let mut eliminations_made = false;
for candidate_val in 1..=9 {
let candidate_bit = 1 << (candidate_val - 1);
eliminations_made |=
Self::find_row_based_jellyfish(prop, candidate_bit, path, self.flags());
eliminations_made |=
Self::find_column_based_jellyfish(prop, candidate_bit, path, self.flags());
}
eliminations_made
}
fn flags(&self) -> crate::core::TechniqueFlags {
crate::core::TechniqueFlags::JELLYFISH
}
}
#[cfg(test)]
mod tests {
use crate::core::{Rustoku, SolvePath, SolveStep, TechniqueFlags};
#[test]
fn test_jellyfish_eliminates_from_correct_lines() {
// Hodoku Jellyfish example
// https://hodoku.sourceforge.net/en/show_example.php?file=bf401&tech=Jellyfish
let s = "200000003080030050003402100001205400000090000009308600002506900090020070400000001";
let mut rustoku = Rustoku::new_from_str(s).unwrap().with_techniques(
TechniqueFlags::EASY | TechniqueFlags::MEDIUM | TechniqueFlags::JELLYFISH,
);
let mut path = SolvePath::default();
rustoku.techniques_make_valid_changes(&mut path);
let eliminations: Vec<_> = path
.steps
.iter()
.filter_map(|step| match step {
SolveStep::CandidateElimination {
row,
col,
value,
flags,
..
} if flags.contains(TechniqueFlags::JELLYFISH) => Some((*row, *col, *value)),
_ => None,
})
.collect();
assert!(
!eliminations.is_empty(),
"Jellyfish should produce at least one candidate elimination"
);
for &(r, c, v) in &eliminations {
let cand_bit = 1u16 << (v - 1);
let remaining = rustoku.candidates.get(r, c);
assert_eq!(
remaining & cand_bit,
0,
"Candidate {v} should be eliminated from ({r},{c}) by Jellyfish"
);
}
// Verify that initial clues were not altered
let original = crate::core::Board::try_from(s).unwrap();
for r in 0..9 {
for c in 0..9 {
let orig_val = original.get(r, c);
if orig_val != 0 {
assert_eq!(
rustoku.board.get(r, c),
orig_val,
"Clue at ({r},{c}) was overwritten"
);
}
}
}
}
}