The question is published on Februby Tutorial Guruji team.
Today at Tutorial Guruji Official website, we are sharing the answer of Sudoku generator algorithm without wasting too much if your time. This is all predicated on having a decent data model for the sudoku board, so I would focus on that first.Hello Developer, Hope you guys are doing great.
You could then use number of board states checked during each verification step as a measure of difficulty.Īlternatively you could program in some smart solving techniques to supplement the brute force solver, but that certainly creates a lot more complexity. One approach that I THINK would work would be to generate a valid sudoku and then gradually remove digits and verify each intermediate state has a single unique solution. A brute force solver/setter would be extremely slow (9 81 possible board states) and in order to set a puzzle with a unique solution you will need to perform some analysis to verify this. But there are of course shades of complexity here too. Well, these are fairly complex tasks, yes. For example, if you remove a given in cell (x,y) you also remove the given in cell (10 - y, 10 - x). If you want your puzzles to look "nicer" you can also implement symmetries for when you remove givens. If you're just trying to generate a single puzzle (like the user chooses a difficulty and clicks "new puzzle"), then you just keep repeating this process and throwing out the result until you get one that matches the requested difficulty. Save that off along with the "difficulty" metric your logical solver assigns it, and repeat. Keep doing this until there are no givens left that you can remove and still have a solvable puzzle.
Then, remove given numbers at random one at a time and ask your logical solver to solve it. Ok, so you have your logical solver and your generator. I haven't tried this, so I'm not sure how often you end up with an invalid grid vs a valid one. If you don't want to backtrack, it's possible that if you hit a bad empty cell, you just throw it out and start over from scratch.
This previous cell may also run out of valid numbers, and so you need to be able to recursively backtrack all the way to the start, potentially. If at any point you encounter a cell which has no possible values (which will happen), then you recursively backtrack and choose a different value for the previous cell. The way to do this is to start in the top-left and choose a random valid number for each cell going left to right and top to bottom. Now you need a way to generate valid final solutions so that you can work backwards from there. So, now that you have your logical solver that can evaluate whether a puzzle can be solved using a restricted set of techniques and can record down what those techniques are, the next step is to generate puzzles. If you want to go harder, the sky's the limit in terms of what to implement and I recommend referencing HoDoKu's wiki for the various "human-like" strategies that it implements. If you just want to replicate what The New York Times calls "Hard" then you just need naked singles, hidden singles, naked pairs/triples/quadruples, hidden pairs/triples/quadruples, pointing, and claiming. Thus, the input to your generator should also be the desired difficulty level, and the only way to judge difficulty is to make a program that solves like a human would and records down what the most difficult steps were. Some Sudoku grids solve using only singles, while others are not human solvable at all without a huge amount of guessing/backtracking. Having a brute force solver is useful for checking uniqueness, but usually the goal of generating Sudokus is also to target the difficulty of the Sudoku. What I mean by logical solver is one which attempts to replicate human logic. Generating a Sudoku first requires that you create a logical solver.