[{"_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_exact_cover","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","aff38994-27ac-11f0-9edc-569c3dd06744","createdAt",["D",1746228308830],"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",6,"aff3c878-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},"b015a45c-27ac-11f0-9edc-569c3dd06744","fileId","aff62cbc-27ac-11f0-9edc-569c3dd06744","parentId","branchId","branchVersion","latest",["D",1716495829241],5,"fileType","script","content","// Exact Cover Sudoku Solver\nimport { Sudoku } from \"https://esm.town/v/saolsen/sudoku\";\n\n// An exact cover problem is solved by taking a list of possible constraint\n// rows and finding a subset of them that covers each column exactly once.\n// If thought of as a binary matrix, we would want to find a set of rows\n// such that each column has exactly one 1 in it.\n\n// To express sudoku as an exact cover problem, we need to encode all the\n// possible numbers that can go into each slot, along with their\n// constraints, in a way that obeys the rules of sudoku.\n// There will be columns for each slot, row, column, and box,\n// So there will be a row for each number and slot for each combination of\n// constraints.\n// eg [1,0...0, 1,0.....0,...] and\n// [1,0...0, 0,1,0...0,...] are both solutions with 1 in the first slot,\n// but the first also says that the 1 is in the first column and the second\n// says that the 1 is in the second column. This way we can account for the\n// constraints of the sudoku board and when we find a covering set of rows\n// we know it is a valid solution to the sudoku board.\n// The full matrix looks like this\n// https://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm\n\n// Each column is a constraint, each row is a possible solution\n// you pick a row to add to the solution, then cover up all the columns\n// that have been satisfied, and all the rows that conflict with an already\n// satisfied constraint. Then you have a smaller sub-matrix to continue\n// picking rows from.\n\n// Instead of actually using a matrix with so many columns, we can use a\n// sparse representation, since most columns will be 0. We can make\n// nodes for each of the 1s in the matrix and link them together in a\n// linked list.\n\n// By using a doubly linked list for the sparse matrix, we can easily remove\n// and replace columns and rows from the matrix to make the search for a\n// solution faster.\n// The algorithm is called \"Dancing Links\" and it is actually pretty similar\n// to the brute force backtracking algorithm. Instead of trying every\n// possible number in every slot (and backtracking on failures), we select a\n// slot value that we know doesn't conflict with any of the already resolved\n// constraints, and then we remove all rows with constraints that are satisfied by\n// the slot value so there are a lot fewer possibilities to try next and the search\n// is much faster.\n\n// There is some value for row,col\n// This constraint makes sure the puzzle is fully filled out.\ntype SlotConstraint = {\n kind: \"slot\";\n row: number; // 0-8\n col: number; // 0-8\n};\n\n// The value `value` is in row `row`.\n// This constraint makes sure that each row has each number exactly once.\ntype RowConstraint = {\n kind: \"row\";\n row: number; // 0-8\n value: number; // 1-9\n};\n\n// The value `value` is in col `col`.\n// This constraint makes sure that each column has each number exactly once.\ntype ColConstraint = {\n kind: \"col\";\n col: number; // 0-8\n value: number; // 1-9\n};\n\n// The value `value` is in box `box`.\n// This constraint makes sure that each box has each number exactly once.\ntype BoxConstraint = {\n kind: \"box\";\n box: number; // 0-8\n value: number; // 1-9\n};\n\ntype Constraint = SlotConstraint | RowConstraint | ColConstraint | BoxConstraint;\n\nconst NUM_CONSTRAINTS = 324;\n\ntype Slot = {\n row: number; // 0-8\n col: number; // 0-8\n value: number; // 1-9\n};\n\nfunction slotToConstraints(slot: Slot): Constraint[] {\n console.assert(slot.row >= 0 && slot.row <= 8);\n console.assert(slot.col >= 0 && slot.col <= 8);\n console.assert(slot.value >= 1 && slot.value <= 9);\n const { row, col, value } = slot;\n const box = Math.floor(row / 3) * 3 + Math.floor(col / 3);\n return [\n { kind: \"slot\", row, col },\n { kind: \"row\", row, value },\n { kind: \"col\", col, value },\n { kind: \"box\", box, value },\n ];\n}\n\nfunction constraintsToSlot(constraints: Constraint[]): Slot {\n console.assert(constraints.length === 4);\n let row = null;\n let col = null;\n let value = null;\n for (let i = 0; i < constraints.length; i++) {\n const constraint = constraints[i];\n switch (constraint.kind) {\n case \"slot\":\n if (row !== null) { console.assert(row === constraint.row); }\n if (col !== null) { console.assert(col === constraint.col); }\n row = constraint.row;\n col = constraint.col;\n break;\n case \"row\":\n if (row !== null) { console.assert(row === constraint.row); }\n if (value !== null) { console.assert(value === constraint.value); }\n row = constraint.row;\n value = constraint.value;\n break;\n case \"col\":\n if (col !== null) { console.assert(col === constraint.col); }\n if (value !== null) { console.assert(value === constraint.value); }\n col = constraint.col;\n value = constraint.value;\n break;\n case \"box\":\n if (value !== null) { console.assert(value === constraint.value); }\n value = constraint.value;\n break;\n }\n }\n console.assert(row !== null && col !== null && value !== null);\n return { row: row!, col: col!, value: value! };\n}\n\nfunction cIndex(constraint: Constraint): number {\n switch (constraint.kind) {\n case \"slot\":\n return constraint.row * 9 + constraint.col;\n case \"row\":\n return 9 * 9 + constraint.row * 9 + constraint.value - 1;\n case \"col\":\n return 9 * 9 + 9 * 9 + constraint.col * 9 + constraint.value - 1;\n case \"box\":\n return 9 * 9 + 9 * 9 + 9 * 9 + constraint.box * 9 + constraint.value - 1;\n }\n}\n\ntype Node = {\n head: number;\n prev: number;\n next: number;\n up: number;\n down: number;\n};\n\ntype Column = Node & {\n constraint: Constraint;\n count: number;\n};\n\nclass Matrix {\n count: number;\n root: number;\n nodes: (Node | Column)[];\n\n constructor() {\n const constraints: Constraint[] = [];\n\n for (let row = 0; row < 9; row++) {\n for (let col = 0; col < 9; col++) {\n constraints.push({ kind: \"slot\", row, col });\n }\n }\n\n for (let row = 0; row < 9; row++) {\n for (let value = 1; value <= 9; value++) {\n constraints.push({ kind: \"row\", row, value });\n }\n }\n\n for (let col = 0; col < 9; col++) {\n for (let value = 1; value <= 9; value++) {\n constraints.push({ kind: \"col\", col, value });\n }\n }\n\n for (let box = 0; box < 9; box++) {\n for (let value = 1; value <= 9; value++) {\n constraints.push({ kind: \"box\", box, value });\n }\n }\n\n console.assert(constraints.length === NUM_CONSTRAINTS);\n\n const nodes: (Node | Column)[] = [];\n\n // Create a column header node for each constraint.\n for (let i = 0; i < constraints.length; i++) {\n const constraint = constraints[i];\n // Assert the constraint order matches the index helper.\n console.assert(cIndex(constraint) === i);\n console.assert(i === nodes.length);\n\n const head = i;\n const prev = i === 0 ? NUM_CONSTRAINTS - 1 : i - 1;\n const next = i === NUM_CONSTRAINTS - 1 ? 0 : i + 1;\n const up = i;\n const down = i;\n const count = 0;\n nodes.push({ head, prev, next, up, down, constraint, count });\n }\n\n // For each possible slot value.\n // Add a row of nodes for each constraint it satisfies.\n for (let row = 0; row < 9; row++) {\n for (let col = 0; col < 9; col++) {\n for (let value = 1; value <= 9; value++) {\n const slot = { row, col, value };\n const constraints = slotToConstraints(slot);\n console.assert(constraints.length === 4);\n\n const i = nodes.length;\n\n // Add the nodes as a linked row.\n nodes.push({ head: cIndex(constraints[0]), prev: i + 3, next: i + 1, up: -1, down: -1 });\n nodes.push({ head: cIndex(constraints[1]), prev: i, next: i + 2, up: -1, down: -1 });\n nodes.push({ head: cIndex(constraints[2]), prev: i + 1, next: i + 3, up: -1, down: -1 });\n nodes.push({ head: cIndex(constraints[3]), prev: i + 2, next: i, up: -1, down: -1 });\n\n // Append each node to its column list.\n for (let n_i = i; n_i <= i + 3; n_i++) {\n const node = nodes[n_i] as Node;\n const column = nodes[node.head] as Column;\n const last_n_i = column.up;\n nodes[last_n_i].down = n_i;\n nodes[n_i].up = last_n_i;\n nodes[n_i].down = node.head;\n nodes[node.head].up = n_i;\n (nodes[node.head] as Column).count++;\n }\n }\n }\n }\n\n this.count = NUM_CONSTRAINTS;\n this.root = 0;\n this.nodes = nodes;\n }\n\n isSolvable(): boolean {\n // If the matrix is empty, then the puzzle is solved.\n if (this.count === 0) {\n return true;\n }\n // If any uncovered column is empty, then the puzzle is unsolvable.\n let i = this.root;\n do {\n const column = this.nodes[i] as Column;\n if (column.count === 0) {\n return false;\n }\n i = column.next;\n } while (i !== this.root);\n return true;\n }\n\n rowConstraints(n_i: number): Constraint[] {\n const constraints: Constraint[] = [];\n let i = n_i;\n do {\n const node = this.nodes[i];\n const column = this.nodes[node.head] as Column;\n constraints.push(column.constraint);\n i = node.next;\n } while (i !== n_i);\n\n return constraints;\n }\n\n shortestColumn(): number {\n console.assert(this.count > 0);\n let count = Infinity;\n let shortest = Infinity;\n let i = this.root;\n do {\n const column = this.nodes[i] as Column;\n if (column.count === count) {\n if (i < shortest) {\n shortest = i;\n }\n } else if (column.count < count) {\n count = column.count;\n shortest = i;\n }\n i = column.next;\n } while (i !== this.root);\n return shortest;\n }\n\n cover(c_i: number): void {\n const column = this.nodes[c_i] as Column;\n\n // Remove the column from the list of columns.\n this.nodes[column.prev].next = column.next;\n this.nodes[column.next].prev = column.prev;\n this.count--;\n\n // Walk down the column.\n for (let n_i = column.down; n_i !== c_i; n_i = this.nodes[n_i].down) {\n // Walk right across the row.\n for (let i = this.nodes[n_i].next; i !== n_i; i = this.nodes[i].next) {\n const node = this.nodes[i];\n this.nodes[node.up].down = node.down;\n this.nodes[node.down].up = node.up;\n (this.nodes[node.head] as Column).count--;\n }\n }\n\n // If the column is the root, update the root.\n if (this.root === c_i) {\n this.root = column.next;\n }\n }\n\n uncover(c_i: number): void {\n const column = this.nodes[c_i] as Column;\n\n // Walk up the column.\n for (let n_i = column.up; n_i !== c_i; n_i = this.nodes[n_i].up) {\n // Walk left across the row.\n for (let i = this.nodes[n_i].prev; i !== n_i; i = this.nodes[i].prev) {\n const node = this.nodes[i];\n this.nodes[node.down].up = i;\n this.nodes[node.up].down = i;\n (this.nodes[node.head] as Column).count++;\n }\n }\n\n // Return the column from the list of columns.\n this.nodes[column.prev].next = c_i;\n this.nodes[column.next].prev = c_i;\n this.count++;\n }\n}\n\nexport function solve(sudoku: Sudoku): Sudoku | null {\n sudoku = Sudoku.parse(sudoku);\n const matrix = new Matrix();\n\n // Cover all columns satisfied by the already filled slots.\n for (let row = 0; row < 9; row++) {\n for (let col = 0; col < 9; col++) {\n const value = sudoku[row][col];\n if (value !== 0) {\n const slot = { row, col, value };\n const constraints = slotToConstraints(slot);\n for (let i = 0; i < constraints.length; i++) {\n const c_i = cIndex(constraints[i]);\n matrix.cover(c_i);\n }\n }\n }\n }\n\n if (!matrix.isSolvable()) {\n console.log(\"Unsolvable\");\n return null;\n }\n\n const solution: { slot: Slot; n_i: number }[] = [];\n\n while (matrix.count > 0) {\n let n_i = 0;\n let node: Node;\n\n if (matrix.isSolvable()) {\n // Pick the column with the fewest nodes\n const c_i = matrix.shortestColumn();\n const column = matrix.nodes[c_i] as Column;\n // Pick the first node in the column\n n_i = column.down;\n node = matrix.nodes[n_i];\n } else {\n // Backtrack\n do {\n const last_slot = solution.pop();\n if (last_slot === undefined) {\n console.log(\"Unsolvable\");\n return null;\n }\n // Uncover the columns.\n const { slot, n_i: last_n_i } = last_slot;\n const constraints = slotToConstraints(slot);\n for (let i = constraints.length - 1; i >= 0; i--) {\n const c_i = cIndex(constraints[i]);\n matrix.uncover(c_i);\n }\n // Choose the next node in the column.\n n_i = matrix.nodes[last_n_i].down;\n node = matrix.nodes[n_i];\n } while (n_i === node.head);\n }\n\n const row_constraints = matrix.rowConstraints(n_i);\n const slot = constraintsToSlot(row_constraints);\n solution.push({ slot, n_i });\n\n for (let i = 0; i < row_constraints.length; i++) {\n const c_i = cIndex(row_constraints[i]);\n matrix.cover(c_i);\n }\n }\n\n // Fill in the solution slots.\n for (let i = 0; i < solution.length; i++) {\n const { slot } = solution[i];\n sudoku[slot.row][slot.col] = slot.value;\n }\n\n return sudoku;\n}","deleted","label",[98],"permalink","https://www.val.town/x/saolsen/sudoku_solver_exact_cover/code/main.tsx","extension","actionData","errors"]