Today’s author, Charlie Ellis, a Program Manager on the Excel team, shares a spreadsheet he built in Excel for solving Sudoku puzzles. The spreadsheet can be found in the attachments at the bottom of this post.For those of you who don’t already know, Sudoku is a type of logic puzzle (that I was completely addicted to about three years ago) that requires you to place the numbers 1-9 into a grid obeying certain rules.A while back, a fellow PM on the Excel team, Dan Cory, wrote a spreadsheet for solving Sudoku puzzles using Excel formulas and made it available on Office Online.
Dan’s spreadsheet was great in that, unlike many of the Sudoku solving spreadsheets out there, it didn’t use any VBA or other scripting to do the work of solving the puzzles, and relied instead on the iterative calculation feature of Excel. It’s quite cool and has been a popular download, but one thing about the spreadsheet that I wanted to see if I couldn’t improve upon was just how complicated it is. In fact, Dan made every single cell its own different formula, and he ended up having to use VBA to create the formulas because maintaining and debugging it without VBA to write all those different formulas in an automated way was impossible.As soon as I saw Dan’s spreadsheet, I wanted to make my own version of a Sudoku solver that not only used only formulas, but also one where the formulas were relatively understandable and there were a small number of distinct formulas. It turned out to not be that tough to build, but I think I learned a fair amount trying different approaches to the problems of making an iterative model like this one perform well and at the same time be reasonably maintainable and understandable. I think it might even have turned up a reasonably useful way at looking at abstraction within formulas given the Excel formula language. I’ve always wanted to blog about the process of creating this spreadsheet and about how iterative formulas work to show the power of Excel’s formula language, because it illustrates the usefulness of circular references and iterative calculation, and because I just think it’s an incredible amount of fun so here goes. Lots of people have created more powerful solvers, many as spreadsheets, some using just formulas, but I wanted to try to explain how you can go about creating a solver and hopefully share some formula tricks that people find useful.Pre-reqsCreating a spreadsheet for solving a Sudoku isn’t entry-level spreadsheeting.
In addition to being pretty good with formulas, you’ll need to understand the concept of iteration. Chris Rae did a great job of explaining the topic in his earlier post on, so I’m not going to repeat that, and I’ll simply assume you already understand iteration.
Killer Sudoku cage combination reference Below are all possible combinations of numbers that can be placed in a Killer Sudoku cage, given the cage size and the cage total. This will help you to quickly note all possibilities for any given cage when solving a Killer Sudoku puzzle.
Second, we’re going to make extremely heavy use of named ranges, and for the stuff I’m doing, the new name manager is very helpful (see for some information about this) and I’m going to assume working knowledge of it and of named ranges generally (though I’m going to show some tricks which may be new to even experienced formula users). Finally, you’ll need to at least be familiar with array notation in Excel.Setting up the boardsFor those I haven’t lost already, I’m going to start by creating a series of boards very much like the ones that Dan Cory used: one 9×9 board for my input, one 9×9 board for the solution, and a 27×27 board for the possible values in each box. I do this by changing the row height, column width, font, and zoom such that all the cells are small squares and then applying borders and fills to get the following:The input and solution boards are reasonably straightforward (the input board is the one in the top left where you’ll type in a puzzle to be solved, the solution board is where the correct answer hopefully shows up).
The board with possible values, which I’ll call the valid values board, is a bit trickier. It is 27×27 because each box in the input and solution boards is represented by a 3×3 set of cells in the valid values board. Each of these nine cells represents whether one of the numbers 1-9 is still in the running to be the actual value for the corresponding box of the solution board and the set of possible values for a given cell in the input/solution cell is the set of all the numbers in a single 3×3 “big cell” that are not blank. If it isn’t already, the purpose/use of this board should become clear later.
For now, let’s fill in all the possible values from one to nine in each of these big cells.Filling in the valid value boardWe want to do this by creating a single formula that will fill in the various numbers 1-9 based on which row and column the formula sits in, and then we’ll later add logic to blank out the numbers that aren’t valid. This formula is a little more complicated than the average spreadsheet formula, so I’ll first give the whole formula and then break it down. This looks like the following:= MOD(COLUMN(A1)-1,3) + 1 + MOD(ROW(A1)-1,3).3When this is entered into the top-left cell of the valid values board and then filled into the entire valid values board, it gives the following results:Note that you’ll want to do the filling in with either Paste Special Formulas or CTRL-Enter because otherwise you’ll mess up all the pretty formatting.Breaking this formula down, ROW and COLUMN return (duh) the row or column of the reference passed to them as a number. Passing these functions A1, as in this formula, means they’ll give us a number that starts at one and goes up. The first part of the formula uses the modulus function to transform the column numbers given by COLUMN into the numbers 0-2, and then adds one to get 1-3. To this we add a 0, 3, or 6, depending on the row number by using the modulo function on the result of the ROW function.Next, because that’s a bit of a gnarly formula to have sitting around, and we’re going to have to use it all over the place, we’re going to take this formula and move it out of the cell and into a named range.
This allows us to abstract away all of the logic for this formula into a single, understandable name. For lack of a better name, I’m going to call it “onetonine” and it will have the same exact formula we just created. Because the context for the relative references (i.e.
What they take as being the current cell) is determined by what cell you’re in when you create the named range, it’s critical that you start off by selecting cell A1, then create the new named range, so that your formula works everywhere within the sheet.This is also why we allow gutters of three rows and three columns around all the boards.Now we can take our new name and test it out in the board, like so:Here CTRL+Enter is by far the easiest way to set the formula for all the cells in the valid values board. First select the whole board, then type in the formula, and instead of pressing Enter, just hit CTRL+Enter to fill the formula you just typed into all the cells (without messing up their formatting).Setting up the solution boardWe’re going to want to base what valid values are left for a given box on what our current solution looks like (as opposed to the input), but in order to do that, we need something in the solution board. To begin with, at least, the solution will definitely contain all of the numbers in boxes from the input board. Let’s start off by doing this in the simplest possible way, while catching the case of blanks. In the solution board, let’s make the cells there all simply equal the corresponding cell in the input board using relative references unless the input cell is blank. The absolute easiest way to do this is with the following formula (shown in the form in which it would be entered into cell D16):=IF(D4,D4,””)Again, use CTRL+Enter to fill this into the appropriate cells.
Now that we have the base thing working, let’s make it more re-usable and meaningful by using named ranges.As we did with the name onetonine, let’s abstract the concept of referring to the correct input cell from any cell in the solution board and turn that into a name. We’ll need to do something similar for all the boards at some point, so we’ll start by making named ranges for each of the boards (I chose inboard, solboard, and valboard) and then a name to go from the solution board to the input board ( incellfromsol) which is simply =Main!D4, then use this to change the formula to be =IF(incellfromsol, incellfromsol, “”). Note that this needs to be input from D16.OK, so far we just made our formula longer, but trust me, this concept becomes a life saver. Doing the same for valid value cells from solution board cells is only a bit trickier.
The name solcellfromval is:=INDEX(solboard, INT((ROW(Main!A1)-1)/3)+1, INT((COLUMN(Main!A1)-1)/3)+1)This must be created from cell P4. This formula uses ROW and COLUMN together with the division operator and INT to convert from the coordinates of the current cell in the 27×27 board to their coordinates in a 9×9 board, then uses INDEX to get the cell out of the solboard corresponding to those coordinates.A neat way of testing this formula is to click into the “Refers to” box of the name manager from different cells in the valid values board. Depending on what cell you’re in you’ll see “dancing ants” (a moving highlight) for a different cell – hopefully the corresponding cell in the solution board.Now that we have some basics, let’s put in an actual puzzle and see about getting the inputs to propagate to the solution board and the valid value board. Here’s the puzzle we’ll use:After entering it, the solution board should look like the input board.
.PLEASE FULLY READ THE SIDE-BAR BEFORE SUBMITTING A POST! SUBMISSION GUIDELINESFAQPROBLEM SOLVED?OPs can reply to any solutions with:This will award the user a and change the flair to SOLVED.
TO APPLY CODE FORMATTING Use 4 spaces to start each lineYou can select code in your VBA window, press Tab, then copy and paste into your thread or comment. PROVIDE YOUR DATA!Include a or use the website to generate the reddit table markup from your spreadsheet. Recent ClippyPoint Milestones!Congratulations and thank you to these contributors DateUserCP10300A community since March 11, 2009 Download the official to convert Excel cells into a table on reddit using.