rustoku_lib/core/techniques/
x_wing.rs

1use crate::core::SolvePath;
2
3use super::{TechniquePropagator, TechniqueRule};
4
5/// X-Wing technique implementation.
6pub struct XWing;
7
8impl TechniqueRule for XWing {
9    fn apply(&self, prop: &mut TechniquePropagator, path: &mut SolvePath) -> bool {
10        let mut eliminations_made = false;
11
12        for candidate_val in 1..=9 {
13            let candidate_bit = 1 << (candidate_val - 1);
14
15            // Check for row-based X-Wings
16            let mut rows_with_two_candidates: Vec<usize> = Vec::new();
17            let mut candidate_cols_in_rows: Vec<Vec<usize>> = Vec::new();
18
19            for r in 0..9 {
20                let mut cols_for_candidate_in_row: Vec<usize> = Vec::new();
21                for c in 0..9 {
22                    if prop.board.is_empty(r, c) && (prop.candidates.get(r, c) & candidate_bit) != 0
23                    {
24                        cols_for_candidate_in_row.push(c);
25                    }
26                }
27                if cols_for_candidate_in_row.len() == 2 {
28                    rows_with_two_candidates.push(r);
29                    candidate_cols_in_rows.push(cols_for_candidate_in_row);
30                }
31            }
32
33            for i in 0..rows_with_two_candidates.len() {
34                for j in (i + 1)..rows_with_two_candidates.len() {
35                    let r1 = rows_with_two_candidates[i];
36                    let r2 = rows_with_two_candidates[j];
37                    let cols1 = &candidate_cols_in_rows[i];
38                    let cols2 = &candidate_cols_in_rows[j];
39
40                    if cols1[0] == cols2[0] && cols1[1] == cols2[1] {
41                        let c1 = cols1[0];
42                        let c2 = cols1[1];
43
44                        // Found an X-Wing in columns c1 and c2 across rows r1 and r2
45                        // Remove candidate from other cells in column c1 (excluding r1, r2)
46                        for r_other in 0..9 {
47                            if r_other != r1 && r_other != r2 && prop.board.is_empty(r_other, c1) {
48                                let initial_mask = prop.candidates.get(r_other, c1);
49                                if (initial_mask & candidate_bit) != 0 {
50                                    eliminations_made |= prop.eliminate_candidate(
51                                        r_other,
52                                        c1,
53                                        candidate_bit,
54                                        self.flags(),
55                                        path,
56                                    );
57                                }
58                            }
59                        }
60
61                        // Remove candidate from other cells in column c2 (excluding r1, r2)
62                        for r_other in 0..9 {
63                            if r_other != r1 && r_other != r2 && prop.board.is_empty(r_other, c2) {
64                                let initial_mask = prop.candidates.get(r_other, c2);
65                                if (initial_mask & candidate_bit) != 0 {
66                                    eliminations_made |= prop.eliminate_candidate(
67                                        r_other,
68                                        c2,
69                                        candidate_bit,
70                                        self.flags(),
71                                        path,
72                                    );
73                                }
74                            }
75                        }
76                    }
77                }
78            }
79
80            // Check for column-based X-Wings (symmetric to row-based)
81            let mut cols_with_two_candidates: Vec<usize> = Vec::new();
82            let mut candidate_rows_in_cols: Vec<Vec<usize>> = Vec::new();
83
84            for c in 0..9 {
85                let mut rows_for_candidate_in_col: Vec<usize> = Vec::new();
86                for r in 0..9 {
87                    if prop.board.is_empty(r, c) && (prop.candidates.get(r, c) & candidate_bit) != 0
88                    {
89                        rows_for_candidate_in_col.push(r);
90                    }
91                }
92                if rows_for_candidate_in_col.len() == 2 {
93                    cols_with_two_candidates.push(c);
94                    candidate_rows_in_cols.push(rows_for_candidate_in_col);
95                }
96            }
97
98            for i in 0..cols_with_two_candidates.len() {
99                for j in (i + 1)..cols_with_two_candidates.len() {
100                    let c1 = cols_with_two_candidates[i];
101                    let c2 = cols_with_two_candidates[j];
102                    let rows1 = &candidate_rows_in_cols[i];
103                    let rows2 = &candidate_rows_in_cols[j];
104
105                    if rows1[0] == rows2[0] && rows1[1] == rows2[1] {
106                        let r1 = rows1[0];
107                        let r2 = rows1[1];
108
109                        // Found an X-Wing in rows r1 and r2 across columns c1 and c2
110                        // Remove candidate from other cells in row r1 (excluding c1, c2)
111                        for c_other in 0..9 {
112                            if c_other != c1 && c_other != c2 && prop.board.is_empty(r1, c_other) {
113                                let initial_mask = prop.candidates.get(r1, c_other);
114                                if (initial_mask & candidate_bit) != 0 {
115                                    eliminations_made |= prop.eliminate_candidate(
116                                        r1,
117                                        c_other,
118                                        candidate_bit,
119                                        self.flags(),
120                                        path,
121                                    );
122                                }
123                            }
124                        }
125
126                        // Remove candidate from other cells in row r2 (excluding c1, c2)
127                        for c_other in 0..9 {
128                            if c_other != c1 && c_other != c2 && prop.board.is_empty(r2, c_other) {
129                                let initial_mask = prop.candidates.get(r2, c_other);
130                                if (initial_mask & candidate_bit) != 0 {
131                                    eliminations_made |= prop.eliminate_candidate(
132                                        r2,
133                                        c_other,
134                                        candidate_bit,
135                                        self.flags(),
136                                        path,
137                                    );
138                                }
139                            }
140                        }
141                    }
142                }
143            }
144        }
145        eliminations_made
146    }
147
148    fn flags(&self) -> crate::core::TechniqueFlags {
149        crate::core::TechniqueFlags::XWING
150    }
151}
rustoku_lib/core/techniques/x_wing.rs

rustoku_lib/core/techniques/
x_wing.rs
