12/23/2023 0 Comments Solving sudoku bit manipulation![]() ![]() Having Keys in our pants pocket satisfies the constraint that our pants should have an item in them, but not the other two constraints. ![]() The question is whether a row satisfies the constraint. You’ll notice I labeled the columns (constraints) as questions. Our list of possible placements of items: keys in pants pocket, keys in coat pocket, keys in backpack, wallet in pants pocket, wallet in coat pocket, wallet in backpack, phone in pants pocket, phone in coat pocket, phone in backpack. Our list of constraints: pants pocket filled, coat pocket filled, backpack filled ![]() To simplify things, let’s consider the original pocket rearrangement problem: The list of constraints become the column headers of a matrix, and the list of ways to satisfy each constraint become rows in that matrix. Well, an exact cover approach would do the following: create a list of constraints that must be satisfied, then create a list of potential ways to satisfy each constraint. How would you go about solving this issue? This is because the number of constraints has grown much larger, as has the number of items that could potentially satisfy those constraints. Now imagine you have a hundred pockets, and three hundred different things that must be placed in them in a certain configuration. You could solve this a variety of ways: keys in pants, phone in coat, wallet in backpack, etc. Have a solution yet? I hope you said yes. One item must go in a pants pocket, one item must go in a coat pocket, and one item must go in a backpack-and no two items can be in the same area. Imagine you are challenged to rearrange where you place your cell phone, keys, and wallet. There exists a type of problem called “ exact cover”, and while Wikipedia explains things ever so well, I’ll throw in my own explanation that should serve well at least in the context of Sudoku. ( Update October 2013: This project is available on GitHub!) Still here? Good, it’s time for me to explain a few things. Long story short: I represented Sudoku as an exact cover problem, then used Donald Knuth’s Algorithm X and Dancing Links implementation to solve that exact cover problem. Thanks to Scott Y’s comments in my article regarding a Sudoku Solver I wrote as part of an AI project, I decided to write a real solver that not only can solve any Sudoku puzzle, but can do it in just a few milliseconds. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |