[{"_1":2,"_168":-5,"_169":-5},"loaderData",{"_3":4,"_91":92},"root",{"_5":6,"_34":35,"_64":65},"ctx",{"_7":8,"_23":-5,"_24":25,"_26":27,"_28":20,"_29":20,"_30":20,"_31":32,"_33":20},"auth",{"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20,"_21":22},"sessionClaims","sessionId","sessionStatus","userId","actor","orgId","orgRole","orgSlug","orgPermissions","factorVerificationAge","isAuthenticated",false,"tokenType","session_token","user","preferencesKeybindings","default","preferencesTheme","light","preferencesFixers","preferencesCopilot","preferencesSelectionAi","notificationCount",0,"flagDenols","ENV",{"_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},"REACT_APP_SENTRY_DSN","https://586020d86f05489db63a554690acf1e9@o1398359.ingest.sentry.io/6724499","VAL_RUNTIME_NAME","prod","RENDER_GIT_COMMIT","230fbbe1911b69d46be82b6db4e617b331d282a6","RENDER_GIT_BRANCH","main","CLERK_PUBLISHABLE_KEY","pk_live_Y2xlcmsudmFsLnRvd24k","POSTHOG_API_TOKEN","phc_nmoyuAkStEZuUp69rYlg1DZgrIt19Gx0Y4Hwf8tGgJP","POSTHOG_API_HOST","https://wart.val.town","WEB_API_TEMPLATE","https://{val}.web.val.run","APP_URL","https://www.val.town","MODULE_URL","https://esm.town","VANITY_WEB_API_TEMPLATE","https://{label}.val.run/","DENOLS_URL","https://lsp.val.town","NODE_ENV","production","API_URL","https://api.val.town","clerkState",{"_66":67},"__internal_clerk_state",{"_68":69,"_70":45,"_71":72,"_73":72,"_74":20,"_75":72,"_76":72,"_77":72,"_78":72,"_79":80,"_89":20,"_90":20},"__clerk_ssr_state",{"_21":22,"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20},"__publishableKey","__proxyUrl","","__domain","__isSatellite","__signInUrl","__signUpUrl","__afterSignInUrl","__afterSignUpUrl","__clerk_debug",{"_81":20,"_19":20,"_82":72,"_83":84,"_85":72,"_86":45,"_87":20,"_88":72},"isSignedIn","proxyUrl","reason","session-token-and-uat-missing","message","publishableKey","isSatellite","domain","__telemetryDisabled","__telemetryDebug","routes/embed.x.$handle.$name.$",{"_93":94,"_95":96,"_97":98,"_99":100,"_147":148,"_165":166,"_167":-5},"handle","saolsen","name","sudoku_solver_human_search","path","main.tsx","project",{"_101":102,"_95":96,"_103":104,"_105":-5,"_106":107,"_108":109,"_110":-5,"_111":-5,"_12":112,"_113":-5,"_114":107,"_115":-5,"_116":32,"_14":117,"_118":119,"_120":119,"_121":122,"_123":122,"_124":122,"_125":119,"_126":119,"_23":127,"_130":131,"_133":134,"_146":20},"id","afdccf60-27ac-11f0-9edc-569c3dd06744","createdAt",["D",1746228308680],"deletedAt","legacyEnvVars",true,"privacy","public","description","imageUrl","e1269f9c-67ab-446c-9c3f-debdc882a7b8","pinnedFileId","pinPreview","screenshotVersion","likeCount","6af58753-71c6-4397-9d5b-2473eb888976","userPerm","r","valPerm","blobPerm","rw","emailPerm","sqlitePerm","projectPerm","telemetryPerm",{"_93":94,"_128":129},"profileImageUrl","https://images.clerk.dev/oauth_github/img_2QtXHzN3gDPhKsBOvKsst8LTxC5.png","org",{"_93":94,"_132":129},"avatar","branch",{"_135":136,"_95":43,"_101":137,"_138":102,"_139":-5,"_140":-5,"_141":-5,"_142":-5,"_143":-5,"_144":96,"_145":94},"version",3,"afdd1128-27ac-11f0-9edc-569c3dd06744","projectId","forkedBranchId","forkedBranchVersion","forkedProjectPrivacy","forkedProjectId","forkedProjectOrgId","projectName","userHandle","isOwned","file",{"_101":149,"_95":98,"_150":151,"_152":-5,"_153":137,"_154":136,"_155":107,"_103":156,"_135":157,"_158":159,"_160":161,"_162":20,"_163":-5,"_97":164},"afeac14c-27ac-11f0-9edc-569c3dd06744","fileId","afdf3854-27ac-11f0-9edc-569c3dd06744","parentId","branchId","branchVersion","latest",["D",1710021899764],2,"fileType","script","content","// This is another brute force with backtracking approach.\n// Instead of going cell by cell, it does what a human would do and\n// tries to pick a cell with the least number of possible values to fill in.\n// If there is only one possibility it picks it, if there is more than one it picks\n// the minimum value. Then when it gets into a state where it can't progress, it undoes\n// picks until it gets to one that had more than one possibility and picks the next one\n// then continues.\nimport { Sudoku } from \"https://esm.town/v/saolsen/sudoku\";\n\ntype Cell = {\n row: number;\n col: number;\n};\n\ntype Val = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;\n\ntype PossibleValues = Array | null>>;\n\ntype Constraint = { cell: Cell; value: Val };\n\nfunction constrainRow(possible_values: PossibleValues, row: number, value: Val): Constraint[] {\n const constrained: Constraint[] = [];\n for (let col = 0; col < 9; col++) {\n const set = possible_values[row][col];\n if (set !== null && set.has(value)) {\n set.delete(value);\n constrained.push({ cell: { row, col }, value });\n }\n }\n return constrained;\n}\n\nfunction constrainCol(possible_values: PossibleValues, col: number, value: Val): Constraint[] {\n const constrained: Constraint[] = [];\n for (let row = 0; row < 9; row++) {\n const set = possible_values[row][col];\n if (set !== null && set.has(value)) {\n set.delete(value);\n constrained.push({ cell: { row, col }, value });\n }\n }\n return constrained;\n}\n\nfunction constrainBox(possible_values: PossibleValues, row: number, col: number, value: Val): Constraint[] {\n const constrained: Constraint[] = [];\n const box_row = Math.floor(row / 3);\n const box_col = Math.floor(col / 3);\n for (let row = box_row * 3; row < box_row * 3 + 3; row++) {\n for (let col = box_col * 3; col < box_col * 3 + 3; col++) {\n const set = possible_values[row][col];\n if (set !== null && set.has(value)) {\n set.delete(value);\n constrained.push({ cell: { row, col }, value });\n }\n }\n }\n return constrained;\n}\n\nfunction undoConstraints(possible_values: PossibleValues, constraints: Constraint[]) {\n for (const { cell: { row, col }, value } of constraints) {\n possible_values[row][col]!.add(value);\n }\n}\n\n// Lets try a \"solve like a human\" algorithm.\nexport function solve(sudoku: Sudoku): Sudoku | null {\n sudoku = Sudoku.parse(sudoku);\n\n const possible_values: PossibleValues = [];\n for (let row = 0; row < 9; row++) {\n const row_possible_values: Set[] = [];\n for (let col = 0; col < 9; col++) {\n row_possible_values.push(new Set([1, 2, 3, 4, 5, 6, 7, 8, 9]));\n }\n possible_values.push(row_possible_values);\n }\n\n // Constrain the possible values based on the initial values.\n for (let row = 0; row < 9; row++) {\n for (let col = 0; col < 9; col++) {\n if (sudoku[row][col] !== 0) {\n const value = sudoku[row][col] as Val;\n\n // No possible values for this cell, it is already filled in.\n possible_values[row][col] = null;\n\n // Remove the value from the possible values for the row, column, and box.\n constrainRow(possible_values, row, value);\n constrainCol(possible_values, col, value);\n constrainBox(possible_values, row, col, value);\n }\n }\n }\n\n const selections: {\n row: number;\n col: number;\n val: Val;\n remaining_choices: Val[];\n constraints: Constraint[];\n }[] = [];\n\n while (true) {\n let min_size = Infinity;\n let selected_row = Infinity;\n let selected_col = Infinity;\n let selected_value: Val = 1;\n let remaining_choices: Val[] = [];\n\n let all_slots_filled = true;\n\n // Find the first cell with the minimum number of possible values.\n find_slot:\n for (let row = 0; row < 9; row++) {\n for (let col = 0; col < 9; col++) {\n const set = possible_values[row][col];\n if (set !== null) {\n all_slots_filled = false;\n if (set.size === 0) {\n // Unsolvable Puzzle, backtrack.\n while (true) {\n const last_selection = selections.pop();\n if (last_selection === undefined) {\n console.log(\"Unsolvable\");\n return null;\n }\n const { row: bt_row, col: bt_col, val: bt_val, remaining_choices: bt_choices, constraints } =\n last_selection;\n\n undoConstraints(possible_values, constraints);\n sudoku[bt_row][bt_col] = 0;\n possible_values[bt_row][bt_col] = new Set([bt_val, ...bt_choices]);\n\n if (bt_choices.length === 0) {\n // No more choices, backtrack further.\n continue;\n }\n\n selected_row = bt_row;\n selected_col = bt_col;\n remaining_choices = bt_choices;\n selected_value = remaining_choices.shift()!;\n break;\n }\n break find_slot;\n } else if (set.size < min_size) {\n selected_row = row;\n selected_col = col;\n min_size = set.size;\n remaining_choices = [...set.values()];\n remaining_choices.sort((a, b) => a - b);\n selected_value = remaining_choices.shift()!;\n }\n }\n }\n }\n\n if (all_slots_filled) {\n return sudoku;\n }\n\n sudoku[selected_row][selected_col] = selected_value;\n possible_values[selected_row][selected_col] = null;\n const constrained_rows = constrainRow(possible_values, selected_row, selected_value);\n const constrained_cols = constrainCol(possible_values, selected_col, selected_value);\n const constrained_boxes = constrainBox(possible_values, selected_row, selected_col, selected_value);\n const constraints = [...constrained_boxes, ...constrained_cols, ...constrained_rows];\n selections.push({\n row: selected_row,\n col: selected_col,\n val: selected_value,\n remaining_choices,\n constraints,\n });\n }\n}","deleted","label",[98],"permalink","https://www.val.town/x/saolsen/sudoku_solver_human_search/code/main.tsx","extension","actionData","errors"]