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 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431
| import numpy as np import time from itertools import combinations import multiprocessing as mp
USE_GPU = False
try: import cupy as cp from numba import cuda, jit test_array = cp.zeros(10) test_array[0] = 1 if test_array[0] == 1: USE_GPU = True print("GPU加速可用") except Exception as e: print(f"GPU加速不可用: {e}") print("将使用CPU多线程模式")
class SudokuSolver: def __init__(self, num_strings): self.grid = np.zeros((9, 9), dtype=np.int32) self.num_strings = num_strings self.solutions = [] self.row_masks = np.zeros(9, dtype=np.int32) self.col_masks = np.zeros(9, dtype=np.int32) self.box_masks = np.zeros(9, dtype=np.int32) self.max_sol = 0 self.tried_placements = 0 self.start_time = time.time() def solve(self): """主入口函数""" self._init_masks() return self._backtrack(0) def dump(self): """打印当前网格状态""" print(f"网格状态 ({len(self.num_strings)}个数串)") for row in self.grid: print(row) def _backtrack(self, str_index): """统一回溯框架:处理数串放置和数独填充""" if str_index == len(self.num_strings): if self._solve_remaining(): self.solutions.append(self.grid.copy()) return True return False if str_index > self.max_sol: self.max_sol = str_index elapsed = time.time() - self.start_time print(f'IDX{str_index}: {self.num_strings[str_index]} [尝试: {self.tried_placements}, 用时: {elapsed:.2f}秒]') current_str = self.num_strings[str_index] current_str_len = len(current_str) all_coors = self._generate_all_possible_coors(current_str_len) for coors in all_coors: self.tried_placements += 1 coors_s = list(zip(coors, [int(x) for x in current_str])) if self._can_place_str(coors_s): self._place_str(coors_s) if self._backtrack(str_index + 1): return True self._remove_str(coors_s) return False def _generate_all_possible_coors(self, str_len): """生成所有可能的坐标方案""" result = [] directions = [(0,1), (0,-1), (1,0), (-1,0), (1,1), (-1,-1), (1,-1), (-1,1)] for r in range(9): for c in range(9): for dr, dc in directions: coors = [] valid = True for i in range(str_len): new_r, new_c = r + i*dr, c + i*dc if new_r < 0 or new_r >= 9 or new_c < 0 or new_c >= 9: valid = False break coors.append((new_r, new_c)) if valid: result.append(coors) return result def _solve_remaining(self): """填充剩余空格""" empty = self._find_empty() if not empty: return True row, col = empty for num in self._get_possible_numbers(row, col): if self._is_valid(row, col, num): self._set_number(row, col, num) if self._solve_remaining(): return True self._clear_number(row, col) return False def _can_place_str(self, coors): """检查是否可以放置数串""" for cr, val in list(coors): r, c = cr if r >= 9 or c >= 9: return False gval = self.grid[r][c] if gval != 0: if gval != val: return False coors.remove((cr, val))
tmp_row_mask = self.row_masks.copy() tmp_col_mask = self.col_masks.copy() tmp_box_mask = self.box_masks.copy()
for cr, val in coors: if not self._try_mask(tmp_row_mask, tmp_col_mask, tmp_box_mask, cr, val): return False return True def _try_mask(self, rm, cm, bm, coor, val): """尝试更新掩码""" mask = 1 << (val - 1) r, c = coor if (rm[r] & mask != 0 or cm[c] & mask != 0 or bm[(r//3)*3 + (c//3)] & mask != 0): return False rm[r] |= mask cm[c] |= mask bm[(r//3)*3 + (c//3)] |= mask return True def _place_str(self, coors): """放置数串""" for cr, val in coors: r, c = cr self._set_number(r, c, val) def _remove_str(self, coors): """移除数串""" for cr, _ in coors: r, c = cr self._clear_number(r, c)
def _init_masks(self): """初始化位掩码""" for r in range(9): for c in range(9): num = self.grid[r][c] if num != 0: self._update_masks(r, c, num, set_mask=True) def _update_masks(self, row, col, num, set_mask): """更新掩码""" mask = 1 << (num - 1) if set_mask: self.row_masks[row] |= mask self.col_masks[col] |= mask self.box_masks[(row//3)*3 + (col//3)] |= mask else: self.row_masks[row] &= ~mask self.col_masks[col] &= ~mask self.box_masks[(row//3)*3 + (col//3)] &= ~mask def _find_empty(self): """寻找空位置""" for r in range(9): for c in range(9): if self.grid[r][c] == 0: return (r, c) return None def _get_possible_numbers(self, row, col): """获取可能的数字""" used = self.row_masks[row] | self.col_masks[col] | self.box_masks[(row//3)*3 + (col//3)] return [i for i in range(1, 10) if not (used & (1 << (i-1)))] def _is_valid(self, row, col, num): """验证数字是否有效""" mask = 1 << (num - 1) return not (self.row_masks[row] & mask or self.col_masks[col] & mask or self.box_masks[(row//3)*3 + (col//3)] & mask) def _set_number(self, row, col, num): """设置数字""" self.grid[row][col] = num self._update_masks(row, col, num, set_mask=True) def _clear_number(self, row, col): """清除数字""" num = self.grid[row][col] if num != 0: self._update_masks(row, col, num, set_mask=False) self.grid[row][col] = 0
if USE_GPU: class SudokuSolverGPU(SudokuSolver): def __init__(self, num_strings): super().__init__(num_strings) def _generate_all_possible_coors(self, str_len): """GPU加速版坐标生成""" return self._generate_all_possible_coors_gpu_simple(str_len) def _generate_all_possible_coors_gpu_simple(self, str_len): """简化的GPU坐标生成,完全避免在CUDA内核中使用复杂数据结构""" all_results = [] directions = [(0,1), (0,-1), (1,0), (-1,0), (1,1), (-1,-1), (1,-1), (-1,1)] for dr, dc in directions: d_valid = cp.zeros((9, 9), dtype='bool') h_valid = np.zeros((9, 9), dtype=bool) for r in range(9): for c in range(9): valid = True for i in range(str_len): new_r, new_c = r + i*dr, c + i*dc if new_r < 0 or new_r >= 9 or new_c < 0 or new_c >= 9: valid = False break h_valid[r, c] = valid d_valid = cp.array(h_valid) valid_positions = cp.where(d_valid == True) for r, c in zip(valid_positions[0].get(), valid_positions[1].get()): coors = [] for i in range(str_len): coors.append((r + i*dr, c + i*dc)) all_results.append(coors) return all_results
def c2n(ch): """字符到数字的映射""" map_c = ['a', 'e', 'u', 'i', 'r', 'p', 'l', 's', 't'] return map_c.index(ch) + 1
def word2ns(chs): """将单词转换为数字串""" map_c = ['a', 'e', 'u', 'i', 'r', 'p', 'l', 's', 't'] data = [] for i in chs: for j in range(len(map_c)): if i == map_c[j]: data.append(str(j + 1)) break return ''.join(data)
def solve_sudoku_with_words(words): """用单词列表求解数独""" print("正在转换单词为数字串...") num_strings = [word2ns(i) for i in words] print(f"数字串: {num_strings}") print("开始求解数独...") start_time = time.time() if USE_GPU: solver = SudokuSolverGPU(num_strings) else: solver = SudokuSolver(num_strings) if solver.solve(): end_time = time.time() print(f"求解成功!耗时 {end_time - start_time:.2f} 秒") print("完整数独解:") for row in solver.solutions[0]: print(row) return solver.solutions[0] else: end_time = time.time() print(f"无可行解。耗时 {end_time - start_time:.2f} 秒") return None
def decode(s): """解码数独解为字符""" map_c = ['a', 'e', 'u', 'i', 'r', 'p', 'l', 's', 't'] payload = '' for i in s: for j in i: if j > 0: payload += map_c[j-1] return payload
def strstr(words: list): """移除被其他单词包含的单词""" i = 0 while i < len(words): word = words[i] contained = False for j in range(len(words)): if i != j and word in words[j]: contained = True break if contained: words.pop(i) else: i += 1
def process_combination(elements, idx, total): """处理单个组合""" print(f"\n正在尝试第 {idx+1}/{total} 种组合...") words = set() for ent in elements: for word in ent.split(): words.add(word) words = list(words) words.sort(key=len) strstr(words) words = words[::-1] print(f"处理后的单词列表: {words}") result = solve_sudoku_with_words(words) if result is not None: solution_text = decode(result) print(f"找到解决方案: {solution_text}") return solution_text else: print("此组合无解") return None
def process_batch(batch, start_idx, total): """处理一批组合""" results = [] for i, elements in enumerate(batch): idx = start_idx + i result = process_combination(elements, idx, total) if result: results.append((idx, result)) return results
if __name__ == "__main__": calist = [ 'past is pleasure', 'please user it', 'rap less piter', 'its pure latter', 'is leet', 'rit platstep', 'all use peatrle', 'pali atar usar', 'sets a pure sereat', 'tales sell appets', ] print("生成所有可能的单词组合...") all_combinations = list(combinations(calist, 5)) all_combinations.reverse() total = len(all_combinations) print(f"总共有 {total} 种组合需要尝试") use_multiprocessing = not USE_GPU and mp.cpu_count() > 1 if use_multiprocessing: print(f"使用多进程并行尝试 (CPU核心数: {mp.cpu_count()})") cpu_count = mp.cpu_count() batch_size = (total + cpu_count - 1) // cpu_count batches = [all_combinations[i:i+batch_size] for i in range(0, total, batch_size)] with mp.Pool(processes=cpu_count) as pool: batch_args = [(batch, i*batch_size, total) for i, batch in enumerate(batches)] all_results = pool.starmap(process_batch, batch_args) solutions = [] for batch_results in all_results: solutions.extend(batch_results) if solutions: for idx, solution in solutions: print(f"组合 {idx+1} 的解决方案: {solution}") else: print("所有组合均无解") else: for idx, elements in enumerate(all_combinations): result = process_combination(elements, idx, total) if result: print(f"组合 {idx+1} 的解决方案: {result}") break
|