Sudoku Solver Algorithm
2024 ж. 15 Мам.
1 259 Рет қаралды
CSE 3500 Personal Project
Everything you need to know about how to properly distract yourself in class.
CSE 3500 Personal Project
Everything you need to know about how to properly distract yourself in class.
Very informative
You could improve efficiency by making a budget of each digit. If there are already 9 9s, for example, we don't have to try 9 and then realize that it's an illegal move, we could anticipate that it will be illegal and avoid several steps. I'm not sure if it would be better/worse/no change to prioritize digits with high or low budgets, though. If there are already 8 8s, then we only need to find one and then we can stop checking for it, but most of our checks will be false. Now that I think about it, 8 8s means we actually know where the last one must go, so only 7/9 positions have to be attempted for any given digit. Out of curiosity, what does your code return for a blank board?
Amazing video! It didn’t make sense but I still loved it!
You deserve more subs. Very good vid
Very interesting! I learned how to code in Visual Basic for Applications (VBA) within Microsoft Excel by creating a Sudoku solver for a friend. I did mine a little differently where it never actually guessed so it was possible not to solve the hardest problems. Basically, I created a bunch of mini boxes using the concept of a logic grid but based in regular Excel cells. For each number, if it appeared in the puzzle, the program placed a "O" and then put "X"s in all the squares that now could not contain that number. For each of the rows, columns, and sub-grids, I had a counter to show if only 1 possible placement was available for that number. I then had an overall checker that duplicated the full grid but looked at each of the 9 numbers and counted how many could still be placed in that spot. (For example, if I could place either a 4 or a 5 in a spot, then my count said 2, but if only a 4 fit, then it said 1.) My VBA program then went through these areas and looked for any place where only 1 number was possible. The program would just pick the first one it found that fit the rule, put the associated number in the puzzle, and then recalculated all the helper cells for the puzzle. Then it went back and performed the search again. Thus, it could break and not solve the puzzle if it ever reached a point where a decision had to be made. Because it wasn't guessing, my program usually took only about a minute to solve (and then would re-run about 5 more times cause I was still learning and had some bug that didn't stop it once the game was complete).
You may want to note that it cannot solve the hardest of Sodoku puzzles, as my 100x100 puzzle would take way too long to solve this way. (There are ways to speed up your time complexity to sqrt(2)^n, I believe.)
Takes the fun out of sudoku though. How does the recursive board function work? I don’t really understand it
Hey! it definetly does take the fun out of sudoku, but you get more fun when you learn how to make something new. The recursive function works keeps calling its self until it returns true (3:03) Once it returns true, it exits out of the loop because it completed its job. It only returns true when the board is wholy solved. The nested for loops can be a bit confusing, but heres how it basically works. The first for loop iterates over the 9 rows, while the second for loop iterates over the 9 columns. The next if statement checks if the currect square we are at is empty (e.g. = 0), and if so, it runs the code in it, which is another for loop that iterates from 1 to 9 and checks if they are "valid moves" in that same cell. If its a valid move, it replaces the zero with that number, and checks to see if the board is completed (by calling itself as a function (3:03)). If it calls itself in the if statement and returns true. It exits out of the num for loop, and starts iterating over other cells repeating all of that. Hope that helped!