How to Fill a Sudoku Grid
How do you actually go about filling a sudoku puzzle grid? This is a question we get asked from time to time, either by budding puzzle writers, those wanting to create a one-off puzzle, or, no doubt in some cases, those who have been tasked with creating a sudoku puzzle as a task as part of a programming course they are taking.
Filling the sudoku grid is fairly straightforward, and there are several different methods that can be used for doing this. Once you have a filled grid then going on to make a fair, valid and accurately graded puzzle is a lot harder. In this text and video discussion, we stick purely to how to perform the former task: filling the grid.
We can define the task as follows: create an algorithm that results in a 9x9 grid that is filled in such a way that the numbers from 1-9 appear once in each row, column and 3x3 box that compose the grid. Of course, other grid sizes exist, but 9x9 is by far the most common. And, in any case, the parameters plugged into the algorithm can be easily changed to reflect other grid sizes as required.
The video below walks through a simple and powerful algorithm that will do just this for you - quickly fill sudoku grids:
There are of course other ways to try and fill a grid. You can still fill standard 9x9 grids with an algorithm that doesn't backtrack at all, for instance by simply stopping each time you reach a point where there are no givens available for a certain square, and starting again from scratch. This will be quick enough to still fill grids in a reasonable time frame. However, the more constraints you add, the harder this gets: for instance if you add a diagonal constraint (sudoku X) then this approach can pretty much grid to a halt, so for maximum flexibility some form of backtracking is usually required to fill grids in a reasonable timeframe, as outlined in the video above.
Another method you can use to increase the chances of each attempt at a fill being successful is to actually implement solve rules that you'd use as a human when trying to tackle a puzzle, and try to make as much progress at each stage of the solve as you can. Whereas the video simply picks a square with the least options at each stage of the solve based on scanning the regions, you could implement solve rules to note that, for instance, where you have 45 as the only options for two squares in a region then none of the other squares in the region can contain either 4 or 5 so there is no point in trying them for those squares as a naive algorithm might do. Or, more simply, just write some code to observe if 9 is a candidate, say, for just one square in a region, then your program would know that square must be the 9 so even if it has several other candidates there is no need to try any of those options, and just go straight to the 9.
By thinking up, and experimenting with, different ways of trying to fill a grid, then you'll find a balance that works for you. Some methods may be more likely to lead to a grid fill but are actually slower overall than simpler methods, whilst some extremely quick and simple methods may have a low success rate. And, of course, there can be many ways of implementing the same algorithm, so the way you go about actually coding your chosen algorithm in the programming language of your choice will also have a big impact on the speed of fill.
Overall, you will probably find the algorithm outlined in the video strikes a good balance between simplicity of coding and speed at grid-filling. However if you use a different method to fill your sudoku grids then please do feel free to discuss in the comments below - it's always interesting to hear different methodologies for filling grids! So scroll to the bottom of the page and fill in the comments box if you'd like to share your own thoughts or experiences on filling sudoku grids.
Date written: 30 May 2020
Category: sudoku | Keywords: sudoku | programming | algorithms
Puzzle Videos: Learn to Solve
How to solve Skeleton Crosswords
Skeleton crosswords are intriguing but difficult puzzles - if you'd like to have a go but aren't sure how to get started then this video could prove interesting.
Would you like to have a go at solving the puzzle? You can do so here: Online Skeleton Crossword Puzzle
Read about other Puzzles
- Hints and Tips on Solving Cryptogram Puzzles
- Sudoku Variants: How Many Are There?
- Hard Codeword Puzzles
- Sandwich Sudoku Puzzles
- The i Book of Codewords
Comment on this blog post
If you would like to comment on this post, please enter your comments below; all fields are mandatory. Posts are moderated before display.
Back to World of Puzzles