![]() means it struggles to compare with the fastest solvers of the day. It's lack of more complex solving techniques hidden singles, naked pairs etc. It tries to guess the square with the fewest candidates. It can solve up to 2 million sudokus per second! Otherwise, it must guess a square and backtrack if it reaches a contradiction. If those rules are enough to solve the puzzle - it's extremely fast. When a digit is placed in a cell two things happen - its value is removed as a candidate from row/column/box, then sum constraints containing the cell are updated and the resulting new mask is reapplied to the remaining squares. The calculation of these constraints is done quickly and lazily with some dynamic programming tricks - i.e. This can be used to quickly mask squares. ![]() If a constraint required us to make 8 in 3 squares there are only two ways to do it: and … And is similarly stored as a mask: \(000011111\) - corresponding to all numbers that could make up a solution. Sums constraints are calculated and cached in a hashset. ![]() When a number is placed in a square it can be removed as a candidate from row/column/box efficiently using binary digits. If were candidates for a square this is stored as \(000010101\) - where the least significant digit corresponding to 1 being a candidate etc. It uses bitsets to improve performance, where possibilities for each cell are stored as a single binary number. The solver's been a learning exercise for rust and as such - the code isn't excellent. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |