12/24/2023 0 Comments Solving sudoku bit manipulation(See also Wikipedia for a similar solution.) This backtracking lets the code finish within the allotted time and ensures that once the grid is completed, the solution is valid. If every digit has conflicts, the algorithm backtracks to a previous cell and tries a different digit there. For each cell, the algorithm checks each digit for conflicts with the relevant cells until a digit fits. This means that each digit has to be unique among those 3 areas, there can be no “conflict” between it and an identical digit in its “zones”.Ĭonstantin’s solution involved a brute-force/backtracking algorithm which fills in digits in each cell until it is able to complete the grid. The goal of the game is to fill in a grid with digits so that every column, row, and 3×3 sub-grid contains all 9 digits. There were two components to solving the problem: First to find a working solution in regular (but short) code, and then to work on minifying it to make it much shorter.īefore discussing the algorithm, I’ll quickly review the rules of sudoku. He chose to code in C++ since he was familiar with it and so he could make use of its macros. Constantin submitted his solution in at 6am and made it to the top 10 in the contest, even with C++ code. Initially, he thought he would go to bed rather than solving the problem, but he found the challenge so interesting he ended up coding away the night. This post will discuss a couple of different approaches to the problem in different languages.Ĭonstantin Dumitrascu lives in Romania, where the codesprint contest ran from 9pm to 9am. The winners were asked if they could share their code and approach with others, and many graciously agreed. The top Hackathon hackers from each school won an all-expenses paid trip to San Francisco to hack with other students. In short, it was another Code Golf Contest. Instead of trying to create a solver with an optimal run-time, the goal was to create one with the shortest possible source code that could still solve the problem within the given amount of time. The challenge was: To create a Sudoku solver that could print a solution to any randomly-generated 9×9 Sudoku problem. Recently we had a CodeSprint for the public and a Hacker Olympics for college students. We run regular coding competitions at HackerRank.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |