algorithmsudoku# How to show a sudoku solution is unique?

Given a unsolved sudoku, how can one show that it has a unique solution?

Solution

Try to find two solutions.

The simplest algorithm is a brute force recursive algorithm with backtracking. Once you have found the first solution, backtrack and look for a second. This is slow but (unlike algorithms that rely on logic alone) it is guaranteed to be able to find all the solutions eventually. Therefore if this algorithm terminates having found only one solution then that solution must be unique.

This will work for easy problems but could take hours or days for harder problems. There are many optimizations you can use if you need more speed.

A simple optimization is to keep track of a candidate list for each square. At each step find the square with the fewest candidates. If there is only one candidate, choose that number, update the grid and the candidates for the other squares, then continue. If there are ever zero candidates you know that a guess you made previously was wrong so you should backtrack.

More advanced optimizations involve looking for patterns which allow you to deduce numbers without making guesses. Here are some examples:

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?