![]() The addresses of the cells in the boxes are a little more difficult to calculate, so I just used a simple lookup for the first (top left) cell in each box. From those you can easily calculate the addresses of all the cells in the same row (keep adding 1) and column (keep adding 9). Single Candidate Number 3 is the only value possible in cell (5,1). Single Candidate Number 6 is the only value possible in cell (7,1). Number 4 is the only value possible in cell (6,1). The reason for doing this is the identification of the cells in the same row is a simple calculation (the first cell in the row that cell X is in is Math.floor(X/9) * 9 the first cell in the same column is X % 9). Step-by-Step Solution for Friday 30th June Beginner Before Step After First step: Add in all possible valid pencilmarks. This will make it easier (most of the time) for you to figure out which numbers go in the remaining empty spaces. While solving classic Sudoku puzzles vary from easy to a substantial challenge, every puzzle has just one correct solution. I made the cell addresses really simple too: just a number from 0 to 80, counting the columns from left to right across each row and then down the rows (so the top row’s cells are 0 to 8, the second row’s cells are 9 to 17, and so on). One of the best ways to get started with solving a Sudoku puzzle is to look for low-hanging fruit the rows, columns or squares that already have the most numbers filled in. Then all I needed to do when backtracking was to pop off the top cell address and I could easily revisit it to increment its value to the next digit. The way I did it was to have a stack of cell addresses I’d visited and modified. The amount of state can be small or it can be pretty large and in the latter case it can sink your algorithm.Īnyway, for the Sudoku example, the simplistic backtracking algorithm is fairly easy to write. The problem with this algorithm is the same problem as with all backtracking algorithms: you’ve got to save some kind of state as you move forward, so that you can restore it when you need to backtrack. This type of algorithm is known as a depth-first search algorithm: we try to move forward as quickly as possible (increasing the depth to which we advance), backtracking if necessary to try again. Sometimes, as I’m sure you can appreciate, you’ll find that you backtrack several cells, but nevertheless, if the puzzle has a solution, you’ll find it. In the latter case, you must backtrack to the previous cell you filled in and increment the digit you find there and check and move forward again. Repeat this inner loop until either you find a valid digit for that cell and move on as before, or until you run out of digits. If there is a clash though, increment the digit you just added and check again whether it already appears in the same row, column, or box. If it’s valid, find the next empty cell and repeat the algorithm. Check to see whether that digit violates one of the Sudoku rules (that is, check to see whether there is already a 1 in the same row, or column, or box). ![]() If you pose this Sudoku-solving question to a group of developers, I think the initial answer would look something like this. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |