Skip to content

Instantly share code, notes, and snippets.

@CalfordMath

CalfordMath/Sudoku Solver - Excel Formulas Only, (No VBA)

Last active May 4, 2024 23:51
Show Gist options
  • Save CalfordMath/9c83740d044dbd9cca91102e4017a47a to your computer and use it in GitHub Desktop.
Save CalfordMath/9c83740d044dbd9cca91102e4017a47a to your computer and use it in GitHub Desktop.
Download ZIP
A Lambda Function with nested recursion that receives a 9x9 puzzle range (i.e. B2:J10) and outputs a 9x9 spilled range with the completed puzzle. No VBA. Just formulas. No specific cell references beyond the input range. It takes about 3 minutes and 3 seconds to solve the world's current hardest sudoku puzzle on an average fast computer. It inco…
Raw
Sudoku Solver - Excel Formulas Only, (No VBA)
Sudoku = LAMBDA(Puzzle,
LET(
Options, MAKEARRAY(27, 27, LAMBDA(r, c, MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3))),
numgrid, SEQUENCE(9, 9, 1),
UpdatedPuzzle, LET(
ApplyLogic, LAMBDA(ApplyLogic, Puzzle, Options,
LET(
Candidates, MAKEARRAY(
27,
27,
LAMBDA(r, c,
(SUM((INDEX(Puzzle, FLOOR((r - 1) / 3, 1) + 1, SEQUENCE(1, 9, 1, 1)) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
(SUM((INDEX(Puzzle, SEQUENCE(9, 1, 1, 1), FLOOR((c - 1) / 3, 1) + 1) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
(SUM((INDEX(Puzzle, FLOOR((r - 1) / 9, 1) * 3 + 1 + SEQUENCE(3, 1, 0, 1), FLOOR((c - 1) / 9, 1) * 3 + 1 + SEQUENCE(1, 3, 0, 1)) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
((INDEX(Puzzle, FLOOR((r - 1) / 3, 1) + 1, FLOOR((c - 1) / 3, 1) + 1) > 0) * 1 = 0)
)
) * Options,
WinFilter, CEILING(
(
MAKEARRAY(
27,
27,
LAMBDA(r, c,
(SUM((INDEX(Candidates, (FLOOR((r + 8) / 9, 1) - 1) * 9 + SEQUENCE(9, 1, 1, 1), (FLOOR((c + 8) / 9, 1) - 1) * 9 + SEQUENCE(1, 9, 1, 1)) = INDEX(Candidates, r, c)) * 1) = 1) * 1
)
) + MAKEARRAY(27, 27, LAMBDA(r, c, (SUM((INDEX(Candidates, SEQUENCE(27, 1, 1, 1), (FLOOR((c + 2) / 3, 1) - 1) * 3 + SEQUENCE(1, 3, 1, 1)) = INDEX(Candidates, r, c)) * 1) = 1) * 1)) +
MAKEARRAY(27, 27, LAMBDA(r, c, (SUM((INDEX(Candidates, (FLOOR((r + 2) / 3, 1) - 1) * 3 + SEQUENCE(3, 1, 1, 1), SEQUENCE(1, 27, 1, 1)) = INDEX(Candidates, r, c)) * 1) = 1) * 1)) +
MAKEARRAY(
27,
27,
LAMBDA(r, c, (SUM((INDEX(Candidates, (FLOOR((r + 2) / 3, 1) - 1) * 3 + SEQUENCE(3, 1, 1, 1), (FLOOR((c + 2) / 3, 1) - 1) * 3 + SEQUENCE(1, 3, 1, 1)) = 0) * 1) = 8))
) * (Candidates / Options)
) / 4,
1
),
IF(
MAX(WinFilter) > 0,
ApplyLogic(ApplyLogic, Puzzle + MAKEARRAY(9, 9, LAMBDA(r, c, SUM(INDEX(Candidates * WinFilter, (r - 1) * 3 + SEQUENCE(3, 1, 1, 1), (c - 1) * 3 + SEQUENCE(1, 3, 1, 1))))), Options),
Puzzle
)
)
),
ApplyLogic(ApplyLogic, Puzzle, Options)
),
Duplicates, OR(
PRODUCT(
MAKEARRAY(
9,
9,
LAMBDA(r, c,
MAX(1, SUM((INDEX(UpdatedPuzzle, r, SEQUENCE(1, 9, 1, 1)) = c) * 1)) * MAX(1, SUM((INDEX(UpdatedPuzzle, SEQUENCE(9, 1, 1, 1), c) = r) * 1)) *
MAX(1, SUM((INDEX(UpdatedPuzzle, FLOOR((r - 1) / 3, 1) * 3 + SEQUENCE(1, 3, 1, 1), FLOOR((c - 1) / 3, 1) * 3 + SEQUENCE(3, 1, 1, 1)) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1))
)
)
) > 1,
MAX(VALUE(UpdatedPuzzle)) > 9
),
Candidates, MAKEARRAY(
27,
27,
LAMBDA(r, c,
(SUM((INDEX(UpdatedPuzzle, FLOOR((r - 1) / 3, 1) + 1, SEQUENCE(1, 9, 1, 1)) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
(SUM((INDEX(UpdatedPuzzle, SEQUENCE(9, 1, 1, 1), FLOOR((c - 1) / 3, 1) + 1) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
(SUM((INDEX(UpdatedPuzzle, FLOOR((r - 1) / 9, 1) * 3 + 1 + SEQUENCE(3, 1, 0, 1), FLOOR((c - 1) / 9, 1) * 3 + 1 + SEQUENCE(1, 3, 0, 1)) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
((INDEX(UpdatedPuzzle, FLOOR((r - 1) / 3, 1) + 1, FLOOR((c - 1) / 3, 1) + 1) > 0) * 1 = 0)
)
) * Options,
x, INDEX(
SORTBY(
SEQUENCE(1, 81, 1, 1),
TOROW(
MAKEARRAY(
9,
9,
LAMBDA(r, c, LET(CandidatesSum, SUM((INDEX(Candidates, SEQUENCE(3, 1, (r - 1) * 3 + 1, 1), SEQUENCE(1, 3, (c - 1) * 3 + 1, 1)) > 0) * 1), IF(CandidatesSum = 0, 10, CandidatesSum)))
)
),
1
),
1,
1
),
IF(
AND(Duplicates = FALSE, MIN(VALUE(UpdatedPuzzle)) > 0),
UpdatedPuzzle,
IF(
Duplicates,
NA(),
LET(
nCandidatesSquare, TOCOL(
VALUE(
INDEX(
Candidates,
(FLOOR((x - 1) / 9, 1)) * 3 + SEQUENCE(3, 1, 1, 1),
(MOD(x + 8, 9)) * 3 + SEQUENCE(1, 3, 1, 1)
)
)
),
nCandidates, FILTER(nCandidatesSquare, nCandidatesSquare > 0),
test, LAMBDA(test, nCandidates, function,
IF(
COUNT(nCandidates),
IFNA(
function(@nCandidates),
test(test, DROP(nCandidates, 1), function)
),
NA()
)
),
test(
test,
nCandidates,
LAMBDA(value, Sudoku(IF(numgrid = x, value, UpdatedPuzzle)))
)
)
)
)
)
);
Raw
Sudoku Solver with Comments
//This commented version is not up to date. use the above version
Sudoku = LAMBDA(inputPuzzle,
LET(
//receive 9x9 array and convert it to 81-number string, or receive the looped 1-column list of puzzle strings
PuzzleTree, IF(COLUMNS(inputPuzzle) > 1, TEXTJOIN("", FALSE, TOROW(IFERROR(VALUE(inputPuzzle), 0), 0)) & "~1", inputPuzzle),
PuzzleTreeRows, ROWS(PuzzleTree),
//create the 9x9 array in memory from the string
Puzzle, MAKEARRAY(9, 9, LAMBDA(r, c, VALUE(MID(INDEX(TEXTSPLIT(INDEX(PuzzleTree, PuzzleTreeRows, 1), "~"), 1, 1), FLOOR(r - 1, 1) * 9 + c, 1)))),
//generate the large array with options 1->9 for each square
Options, MAKEARRAY(27, 27, LAMBDA(r, c, MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3))),
//Fill in all logically deduced values based on the current puzzle
UpdatedPuzzle, LET(
//Use recursion to keep updating and checking for new logical moves until none are left
ApplyLogic, LAMBDA(ApplyLogic, Puzzle, Options,
LET(
//Eliminate options based on values already contained in rows, columns, and boxes to leave only eligible Candidates
Candidates, MAKEARRAY(
27,
27,
LAMBDA(r, c,
//Check to see if an option is already in the puzzle. Narrow the 27x27 regions to the corresponding 9x9 regions to be searched.
//Rows
(SUM((INDEX(Puzzle, FLOOR((r - 1) / 3, 1) + 1, SEQUENCE(1, 9, 1, 1)) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
//Columns
(SUM((INDEX(Puzzle, SEQUENCE(9, 1, 1, 1), FLOOR((c - 1) / 3, 1) + 1) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
//Boxes
(SUM((INDEX(Puzzle, FLOOR((r - 1) / 9, 1) * 3 + 1 + SEQUENCE(3, 1, 0, 1), FLOOR((c - 1) / 9, 1) * 3 + 1 + SEQUENCE(1, 3, 0, 1)) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
//Square already filled in
((INDEX(Puzzle, FLOOR((r - 1) / 3, 1) + 1, FLOOR((c - 1) / 3, 1) + 1) > 0) * 1 = 0)
)
) * Options,
//Find hidden singles (https://sudoku.com/sudoku-rules/hidden-singles) by checking if a candidate is the last hope for a unit (row, column, or square) to achieve its number,
//And find naked singles (http://sudopedia.enjoysudoku.com/Naked_Single.html) by checking if a candidate is the only candidate for that square
WinFilter, CEILING(
(
MAKEARRAY(
27,
27,
//Search boxes: count the number of occurrences for a specific candidate and check if this equals 1
LAMBDA(r, c,
(SUM((INDEX(Candidates, (FLOOR((r + 8) / 9, 1) - 1) * 9 + SEQUENCE(9, 1, 1, 1), (FLOOR((c + 8) / 9, 1) - 1) * 9 + SEQUENCE(1, 9, 1, 1)) = INDEX(Candidates, r, c)) * 1) = 1) * 1
)
) +
//Similar logic is applied to columns (if a candidate is the last hope)
MAKEARRAY(27, 27, LAMBDA(r, c, (SUM((INDEX(Candidates, SEQUENCE(27, 1, 1, 1), (FLOOR((c + 2) / 3, 1) - 1) * 3 + SEQUENCE(1, 3, 1, 1)) = INDEX(Candidates, r, c)) * 1) = 1) * 1)) +
//And to rows
MAKEARRAY(27, 27, LAMBDA(r, c, (SUM((INDEX(Candidates, (FLOOR((r + 2) / 3, 1) - 1) * 3 + SEQUENCE(3, 1, 1, 1), SEQUENCE(1, 27, 1, 1)) = INDEX(Candidates, r, c)) * 1) = 1) * 1)) +
//only candidate in the square
MAKEARRAY(27, 27, LAMBDA(r, c, (SUM((INDEX(Candidates, (FLOOR((r + 2) / 3, 1) - 1) * 3 + SEQUENCE(3, 1, 1, 1), (FLOOR((c + 2) / 3, 1) - 1) * 3 + SEQUENCE(1, 3, 1, 1)) = 0) * 1) = 8))) *
(Candidates / Options)
) / 4,
1
),
//The resulting array when we add the filters together contains 1s only in places where a hidden single or naket single candidates occurs, and a zero everywhere else
IF(
//If there were still logically deduced numbers to add, update the puzzle and loop it recursively to check for more
MAX(WinFilter) > 0,
ApplyLogic(ApplyLogic, Puzzle + MAKEARRAY(9, 9, LAMBDA(r, c, SUM(INDEX(Candidates * WinFilter, (r - 1) * 3 + SEQUENCE(3, 1, 1, 1), (c - 1) * 3 + SEQUENCE(1, 3, 1, 1))))), Options),
//otherwise, return the current puzzle since it's as solved as possible using logical deduction
Puzzle
)
)
),
ApplyLogic(ApplyLogic, Puzzle, Options) //initial call to the recursive lambda ApplyLogic
),
//Incorrect branches will lead to a contradiction, where the same value is the only option for more than one square in a row, column, or box. Catch this and backtrack!
Duplicates, OR(
PRODUCT(
MAKEARRAY(
9,
9,
LAMBDA(r, c,
//Count how many values in a particular row/column/box are equal to 1 through 9, multiplying these results. If there are none, we assign 1 so the product isn't zero.
MAX(1, SUM((INDEX(UpdatedPuzzle, r, SEQUENCE(1, 9, 1, 1)) = c) * 1)) * MAX(1, SUM((INDEX(UpdatedPuzzle, SEQUENCE(9, 1, 1, 1), c) = r) * 1)) *
MAX(1, SUM((INDEX(UpdatedPuzzle, FLOOR((r - 1) / 3, 1) * 3 + SEQUENCE(1, 3, 1, 1), FLOOR((c - 1) / 3, 1) * 3 + SEQUENCE(3, 1, 1, 1)) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1))
)
)
//If the product of these products is greater than 1, there's a duplicate somewhere
) > 1,
//if multiple conclusions were reached for the same square, it would have added the values together potentially giving a result over 9. (Sums under 9 would be caught by a duplicate)
MAX(UpdatedPuzzle > 9)
),
//need to determine candidates again, now that logic has been exhausted, filter out values already contained in the row, columns, or box of each square.
Candidates, MAKEARRAY(
27,
27,
LAMBDA(r, c,
(SUM((INDEX(UpdatedPuzzle, FLOOR((r - 1) / 3, 1) + 1, SEQUENCE(1, 9, 1, 1)) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
(SUM((INDEX(UpdatedPuzzle, SEQUENCE(9, 1, 1, 1), FLOOR((c - 1) / 3, 1) + 1) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
(SUM((INDEX(UpdatedPuzzle, FLOOR((r - 1) / 9, 1) * 3 + 1 + SEQUENCE(3, 1, 0, 1), FLOOR((c - 1) / 9, 1) * 3 + 1 + SEQUENCE(1, 3, 0, 1)) = MOD(c - 1, 3) + 1 + 3 * MOD(r - 1, 3)) * 1) = 0) *
((INDEX(UpdatedPuzzle, FLOOR((r - 1) / 3, 1) + 1, FLOOR((c - 1) / 3, 1) + 1) > 0) * 1 = 0)
)
) * Options,
//Determine which square has the fewest candidates so branching can be most efficient
x, INDEX(
SORTBY(
SEQUENCE(1, 81, 1, 1),
TOROW(
MAKEARRAY(9, 9, LAMBDA(r, c, LET(CandidatesSum, SUM((INDEX(Candidates, SEQUENCE(3, 1, (r - 1) * 3 + 1, 1), SEQUENCE(1, 3, (c - 1) * 3 + 1, 1)) > 0) * 1), IF(CandidatesSum = 0, 10, CandidatesSum))))
),
1
),
1,
1
),
//Grab the last character of the PuzzleTree giving the current branch index
n_index, VALUE(RIGHT(INDEX(PuzzleTree, PuzzleTreeRows, 1), 1)),
//Get a string of the candidate options for square x, the optimal branching square
nCandidates, SUBSTITUTE(TEXTJOIN("", FALSE, TOROW(VALUE(INDEX(Candidates, (FLOOR((x - 1) / 9, 1)) * 3 + SEQUENCE(3, 1, 1, 1), (MOD(x + 8, 9)) * 3 + SEQUENCE(1, 3, 1, 1))), 0)), "0", ""),
//If there no candidates (puzzle is solved or impossible) or if all branches have already been exhausted, flag this with -1, otherwise select the next branch option
//Trying largest to smallest proved faster for a particular puzzle, but is not necessary in general
n, IF(OR(nCandidates = "", n_index > LEN(nCandidates)), -1, VALUE(MID(nCandidates, LEN(nCandidates) - n_index + 1, 1))),
//For backtracking purposes, grab the branch index of the previous node
LastnIndex, IF(PuzzleTreeRows > 1, VALUE(RIGHT(INDEX(PuzzleTree, PuzzleTreeRows - 1, 1), 1)), -1),
IF(
AND(Duplicates = FALSE, MIN(UpdatedPuzzle) > 0),
//Output the solution as a 9x9 array
MAKEARRAY(9, 9, LAMBDA(r, c, VALUE(MID(TEXTJOIN("", FALSE, TOROW(VALUE(UpdatedPuzzle), 0)), FLOOR(r - 1, 1) * 9 + c, 1)))),
IF(
//Hit a deadend with the initial puzzle
AND(OR(Duplicates, n = -1), PuzzleTreeRows = 1),
"Impossible",
IF(
//Hit a duplicate dead end or all branches have been tried
OR(Duplicates, n = -1),
//backtrack to the last node and start clean with another branch, it will keep backing up to a node with branches remaining.
Sudoku(MAKEARRAY(PuzzleTreeRows - 1, 1, LAMBDA(r, c, IF(r < PuzzleTreeRows - 1, INDEX(PuzzleTree, r, c), LEFT(INDEX(PuzzleTree, PuzzleTreeRows - 1, 1), 81) & "~" & LastnIndex + 1)))),
//Hit the end of logic, but not a contradiction situation. Continue with the next branch guess
Sudoku(MAKEARRAY(PuzzleTreeRows + 1, 1, LAMBDA(r, c, IF(r < PuzzleTreeRows + 1, INDEX(PuzzleTree, r, c), REPLACE(TEXTJOIN("", FALSE, TOROW(VALUE(UpdatedPuzzle), 0)), x, 1, n) & "~1"))))
)
)
)
)
);
@CalfordMath
Copy link
Author

CalfordMath commented Mar 21, 2023 •
edited
Loading

This recursive Lambda function will solve any Sudoku Puzzle. Pass it a 9x9 puzzle range and it will output a 9x9 spilled range with the solution.
Example:
=SolveSudoku(B2:J10)

Using Excel 365, click on Excel Labs in the Home menu bar:
image
Then open Advanced Formula Environment:
image

Go to the Modules tab, and select the Import From Url option and paste the Gist share link
image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment