![]() ![]() I cross-reference the solutions against a list of known solutions that have been published online. Once the macro has generated solutions for all 1,000 puzzles, I want to ensure that these solutions are correct. I will dive deeper into this section in a few moments. This macro is where I keep the “secret sauce” – the algorithm that actually solves Sudoku puzzles. The “macro” is actually an entire workflow hidden inside one tool. This includes an Input tool that reads a CSV file containing 1,000 randomly selected Sudoku puzzles and a Select tool that allows me to clean my data before using it in the rest of the workflow. This workflow has four main parts, each consisting of multiple tools: A software tool that I enjoy using – Alteryx – is really useful for automating “analytic processes” such as this.īut wait! How can a Sudoku puzzle be solved with an “ analytic process ”? So, I decided to make a robot that can follow the same thought process that I was using but hopefully solve the puzzles a lot faster and without manual effort. My brain was having fun, but my writing hand was getting sore. This tedious manual effort can cause an infraction to Rule 3: “Have fun!”Īfter playing Sudoku many times myself, I realized that I was using the same patterns, again and again, to find the solutions to these puzzles. Sometimes, these strategies can be very repetitive and require a lot of manual effort to execute (the game is typically played on paper with a pencil). ![]() While the game itself can be challenging and complex, several strategies can be used successfully to find the solution. For very hard puzzles, that number can be much higher. It is believed that the average Sudoku player spends approximately 20 minutes solving a typical Sudoku puzzle. Text(B(ii,2)-0.5,9.It seems simple, right? Wrong! It can be incredibly challenging to solve a Sudoku puzzle. % If B is a 9-by-9 matrix, convert it to 3 columns first % we subtract 0.5 to center the clue in the box. % boxes, j is the horizontal distance, 10-i is the vertical distance, and % the top, j is the column, and k is the clue. % The rows of B are of the form (i,j,k) where i is the row counting from Rectangle('Position','LineWidth',1) % minor vertical lines Rectangle('Position','LineWidth',1) % minor horizontal lines Rectangle('Position','LineWidth',2) % heavy horizontal lines Rectangle('Position','LineWidth',2) % heavy vertical lines Rectangle('Position','LineWidth',3,'Clipping','off') % outside border ![]() In other words, for every i and j,įigure hold on axis off axis equal % prepare to draw What properties does x have? First, each square in the 2-D grid (i,j) has exactly one value, so there is exactly one nonzero element among the 3-D array entries x ( i, j, 1 ). Suppose a solution x is represented in a 9-by-9-by-9 binary array. Express the Rules for Sudoku as Constraints However, for tie breaking in the internals of the integer programming solver, giving increased solution speed, use a nonconstant objective function. The problem is really just to find a feasible solution, meaning one that satisfies all the constraints. The objective function is not needed here, and might as well be a constant term 0. This formulation is precisely suited for binary integer programming. The ninth layer has a 1 wherever the solution or clue has a 9. The second layer has a 1 wherever the solution or clue has a 2. The top grid, a square layer of the array, has a 1 wherever the solution or clue has a 1. Think of the cubic array as being 9 square grids stacked on top of each other, where each layer corresponds to an integer from 1 through 9. The key idea is to transform a puzzle from a square 9-by-9 grid to a cubic 9-by-9-by-9 array of binary values (0 or 1). Just express the rules of Sudoku, express the clues as constraints on the solution, and then MATLAB produces the solution. This approach is particularly simple because you do not give a solution algorithm. This example shows a straightforward approach using binary integer programming. ![]() There are many approaches to solving Sudoku puzzles manually, as well as many programmatic approaches. This puzzle, and an alternative MATLAB® solution technique, was featured in Cleve's Corner in 2009. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |