![]() Unique sudoku boards, I call them UBs, number 5,472,730,538 which is reduced from the actual larger number because of rotating and symmetry. ![]() If the DLX algorithm does solve puzzles in milliseconds, then I *think* enumerating all possible 17 clue sudoku puzzles (after removing symmetries / permutations) will be amenable to a distributed approach (a la "", "BOINC", etc etc) : A few thousand volunteers should give you about 150 million CPU hours per year) - I suspect that would make the problem eminently solveable. I'm just coding this up in the next couple of days I'll get back to you if you want. I suspect that using the DLX algorithm to solve the "exact cover" problem (which explicitly represents all possible combinations of constraints and dependencies between them), you should be able to get a reasonable solution in milliseconds, particularly if the implementation takes into account the capabilities of modern hardware. You mention a per solution time of six seconds, I'm assuming this is brute force search of the space, taking the "least branches first" approach to filling the solution tree. So a practical search of this space without using a trick like Avoidable Sets is impossible. Given 22 clues the average time is 0.037 seconds and becomes millisecond or less with 25 clues or more. 17 clue puzzles take on average 6 seconds - although the exact orientation and placement of numbers can make this vary from 0.5 seconds to 30 seconds. Anyone familiar with the solver will know this feature. I have been running some tests on my Solution Count program which shows how the time to check a puzzle using a brute force method becomes exponential with the reduction in the number of clues. Nevertheless, to get a result in a practical time is an achievement. So it is understandable that the computing time was still considerable. ![]() The algorithm must also take into account higher order Avoidable Sets (with nine numbers instead of 4). First you must obtain (or generate) all possible unique filled-in Sudoku boards, of which there are 5,472,730,538. These are sets of four cells which potentially could be interchanged to make two solutions - and therefore, minimally, one of those cells must be a clue.Įven with this insight, it is still a challenging algorithm to run. The author identifies the Unavoidable Sets as the key to reducing the search space. To search through all possible combinations would take an impractical amount of time. What is interesting about the paper is the algorithm to search the space. This is not a mathematical proof as such but a brute force computer search through the number space within the Sudoku set, and the author admits that a mathematical proof is still be discovered. One such set I use for calibrating and testing. There are about 50,000 such puzzles collected from various sources out and about on the Internet. ![]() It has been conjectured for some time that 17 clues is the minimum number of necessary clues to make a single solution Sudoku puzzle. (Note: Nature's article tries to reproduce the 17 Clue example from the paper but they get the 43 in the wrong place, giving an invalid puzzle with 9734 solutions. This has been highlighted in a number of news outlets and scientifc journals (eg Nature). A recent paper by Gary McGuire, Bastian Tugemann, Gilles Civario " There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem" (PDF) shows a new and interesting approach to the problem of the minimum numbers of clues to a normal Sudoku.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |