Coverage for src / hodoku / solver / uniqueness.py: 98%

1"""Uniqueness solver: Uniqueness Tests 1-6, Hidden Rectangle, BUG+1, 

2Avoidable Rectangles 1-2. 

3 

4Mirrors Java's UniquenessSolver. 

5""" 

6 

7from __future__ import annotations 

8 

9from hodoku.core.grid import BLOCKS, BUDDIES, COLS, CONSTRAINTS, Grid, LINES 

10from hodoku.core.solution_step import Candidate, SolutionStep 

11from hodoku.core.types import SolutionType 

12 

13_UT_TYPES = frozenset({ 

14 SolutionType.UNIQUENESS_1, 

15 SolutionType.UNIQUENESS_2, 

16 SolutionType.UNIQUENESS_3, 

17 SolutionType.UNIQUENESS_4, 

18 SolutionType.UNIQUENESS_5, 

19 SolutionType.UNIQUENESS_6, 

20 SolutionType.HIDDEN_RECTANGLE, 

21}) 

22 

23_AR_TYPES = frozenset({ 

24 SolutionType.AVOIDABLE_RECTANGLE_1, 

25 SolutionType.AVOIDABLE_RECTANGLE_2, 

26}) 

27 

28# Bitmask for all 9 digits (bits 0-8 → digits 1-9) 

29_ALL_DIGITS = (1 << 9) - 1 

30 

31 

32class UniquenessSolver: 

33 """Uniqueness Tests 1–6, Hidden Rectangle, BUG+1.""" 

34 

35 def __init__(self, grid: Grid) -> None: 

36 self.grid = grid 

37 

38 def get_step(self, sol_type: SolutionType) -> SolutionStep | None: 

39 if sol_type in _UT_TYPES: 

40 return self._find_ur(sol_type) 

41 if sol_type in _AR_TYPES: 

42 return self._find_ar(sol_type, only_one=True) 

43 if sol_type == SolutionType.BUG_PLUS_1: 

44 return self._find_bug_plus_1() 

45 return None 

46 

47 def find_all(self, sol_type: SolutionType) -> list[SolutionStep]: 

48 if sol_type in _UT_TYPES: 

49 return self._find_ur_all(sol_type) 

50 if sol_type in _AR_TYPES: 

51 results: list[SolutionStep] = [] 

52 self._find_ar(sol_type, only_one=False, results=results) 

53 return results 

54 if sol_type == SolutionType.BUG_PLUS_1: 

55 step = self._find_bug_plus_1() 

56 return [step] if step is not None else [] 

57 return [] 

58 

59 def _find_ur_all(self, target_type: SolutionType) -> list[SolutionStep]: 

60 """Return ALL UR steps of the given type.""" 

61 grid = self.grid 

62 seen_rects: set[tuple[int, int, int, int]] = set() 

63 results: list[SolutionStep] = [] 

64 allowed = self._compute_allowed() 

65 

66 # Java only starts from bivalue cells (getAnzCandidates(i) == 2) 

67 for i11 in range(81): 

68 if grid.values[i11] != 0: 

69 continue 

70 if bin(grid.candidates[i11]).count("1") != 2: 

71 continue 

72 cands = [d for d in range(1, 10) if grid.candidates[i11] >> (d - 1) & 1] 

73 cand1, cand2 = cands[0], cands[1] 

74 self._find_ur_for_pair( 

75 i11, cand1, cand2, seen_rects, [], target_type, 

76 collector=results, allowed=allowed, 

77 ) 

78 return results 

79 

80 # ------------------------------------------------------------------ 

81 # Avoidable Rectangles 

82 # ------------------------------------------------------------------ 

83 

84 def _find_ar( 

85 self, 

86 target_type: SolutionType, 

87 only_one: bool = True, 

88 results: list[SolutionStep] | None = None, 

89 ) -> SolutionStep | None: 

90 """Find Avoidable Rectangle steps. 

91 

92 An AR is a UR where some cells are already solved (but NOT givens). 

93 Starting cells must be solved non-given cells. 

94 """ 

95 grid = self.grid 

96 seen_rects: set[tuple[int, int, int, int]] = set() 

97 

98 for i11 in range(81): 

99 # Must be solved and not a given 

100 if grid.values[i11] == 0 or grid.is_fixed(i11): 

101 continue 

102 cand1 = grid.values[i11] 

103 

104 step = self._find_ar_for_start( 

105 i11, cand1, seen_rects, target_type, only_one, results, 

106 ) 

107 if only_one and step is not None: 

108 return step 

109 return None 

110 

111 def _find_ar_for_start( 

112 self, 

113 i11: int, 

114 cand1: int, 

115 seen_rects: set[tuple[int, int, int, int]], 

116 target_type: SolutionType, 

117 only_one: bool, 

118 results: list[SolutionStep] | None, 

119 ) -> SolutionStep | None: 

120 grid = self.grid 

121 r11, c11, b11 = CONSTRAINTS[i11] 

122 

123 # Find second cell in same block, same row or col, also solved non-given 

124 for i12 in BLOCKS[b11]: 

125 if i12 == i11: 

126 continue 

127 r12, c12, _ = CONSTRAINTS[i12] 

128 if r12 != r11 and c12 != c11: 

129 continue 

130 if grid.values[i12] == 0 or grid.is_fixed(i12): 

131 continue 

132 cand2 = grid.values[i12] 

133 

134 is_lines = (r11 == r12) 

135 unit11 = COLS[c11] if is_lines else LINES[r11] 

136 unit12 = COLS[c12] if is_lines else LINES[r12] 

137 

138 for idx in range(9): 

139 i21 = unit11[idx] 

140 i22 = unit12[idx] 

141 if CONSTRAINTS[i21][2] == b11: 

142 continue # must be different block 

143 

144 # Three valid configurations for the far side: 

145 v21 = grid.values[i21] 

146 v22 = grid.values[i22] 

147 nc21 = grid.candidates[i21].bit_count() 

148 nc22 = grid.candidates[i22].bit_count() 

149 

150 valid = False 

151 # Case 1: i21 solved=cand2 (not given), i22 unsolved bivalue with cand1 

152 if (v21 == cand2 and not grid.is_fixed(i21) and 

153 v22 == 0 and grid.candidates[i22] >> (cand1 - 1) & 1 and nc22 == 2): 

154 valid = True 

155 # Case 2: i22 solved=cand1 (not given), i21 unsolved bivalue with cand2 

156 elif (v22 == cand1 and not grid.is_fixed(i22) and 

157 v21 == 0 and grid.candidates[i21] >> (cand2 - 1) & 1 and nc21 == 2): 

158 valid = True 

159 # Case 3: both unsolved bivalue, i21 has cand2, i22 has cand1 

160 elif (v21 == 0 and grid.candidates[i21] >> (cand2 - 1) & 1 and nc21 == 2 and 

161 v22 == 0 and grid.candidates[i22] >> (cand1 - 1) & 1 and nc22 == 2): 

162 valid = True 

163 

164 if not valid: 

165 continue 

166 

167 key = tuple(sorted((i11, i12, i21, i22))) 

168 if key in seen_rects: 

169 continue 

170 seen_rects.add(key) 

171 

172 step = self._check_ar( 

173 i11, i12, i21, i22, cand1, cand2, 

174 target_type, only_one, results, 

175 ) 

176 if only_one and step is not None: 

177 return step 

178 return None 

179 

180 def _check_ar( 

181 self, 

182 i11: int, i12: int, i21: int, i22: int, 

183 cand1: int, cand2: int, 

184 target_type: SolutionType, 

185 only_one: bool, 

186 results: list[SolutionStep] | None, 

187 ) -> SolutionStep | None: 

188 grid = self.grid 

189 

190 def _emit(step: SolutionStep) -> SolutionStep | None: 

191 if not step.candidates_to_delete: 

192 return None 

193 if results is not None: 

194 if step.type == target_type: 

195 results.append(step) 

196 return None 

197 if step.type == target_type: 

198 return step 

199 return None 

200 

201 if grid.values[i21] != 0 or grid.values[i22] != 0: 

202 # AR Type 1: one far cell solved, eliminate UR candidate from the other 

203 step = SolutionStep(SolutionType.AVOIDABLE_RECTANGLE_1) 

204 step.add_value(cand1) 

205 step.add_value(cand2) 

206 step.add_index(i11) 

207 step.add_index(i12) 

208 step.add_index(i21) 

209 step.add_index(i22) 

210 if grid.values[i21] != 0: 

211 # i21 solved (cand2), eliminate cand1 from i22 

212 if grid.candidates[i22] >> (cand1 - 1) & 1: 

213 step.add_candidate_to_delete(i22, cand1) 

214 else: 

215 # i22 solved (cand1), eliminate cand2 from i21 

216 if grid.candidates[i21] >> (cand2 - 1) & 1: 

217 step.add_candidate_to_delete(i21, cand2) 

218 return _emit(step) 

219 else: 

220 # AR Type 2: both far cells unsolved bivalue 

221 # Find the shared additional candidate 

222 cands21 = [d for d in range(1, 10) if grid.candidates[i21] >> (d - 1) & 1] 

223 additional = cands21[0] if cands21[0] != cand2 else cands21[1] 

224 if not (grid.candidates[i22] >> (additional - 1) & 1): 

225 return None 

226 

227 # Eliminate additional from all cells seeing both i21 and i22 

228 peers = BUDDIES[i21] & BUDDIES[i22] & grid.candidate_sets[additional] 

229 if not peers: 

230 return None 

231 

232 step = SolutionStep(SolutionType.AVOIDABLE_RECTANGLE_2) 

233 step.add_value(cand1) 

234 step.add_value(cand2) 

235 step.add_index(i11) 

236 step.add_index(i12) 

237 step.add_index(i21) 

238 step.add_index(i22) 

239 while peers: 

240 lsb = peers & -peers 

241 cell = lsb.bit_length() - 1 

242 step.add_candidate_to_delete(cell, additional) 

243 peers ^= lsb 

244 return _emit(step) 

245 

246 # ------------------------------------------------------------------ 

247 # Helpers 

248 # ------------------------------------------------------------------ 

249 

250 def _compute_allowed(self) -> list[int]: 

251 """Return per-digit bitmasks of empty cells not blocked by any solved cell. 

252 

253 allowed[d] = cells where digit d could theoretically be placed based 

254 solely on the solved-cell constraints (ignoring manual candidate 

255 deletions). This corresponds to Java's ``candidatesAllowed`` array, 

256 used when ``allowUniquenessMissingCandidates = true``. 

257 """ 

258 grid = self.grid 

259 # Start with all cells for each digit, then mask off solved-cell buddies 

260 allowed: list[int] = [0] * 10 

261 full = (1 << 81) - 1 

262 for d in range(1, 10): 

263 a = full 

264 for i in range(81): 

265 if grid.values[i] == d: 

266 a &= ~BUDDIES[i] 

267 a &= ~(1 << i) 

268 # Intersect with empty cells 

269 for i in range(81): 

270 if grid.values[i] != 0: 

271 a &= ~(1 << i) 

272 allowed[d] = a 

273 return allowed 

274 

275 # ------------------------------------------------------------------ 

276 # BUG+1 

277 # ------------------------------------------------------------------ 

278 

279 def _find_bug_plus_1(self) -> SolutionStep | None: 

280 """Bivalue Universal Grave + 1. 

281 

282 Exactly one unsolved cell has 3 candidates; all other unsolved cells 

283 have exactly 2. Every unit has at most 2 occurrences of each candidate 

284 except one (cand3) which appears exactly 3 times in one row, one col, 

285 and one box — and that cell is the trivalue cell. 

286 """ 

287 grid = self.grid 

288 index3 = -1 

289 for i in range(81): 

290 if grid.values[i] != 0: 

291 continue 

292 n = bin(grid.candidates[i]).count("1") 

293 if n > 3: 

294 return None 

295 if n == 3: 

296 if index3 != -1: 

297 return None # two trivalue cells → not BUG+1 

298 index3 = i 

299 if index3 == -1: 

300 return None 

301 

302 cand3 = -1 

303 bug_row = bug_col = bug_box = -1 

304 for unit in range(27): 

305 for d in range(1, 10): 

306 cnt = grid.free[unit][d] 

307 if cnt > 3: 

308 return None 

309 if cnt == 3: 

310 unit_type = unit // 9 # 0=row, 1=col, 2=box 

311 if unit_type == 0: 

312 if bug_row != -1 or (cand3 != -1 and cand3 != d): 

313 return None 

314 cand3 = d 

315 bug_row = unit 

316 elif unit_type == 1: 

317 if bug_col != -1 or (cand3 != -1 and cand3 != d): 

318 return None 

319 cand3 = d 

320 bug_col = unit 

321 else: 

322 if bug_box != -1 or (cand3 != -1 and cand3 != d): 

323 return None 

324 cand3 = d 

325 bug_box = unit 

326 

327 if cand3 == -1: 

328 return None 

329 r3, c3, b3 = CONSTRAINTS[index3] 

330 if r3 != bug_row or (9 + c3) != bug_col or (18 + b3) != bug_box: 

331 return None 

332 if not (grid.candidate_sets[cand3] >> index3 & 1): 

333 return None 

334 

335 step = SolutionStep(SolutionType.BUG_PLUS_1) 

336 mask = grid.candidates[index3] 

337 for d in range(1, 10): 

338 if mask >> (d - 1) & 1 and d != cand3: 

339 step.add_candidate_to_delete(index3, d) 

340 return step if step.candidates_to_delete else None 

341 

342 # ------------------------------------------------------------------ 

343 # Unique Rectangle search 

344 # ------------------------------------------------------------------ 

345 

346 def _find_ur(self, target_type: SolutionType) -> SolutionStep | None: 

347 """Find the first UR step of the given type (or any UR type if caching).""" 

348 grid = self.grid 

349 seen_rects: set[tuple[int, int, int, int]] = set() 

350 cached: list[SolutionStep] = [] 

351 allowed = self._compute_allowed() 

352 

353 # Java only starts from bivalue cells (getAnzCandidates(i) == 2) 

354 for i11 in range(81): 

355 if grid.values[i11] != 0: 

356 continue 

357 if bin(grid.candidates[i11]).count("1") != 2: 

358 continue 

359 cands = [d for d in range(1, 10) if grid.candidates[i11] >> (d - 1) & 1] 

360 cand1, cand2 = cands[0], cands[1] 

361 step = self._find_ur_for_pair( 

362 i11, cand1, cand2, seen_rects, cached, target_type, 

363 allowed=allowed, 

364 ) 

365 if step is not None: 

366 return step 

367 

368 # Return cached step of the requested type 

369 for step in cached: 

370 if step.type == target_type: 

371 return step 

372 return None 

373 

374 def _find_ur_for_pair( 

375 self, 

376 i11: int, 

377 cand1: int, 

378 cand2: int, 

379 seen_rects: set[tuple[int, int, int, int]], 

380 cached: list[SolutionStep], 

381 target_type: SolutionType, 

382 collector: list[SolutionStep] | None = None, 

383 allowed: list[int] | None = None, 

384 ) -> SolutionStep | None: 

385 """Search for URs starting at i11 with the given candidate pair. 

386 

387 When *allowed* is provided (list[int] indexed 0..9), cells are accepted 

388 as UR members if the digit is *allowed* there (not blocked by any solved 

389 cell in the same house), even if the candidate has been manually deleted. 

390 This mirrors Java's ``allowUniquenessMissingCandidates = true`` mode, 

391 which is HoDoKu's default. 

392 """ 

393 grid = self.grid 

394 r11, c11, b11 = CONSTRAINTS[i11] 

395 

396 def _has_cands(cell: int) -> bool: 

397 if allowed is not None: 

398 return bool(allowed[cand1] >> cell & 1 and allowed[cand2] >> cell & 1) 

399 return bool(grid.candidates[cell] >> (cand1 - 1) & 1 and 

400 grid.candidates[cell] >> (cand2 - 1) & 1) 

401 

402 # Find second cell in the same block sharing both candidates, 

403 # in the same row OR same col 

404 for i12 in BLOCKS[b11]: 

405 if i12 == i11: 

406 continue 

407 r12, c12, b12 = CONSTRAINTS[i12] 

408 if r12 != r11 and c12 != c11: 

409 continue # not aligned in row or col 

410 if grid.values[i12] != 0: 

411 continue 

412 if not _has_cands(i12): 

413 continue 

414 

415 is_lines = (r11 == r12) 

416 # The opposite side of the rectangle 

417 unit11 = COLS[c11] if is_lines else LINES[r11] 

418 unit12 = COLS[c12] if is_lines else LINES[r12] 

419 

420 for idx in range(9): 

421 i21 = unit11[idx] 

422 i22 = unit12[idx] 

423 if CONSTRAINTS[i21][2] == b11: 

424 continue # must be a different block 

425 if grid.values[i21] != 0 or grid.values[i22] != 0: 

426 continue 

427 if not _has_cands(i21): 

428 continue 

429 if not _has_cands(i22): 

430 continue 

431 

432 # Deduplicate rectangles 

433 key = tuple(sorted((i11, i12, i21, i22))) 

434 if key in seen_rects: 

435 continue 

436 seen_rects.add(key) 

437 

438 step = self._check_ur( 

439 i11, i12, i21, i22, cand1, cand2, cached, target_type, 

440 collector=collector, 

441 ) 

442 if collector is None and step is not None: 

443 return step 

444 return None 

445 

446 def _check_ur( 

447 self, 

448 i11: int, i12: int, i21: int, i22: int, 

449 cand1: int, cand2: int, 

450 cached: list[SolutionStep], 

451 target_type: SolutionType, 

452 collector: list[SolutionStep] | None = None, 

453 ) -> SolutionStep | None: 

454 """Evaluate all UR types for this rectangle.""" 

455 grid = self.grid 

456 indexe = (i11, i12, i21, i22) 

457 ur_mask = (1 << (cand1 - 1)) | (1 << (cand2 - 1)) 

458 

459 # Partition cells: two_cands = cells with only cand1/cand2; additional = rest 

460 two_cands: list[int] = [] 

461 additional: list[int] = [] 

462 for cell in indexe: 

463 extra = grid.candidates[cell] & ~ur_mask & _ALL_DIGITS 

464 if extra == 0: 

465 two_cands.append(cell) 

466 else: 

467 additional.append(cell) 

468 

469 twoSize = len(two_cands) 

470 

471 def emit(step: SolutionStep) -> SolutionStep | None: 

472 if collector is not None: 

473 if step.type == target_type: 

474 collector.append(step) 

475 return None 

476 if step.type == target_type: 

477 return step 

478 cached.append(step) 

479 return None 

480 

481 def make_step(sol_type: SolutionType) -> SolutionStep: 

482 s = SolutionStep(sol_type) 

483 s.add_value(cand1) 

484 s.add_value(cand2) 

485 for c in indexe: 

486 s.add_index(c) 

487 return s 

488 

489 # UT1: 3 cells are pure bivalue → eliminate both from the 4th 

490 if twoSize == 3: 

491 del_cell = additional[0] 

492 s = make_step(SolutionType.UNIQUENESS_1) 

493 for d in (cand1, cand2): 

494 if grid.candidates[del_cell] >> (d - 1) & 1: 

495 s.add_candidate_to_delete(del_cell, d) 

496 if s.candidates_to_delete: 

497 result = emit(s) 

498 if result: 

499 return result 

500 

501 # UT2 / UT5: 1 or 2 additional-candidate cells all share exactly 1 extra candidate 

502 if twoSize in (1, 2): 

503 add_mask = 0 

504 buddies_all = (1 << 81) - 1 

505 for cell in additional: 

506 add_mask |= grid.candidates[cell] & ~ur_mask & _ALL_DIGITS 

507 if bin(add_mask).count("1") > 1: 

508 break 

509 buddies_all &= BUDDIES[cell] 

510 if bin(add_mask).count("1") == 1: 

511 add_cand = add_mask.bit_length() # digit (1-9) 

512 elim = grid.candidate_sets[add_cand] & buddies_all 

513 for cell in additional + two_cands: 

514 elim &= ~(1 << cell) 

515 if elim: 

516 i1, i2 = additional[0], (additional[1] if len(additional) > 1 else two_cands[0]) 

517 r1, c1 = CONSTRAINTS[i1][:2] 

518 r2, c2 = CONSTRAINTS[i2][:2] 

519 same_line_or_col = (r1 == r2 or c1 == c2) 

520 sol_type = ( 

521 SolutionType.UNIQUENESS_2 

522 if (len(additional) <= 2 and same_line_or_col) 

523 else SolutionType.UNIQUENESS_5 

524 ) 

525 s = make_step(sol_type) 

526 tmp = elim 

527 while tmp: 

528 lsb = tmp & -tmp 

529 s.add_candidate_to_delete(lsb.bit_length() - 1, add_cand) 

530 tmp ^= lsb 

531 result = emit(s) 

532 if result: 

533 return result 

534 

535 # UT3: 2 additional-candidate cells; find k-1 more cells in a shared house 

536 # to form a Naked Subset on the additional candidates 

537 if twoSize == 2: 

538 u3_cands = 0 

539 for cell in additional: 

540 u3_cands |= grid.candidates[cell] & ~ur_mask & _ALL_DIGITS 

541 i1, i2 = additional 

542 r1, c1, b1 = CONSTRAINTS[i1] 

543 r2, c2, b2 = CONSTRAINTS[i2] 

544 ur_all = set(indexe) 

545 for unit_cells, unit_type in [ 

546 (LINES[r1] if r1 == r2 else None, 0), 

547 (COLS[c1] if c1 == c2 else None, 1), 

548 (BLOCKS[b1] if b1 == b2 else None, 2), 

549 ]: 

550 if unit_cells is None: 

551 continue 

552 # Candidates to add: cells in unit not in UR and not holding cand1/cand2 

553 u3_pool = [ 

554 c for c in unit_cells 

555 if c not in ur_all 

556 and grid.values[c] == 0 

557 and not (grid.candidates[c] >> (cand1 - 1) & 1) 

558 and not (grid.candidates[c] >> (cand2 - 1) & 1) 

559 and grid.candidates[c] & _ALL_DIGITS 

560 ] 

561 step = self._check_ut3_recursive( 

562 unit_type, unit_cells, u3_pool, u3_cands, list(additional), 

563 ur_mask, ur_all, 0, indexe, cand1, cand2, cached, target_type, 

564 collector=collector, 

565 ) 

566 if collector is None and step: 

567 return step 

568 

569 # UT4: 2 additional-candidate cells in same row/col; one UR candidate is absent 

570 # from all cells seen by both → eliminate the other from the 2 extra cells 

571 if twoSize == 2: 

572 i1, i2 = additional 

573 r1, c1 = CONSTRAINTS[i1][:2] 

574 r2, c2 = CONSTRAINTS[i2][:2] 

575 if r1 == r2 or c1 == c2: 

576 shared_buddies = BUDDIES[i1] & BUDDIES[i2] 

577 del_cand = -1 

578 if not (grid.candidate_sets[cand1] & shared_buddies): 

579 del_cand = cand2 

580 elif not (grid.candidate_sets[cand2] & shared_buddies): 

581 del_cand = cand1 

582 if del_cand != -1: 

583 s = make_step(SolutionType.UNIQUENESS_4) 

584 for cell in additional: 

585 if grid.candidates[cell] >> (del_cand - 1) & 1: 

586 s.add_candidate_to_delete(cell, del_cand) 

587 if s.candidates_to_delete: 

588 result = emit(s) 

589 if result: 

590 return result 

591 

592 # UT6: 2 diagonal additional-candidate cells; one UR candidate appears ONLY 

593 # in the UR cells in both its rows and cols → delete that candidate from the 2 extra cells 

594 if twoSize == 2: 

595 i1, i2 = additional 

596 r1, c1 = CONSTRAINTS[i1][:2] 

597 r2, c2 = CONSTRAINTS[i2][:2] 

598 if r1 != r2 and c1 != c2: 

599 # union of lines and cols through the extra cells, minus the UR itself 

600 lines_cols_mask = 0 

601 for row in (r1, r2): 

602 for cell in LINES[row]: 

603 lines_cols_mask |= 1 << cell 

604 for col in (c1, c2): 

605 for cell in COLS[col]: 

606 lines_cols_mask |= 1 << cell 

607 for cell in indexe: 

608 lines_cols_mask &= ~(1 << cell) 

609 del_cand = -1 

610 if not (grid.candidate_sets[cand1] & lines_cols_mask): 

611 del_cand = cand1 

612 elif not (grid.candidate_sets[cand2] & lines_cols_mask): 

613 del_cand = cand2 

614 if del_cand != -1: 

615 s = make_step(SolutionType.UNIQUENESS_6) 

616 for cell in sorted(additional): 

617 if grid.candidates[cell] >> (del_cand - 1) & 1: 

618 s.add_candidate_to_delete(cell, del_cand) 

619 if s.candidates_to_delete: 

620 result = emit(s) 

621 if result: 

622 return result 

623 

624 # Hidden Rectangle: 1 or 2 bivalue cells (diagonally placed if 2); 

625 # the row AND col through the non-bivalue side have no other occurrences 

626 # of one UR candidate → eliminate the other from the intersection cell 

627 if twoSize in (1, 2): 

628 if twoSize == 2: 

629 i1t, i2t = two_cands 

630 r1t, c1t = CONSTRAINTS[i1t][:2] 

631 r2t, c2t = CONSTRAINTS[i2t][:2] 

632 if r1t == r2t or c1t == c2t: 

633 pass # must be diagonal 

634 else: 

635 for corner in two_cands: 

636 step = self._check_hidden_rect( 

637 corner, additional, two_cands, cand1, cand2, 

638 indexe, cached, target_type, collector=collector, 

639 ) 

640 if collector is None and step: 

641 return step 

642 else: 

643 corner = two_cands[0] 

644 step = self._check_hidden_rect( 

645 corner, additional, two_cands, cand1, cand2, 

646 indexe, cached, target_type, collector=collector, 

647 ) 

648 if collector is None and step: 

649 return step 

650 

651 return None 

652 

653 def _check_ut3_recursive( 

654 self, 

655 unit_type: int, 

656 unit_cells: tuple[int, ...], 

657 pool: list[int], 

658 cands_included: int, 

659 indices_included: list[int], 

660 ur_mask: int, 

661 ur_all: set[int], 

662 start: int, 

663 indexe: tuple[int, int, int, int], 

664 cand1: int, cand2: int, 

665 cached: list[SolutionStep], 

666 target_type: SolutionType, 

667 collector: list[SolutionStep] | None = None, 

668 ) -> SolutionStep | None: 

669 grid = self.grid 

670 for i in range(start, len(pool)): 

671 new_cands = cands_included | (grid.candidates[pool[i]] & _ALL_DIGITS) 

672 new_indices = indices_included + [pool[i]] 

673 

674 # For blocks: skip if all in same row/col (already checked by line/col pass) 

675 if unit_type == 2 and _same_line_or_col(new_indices): 

676 pass 

677 else: 

678 n_cands = bin(new_cands).count("1") 

679 n_cells = len(new_indices) 

680 if n_cands == n_cells - 1: 

681 # Naked Subset found — find eliminations in the unit 

682 s = SolutionStep(SolutionType.UNIQUENESS_3) 

683 s.add_value(cand1) 

684 s.add_value(cand2) 

685 for c in indexe: 

686 s.add_index(c) 

687 new_idx_set = set(new_indices) 

688 for cell in unit_cells: 

689 if grid.values[cell] != 0 or cell in new_idx_set: 

690 continue 

691 del_mask = grid.candidates[cell] & new_cands 

692 for d in range(1, 10): 

693 if del_mask >> (d - 1) & 1: 

694 s.add_candidate_to_delete(cell, d) 

695 # Also eliminate from shared block if applicable 

696 if unit_type in (0, 1): 

697 block = _same_block(new_indices) 

698 if block != -1: 

699 for cell in BLOCKS[block]: 

700 if grid.values[cell] != 0 or cell in new_idx_set: 

701 continue 

702 del_mask = grid.candidates[cell] & new_cands 

703 for d in range(1, 10): 

704 if del_mask >> (d - 1) & 1: 

705 s.add_candidate_to_delete(cell, d) 

706 # Add fins (the subset cells and their shared candidates) 

707 for d in range(1, 10): 

708 if new_cands >> (d - 1) & 1: 

709 for cell in new_indices: 

710 if grid.candidates[cell] >> (d - 1) & 1: 

711 s.fins.append(Candidate(cell, d)) 

712 if s.candidates_to_delete: 

713 if collector is not None: 

714 if s.type == target_type: 

715 collector.append(s) 

716 else: 

717 if s.type == target_type: 

718 return s 

719 cached.append(s) 

720 

721 step = self._check_ut3_recursive( 

722 unit_type, unit_cells, pool, new_cands, new_indices, 

723 ur_mask, ur_all, i + 1, indexe, cand1, cand2, cached, target_type, 

724 collector=collector, 

725 ) 

726 if collector is None and step: 

727 return step 

728 return None 

729 

730 def _check_hidden_rect( 

731 self, 

732 corner: int, 

733 additional: list[int], 

734 two_cands: list[int], 

735 cand1: int, cand2: int, 

736 indexe: tuple[int, int, int, int],