Skip to content

Instantly share code, notes, and snippets.

@lhem
Last active May 4, 2024 23:54
Show Gist options
  • Save lhem/938a4e4a624bd2f68b6f7362b7971004 to your computer and use it in GitHub Desktop.
Save lhem/938a4e4a624bd2f68b6f7362b7971004 to your computer and use it in GitHub Desktop.
//ref: https://codereview.stackexchange.com/q/199771
solver=LAMBDA(grid,
LET(numbers,SEQUENCE(9),
numgrid,SEQUENCE(9,9,0),
pos,XMATCH(0,TOCOL(grid*1))-1,
IF(ISNA(pos),
grid,
LET(i,INT(pos/9),
j,MOD(pos,9),
row,INDEX(grid,i+1,),
col,INDEX(grid,,j+1),
sqr,INDEX(grid,FLOOR(i,3)+{1;2;3},FLOOR(j,3)+{1,2,3}),
values,UNIQUE(VSTACK(numbers,col,TOCOL(row),TOCOL(sqr)),,1),
test(values,LAMBDA(value,solver(IF(numgrid=pos,value,grid))))
)
)
)
);
test=LAMBDA(values,function,
IF(COUNT(values),
IFNA(function(@values),
test(DROP(values,1),function)
),
NA()
)
)
//example:
//=solver({
//0,0,0,0,0,0,0,9,0;
//0,9,7,0,0,0,4,0,0;
//0,0,8,0,6,0,0,7,0;
//0,0,0,9,8,7,0,0,0;
//0,0,0,0,0,4,0,0,1;
//0,0,0,0,0,6,0,2,4;
//2,0,0,0,0,0,5,0,3;
//0,4,0,0,5,0,0,0,0;
//6,0,0,8,0,0,0,0,0})
@CalfordMath
Copy link

This is a brilliant Excel adaptation of the backtracking algorithm to solve a sudoku puzzle! I love the minimalism, in particular, the way values is determined with the UNIQUE & VSTACK functions. I learned a ton! For those reading this, to see an excellent visual walk-through of this code, check out Owen Price's LinkedIn post. I tried this sudoku solver function with the world's hardest sudoku puzzle, and it solved it in about 1 min 33 seconds on my Surface Pro 7. I've been trying to get a clear answer on the recursion limits of lambda functions but it seems a bit unclear; kind of a combination of the number of loops and the computation performed each loop. I didn't actually think a pure backtracking approach would work in Excel, due to the number of recursion loops it could require! I had also created a lambda function to solve Sudoku puzzles (my code was far less concise than this one, but it works!), but I began from a logical deduction direction, similar to Chris Rae's approach, but using dynamic arrays and recursion to have the computer do all the updating automatically. I only learned about backtracking (guessing) when my code failed for puzzles that cannot be solved by deduction alone (at least not by the logic I had coded). My method is similar in the way it goes through a list of candidates, but it only guesses when logic has dried up, and it selects the empty cell with the fewest candidates to minimize incorrect explorations. After each guess, it applies logical deduction again as far as possible. My bulky code required for logical deduction (identifying "naked singles" and "hidden singles") makes each loop involve more computation, but the trade off is that it requires fewer loops to reach the solution. For puzzles that can be logically reduced, my code runs faster, but for nasty puzzles, pure-backtracking proved faster (mine took over 3 minutes to solve the hardest puzzle). I also had to restrict the amount of logic coded in, since I hit the 8,192 character limit at one point. I had to scrap my "hidden pair" code. Recursion is so mind-bending I still feel like I don't fully follow what the code is doing! haha. I was just so happy to see someone else wielding Excel in a creative way to tackle the problem I've been obsessed with. Well done, sir! It is tough to find people who, first of all, understand what you're coding and, second of all, care! It can be a lonely hobby.

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