1/1/2024 0 Comments Sudoku games hard![]() # we didn't find any solution given the current board status # return False to notify upper recursive solve_helper that # if we are here, it means we have tried all values in this cell without finding a solution # then clear cell to return the board to the status before x was filled # so we can skip further processing if 2 solutions have been found # the problem requires us raise error if there are more than one solution, # then try to solve from the next cell k+1, # fill the cell with value x only if x has not appeared on the same row or col or 3x3 box # try to fill each value from 1 to 9 in this cell # if this cell has been filled, go on to solve the next cell # return True to notify that we have found a solution # if we get pass the last cell, it means we have filled every cells with valid values. # k is the cell index, counting from left to right and top to bottom. # given the sudoku has been filled up to cell k-1, try to solve the sudoku from cell k # recursively solve the sudoku, starting from cell 0 # init a blank board with all cells filled with zero The sample code goes as below: import copy The first thing that we want to try is of course reusing the solution from the last challenge, with some modifications to fit the new additional requirements. The hardest test that we are going to solve is the puzzle below, which has only 17 given numbers: # Should solve very hard puzzleĪssert(sudoku_solver(puzzle) = solution) The backtracking approach The good news is, we can return an error early immediately when we found the second solution. Therefore, instead of return the first solution we found, we have to keep testing other possibilities to make sure that there are no other solution to the sudoku. Or it should raise an error in cases of: invalid grid (not 9×9, cell with values not in the range 1~9) multiple solutions for the same puzzle or the puzzle is unsolvable.Ĭompared to the problem in part 1, this problem requires us to raise an error if there are more than one solution to the sudoku. The function will take a sudoku grid and it should return a 9×9 array with the proper answer for the puzzle. Write a function that solves sudoku puzzles of any difficulty. ![]() A very hard will have several layers of multiple candidates for any empty cell. Note: The minimum of givens required to create a unique (with no multiple solutions) sudoku game is 17.Ī hard sudoku game means that at start no cell will have a single candidates and thus require guessing and trial and error. ![]() Very Hard sudoku have less than 28 givens.Easy sudoku generally have over 32 givens.There are several difficulty of sudoku games, we can estimate the difficulty of a sudoku game based on how many cells are given of the 81 cells of the game. It is recommended that you try to practice on your own first before going on to read the solution. This time, we are going to find a better solution so that we can pass the tests in the new challenge within the 10-second time limit. While the algorithm did the job, it couln’t beat the time limit in the more advanced challenge: Hard Sudoku Solver 1. In part 1, we have solved some hard sudoku puzzles using the backtracking approach. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |