We will start filling the grid with those “single candidates”. Once we have generated the candidates for each case, we will see that some of them can be filled by only a single candidate. That means any of the digits in the list. ,, ,, ,, ,, ]]įor instance, the case at the 3th row ( i = 2) and the 1st column ( j = 0) could be filled with any of the digits candidates. This function returns the following candidates for our current puzzle: > candidates = get_candidates(grid) We made use of the helper function subgrid_index that returns the corresponding sub-grid index for the i and j indices of the grid’s case. The candidates are implemented as nested lists. If you aren’t familiar with them, you can see a worked example here. We have used Python set’s operations to handle the candidates. # If the case is filled take its value as the only candidate The following function implements this idea: def get_candidates(grid): We will call that set of options “candidates”. ![]() That means that each case can be filled with digits that don’t appear in the case’s row, column and sub-grid. We know that each digit can occur only once for each row, column and sub-grid. See that we’re dividing the original grid into groups of 3×3 sub-grids from left to right, top to bottom. This will return the following sub-grids for our original puzzle: > subgrids = get_subgrids(grid) We can group the values of each 3×3 sub-grid as follows: def get_subgrids(grid): Part of the analysis has to do with checking the values of each sub-grid. Which will return the grid as expected: > grid = create_grid(puzzle) We can populate the 9×9 Sudoku grid with the following function: def create_grid(puzzle_str): As an example, we will work with: puzzle = """043080250 That means we will have 9 lines of 9 digits each. Empty cases will be denoted by 0 and each line of the string will represent a row of the grid. Using Numpy for the gridįor the 9×9 grid, we will use Numpy arrays (the experience I got using Numpy to implement a tic-tac-toe board came in handy here). The goal is to fill the grid’s empty cases, having each digit between 1-9 appear only once in each row, column and 3×3 sub-grid. The grid is also divided into nine 3×3 sub-grids. If you’re not familiar with it, Sudoku is a mathematical puzzle where you have a 9×9 grid partially filled with digits from 1 to 9. Setting up the Sudoku grid Sudoku: What is it? For a more efficient solution based on this one, see here. It will take too long to solve difficult Sudoku puzzles. Note: This solver is a simplified implementation. In this post we will see how to implement a simple version of the solver. After much work, I was finally able to program a solver that recursively tried filling the empty cases and tracked back when necessary. The meat of the problem was implementing a Sudoku solver.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |