mopdf.com

Sudoku andMathematicsBacktrack searchMax NeunhöfferIf we cannot conclude another number, then we:SudokusWhat is a Sudoku?1remember the current search situation2concentrate on one place and try a possible number3work under this assumption4if we find a solution, we are done5if we arrive at a contradiction, we backtrack, revertour decision and go to 2. with another possibility.Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemTheoremBacktrack SearchIf there is a unique solution, this method will find it.

Sudoku andMathematicsBacktrack searchMax NeunhöfferIf we cannot conclude another number, then we:SudokusWhat is a Sudoku?1remember the current search situation2concentrate on one place and try a possible number3work under this assumption4if we find a solution, we are done5if we arrive at a contradiction, we backtrack, revertour decision and go to 2. with another possibility.Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemTheoremBacktrack SearchIf there is a unique solution, this method will find it.If there are many solutions, a minor modification lets usfind all of them.

Sudoku andMathematicsBacktrack searchMax NeunhöfferIf we cannot conclude another number, then we:SudokusWhat is a Sudoku?1remember the current search situation2concentrate on one place and try a possible number3work under this assumption4if we find a solution, we are done5if we arrive at a contradiction, we backtrack, revertour decision and go to 2. with another possibility.Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemTheoremBacktrack SearchIf there is a unique solution, this method will find it.If there are many solutions, a minor modification lets usfind all of them. Solving Sudokus is mathematics!

Sudoku andMathematicsMax NeunhöfferSudokusWhat is a Sudoku?Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchHow difficult is a Sudoku puzzle?This depends on how much one has to try.

Sudoku andMathematicsMax NeunhöfferHow difficult is a Sudoku puzzle?This depends on how much one has to try.SudokusWhat is a Sudoku?Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchIf you can conclude the solution all the way through, thenone would consider the puzzle to be relatively easy.

Sudoku andMathematicsMax NeunhöfferHow difficult is a Sudoku puzzle?This depends on how much one has to try.SudokusWhat is a Sudoku?Solving SudokusConclusionsIf you can conclude the solution all the way through, thenone would consider the puzzle to be relatively easy.Backtrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchIf you have to try possibly multiple times, then one wouldconsider the puzzle to be more difficult.

Sudoku andMathematicsMax NeunhöfferHow difficult is a Sudoku puzzle?This depends on how much one has to try.SudokusWhat is a Sudoku?Solving SudokusConclusionsIf you can conclude the solution all the way through, thenone would consider the puzzle to be relatively easy.Backtrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusIf you have to try possibly multiple times, then one wouldconsider the puzzle to be more difficult.Symmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchIt is hard to quantify this, because there are so manydifferent ways to conclude numbers.

Sudoku andMathematicsMax NeunhöfferHow difficult is a Sudoku puzzle?This depends on how much one has to try.SudokusWhat is a Sudoku?Solving SudokusConclusionsIf you can conclude the solution all the way through, thenone would consider the puzzle to be relatively easy.Backtrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusIf you have to try possibly multiple times, then one wouldconsider the puzzle to be more difficult.Symmetry BreakingOpen problems16 CluesHow many clues?It is hard to quantify this, because there are so manydifferent ways to conclude numbers.Unavoidable SetsThe Hitting Set ProblemBacktrack SearchA computer solves this in 28µs 45000 clock cycles!

Sudoku andMathematicsMax NeunhöfferHow difficult is a Sudoku puzzle?This depends on how much one has to try.SudokusWhat is a Sudoku?Solving SudokusConclusionsIf you can conclude the solution all the way through, thenone would consider the puzzle to be relatively easy.Backtrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusIf you have to try possibly multiple times, then one wouldconsider the puzzle to be more difficult.Symmetry BreakingOpen problems16 CluesHow many clues?It is hard to quantify this, because there are so manydifferent ways to conclude numbers.Unavoidable SetsThe Hitting Set ProblemBacktrack SearchA computer solves this in 28µs 45000 clock cycles! Solving Sudokus is not a difficult problem in CompSci.

Sudoku andMathematicsMax NeunhöfferHow difficult is a Sudoku puzzle?This depends on how much one has to try.SudokusWhat is a Sudoku?Solving SudokusConclusionsIf you can conclude the solution all the way through, thenone would consider the puzzle to be relatively easy.Backtrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusIf you have to try possibly multiple times, then one wouldconsider the puzzle to be more difficult.Symmetry BreakingOpen problems16 CluesHow many clues?It is hard to quantify this, because there are so manydifferent ways to conclude numbers.Unavoidable SetsThe Hitting Set ProblemBacktrack SearchA computer solves this in 28µs 45000 clock cycles! Solving Sudokus is not a difficult problem in CompSci.There is a whole branch of CompSci/Maths calledConstraint Satisfaction: deals with very hard problemssimilar to Solving Sudokus

Sudoku andMathematicsHow many Sudoku grids are there?Max NeunhöfferSudokusWhat is a Sudoku?Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchA full Sudoku grid is a latin square: every symbol 1 to 9occurs in every row and every column exactly once.

Sudoku andMathematicsHow many Sudoku grids are there?Max NeunhöfferSudokusWhat is a Sudoku?A full Sudoku grid is a latin square: every symbol 1 to 9occurs in every row and every column exactly once.Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Number of 9 9 latin squaresThere are altogetherEquivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack Search5 524 751 496 156 892 842 531 225 600 5.525 · 1027latin squares of size 9 9.

Sudoku andMathematicsHow many Sudoku grids are there?Max NeunhöfferSudokusWhat is a Sudoku?A full Sudoku grid is a latin square: every symbol 1 to 9occurs in every row and every column exactly once.Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Number of 9 9 latin squaresThere are altogetherEquivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?5 524 751 496 156 892 842 531 225 600 5.525 · 1027latin squares of size 9 9.Unavoidable SetsThe Hitting Set ProblemBacktrack SearchSudokus fulfill additional conditions, so there are fewer.

Sudoku andMathematicsHow many Sudoku grids are there?Max NeunhöfferSudokusWhat is a Sudoku?A full Sudoku grid is a latin square: every symbol 1 to 9occurs in every row and every column exactly once.Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Number of 9 9 latin squaresThere are altogetherEquivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?5 524 751 496 156 892 842 531 225 600 5.525 · 1027latin squares of size 9 9.Unavoidable SetsThe Hitting Set ProblemBacktrack SearchSudokus fulfill additional conditions, so there are fewer.How could one possibly count these?

Sudoku andMathematicsHow many Sudoku grids are there?Max NeunhöfferSudokusWhat is a Sudoku?A full Sudoku grid is a latin square: every symbol 1 to 9occurs in every row and every column exactly once.Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Number of 9 9 latin squaresThere are altogetherEquivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?5 524 751 496 156 892 842 531 225 600 5.525 · 1027latin squares of size 9 9.Unavoidable SetsThe Hitting Set ProblemBacktrack SearchSudokus fulfill additional conditions, so there are fewer.How could one possibly count these?Not by brute force: If our computer enumerates one ineach clock cycle, it would need 90000 years to finish!

Sudoku andMathematicsMax NeunhöfferSudokusCounting full Sudoku gridsConsider only the first block row:1We can renumber to get this left hand 3 3-block:What is a Sudoku?Solving SudokusConclusionsBacktrack searchSudoku difficulty1 2 3 ? ? ? ? ? ?4 5 6 ? ? ? ? ? ?7 8 9 ? ? ? ? ? ?SymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchCount those, multiply by 9! 362880 in the end.

Sudoku andMathematicsMax NeunhöfferSudokusCounting full Sudoku gridsConsider only the first block row:1We can renumber to get this left hand 3 3-block:What is a Sudoku?1 2 3 ? ? ? ? ? ?4 5 6 ? ? ? ? ? ?7 8 9 ? ? ? ? ? ?Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack Search2Count those, multiply by 9! 362880 in the end.Distinguish more cases and identify different cases,which have the same number of completions.

Sudoku andMathematicsMax NeunhöfferSudokusCounting full Sudoku gridsConsider only the first block row:1We can renumber to get this left hand 3 3-block:What is a Sudoku?1 2 3 ? ? ? ? ? ?4 5 6 ? ? ? ? ? ?7 8 9 ? ? ? ? ? ?Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry Breaking2Open problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack Search3Count those, multiply by 9! 362880 in the end.Distinguish more cases and identify different cases,which have the same number of completions.Finally, run a (backtrack) computer search for eachcase to count the possibilities.

Sudoku andMathematicsMax NeunhöfferSudokusCounting full Sudoku gridsConsider only the first block row:1We can renumber to get this left hand 3 3-block:What is a Sudoku?1 2 3 ? ? ? ? ? ?4 5 6 ? ? ? ? ? ?7 8 9 ? ? ? ? ? ?Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry Breaking2Open problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack Search3Count those, multiply by 9! 362880 in the end.Distinguish more cases and identify different cases,which have the same number of completions.Finally, run a (backtrack) computer search for eachcase to count the possibilities.The answerThere are altogether6 670 903 752 021 072 936 960 6.671 · 1021different full Sudoku grids. (Felgenhauer/Jarvis 2006)http://www.afjarvis.staff.shef.ac.uk/sudoku/

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusWhat is a Sudoku?Solving Sudokus7 9 36 8 45 14 85 1 29 3 762Conclusions1 2 59 7 38 4 6Backtrack search93 276 8 457 82 4633 987 2Sudoku difficultySymmetry6 415 19 15How many grids?Equivalent SudokusSymmetry BreakingOpen problems3 1 9 4 6 58 5 7 1 2 922 6 418 3 716 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchEquivalence transformations:7 84 6 35 9

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusWhat is a Sudoku?Solving Sudokus7 9 36 8 45 14 85 1 29 3 762Conclusions1 2 59 7 38 4 6Backtrack search93 276 8 457 82 4633 987 2Sudoku difficultySymmetry6 415 19 15How many grids?Equivalent SudokusSymmetry BreakingOpen problems3 1 9 4 6 58 5 7 1 2 922 6 418 3 716 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemEquivalence transformations:Backtrack SearchPermute: rows in a block,7 84 6 35 9

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusWhat is a Sudoku?Solving Sudokus7 9 36 8 45 14 85 1 29 3 762Conclusions1 2 59 7 38 4 6Backtrack search93 276 8 457 82 4633 987 2Sudoku difficultySymmetry6 415 19 15How many grids?Equivalent SudokusSymmetry BreakingOpen problems3 1 9 4 6 58 5 7 1 2 922 6 418 3 77 84 6 35 916 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemEquivalence transformations:Backtrack SearchPermute: rows in a block, columns in a block,

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusWhat is a Sudoku?Solving Sudokus7 9 36 8 45 14 85 1 29 3 762Conclusions1 2 59 7 38 4 6Backtrack search93 276 8 457 82 4633 987 2Sudoku difficultySymmetry6 415 19 15How many grids?Equivalent SudokusSymmetry BreakingOpen problems3 1 9 4 6 58 5 7 1 2 922 6 418 3 77 84 6 35 916 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemEquivalence transformations:Backtrack SearchPermute: rows in a block, columns in a block,block-rows,

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusWhat is a Sudoku?Solving Sudokus7 9 36 8 45 14 85 1 29 3 762Conclusions1 2 59 7 38 4 6Backtrack search93 276 8 457 82 4633 987 2Sudoku difficultySymmetry6 415 19 15How many grids?Equivalent SudokusSymmetry BreakingOpen problems3 1 9 4 6 58 5 7 1 2 922 6 418 3 77 84 6 35 916 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemEquivalence transformations:Backtrack SearchPermute: rows in a block, columns in a block,block-rows, block-columns

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusWhat is a Sudoku?Solving Sudokus7 9 36 8 45 14 85 1 29 3 762Conclusions1 2 59 7 38 4 6Backtrack search93 276 8 457 82 4633 987 2Sudoku difficultySymmetry6 415 19 15How many grids?Equivalent SudokusSymmetry BreakingOpen problems3 1 9 4 6 58 5 7 1 2 922 6 418 3 77 84 6 35 916 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemEquivalence transformations:Backtrack SearchPermute: rows in a block, columns in a block,block-rows, block-columnsRenumber: entries

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusWhat is a Sudoku?Solving Sudokus7 9 36 8 45 14 85 1 29 3 762Conclusions1 2 59 7 38 4 6Backtrack search93 276 8 457 82 4633 987 2Sudoku difficultySymmetry6 415 19 15How many grids?Equivalent SudokusSymmetry BreakingOpen problems3 1 9 4 6 58 5 7 1 2 922 6 418 3 77 84 6 35 916 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemEquivalence transformations:Backtrack SearchPermute: rows in a block, columns in a block,block-rows, block-columnsRenumber: entriesFlip: entire grid

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusWhat is a Sudoku?Solving Sudokus7 9 36 8 45 14 85 1 29 3 762Conclusions1 2 59 7 38 4 6Backtrack search93 276 8 457 82 4633 987 2Sudoku difficultySymmetry6 415 19 15How many grids?Equivalent SudokusSymmetry BreakingOpen problems3 1 9 4 6 58 5 7 1 2 922 6 418 3 77 84 6 35 916 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemEquivalence transformations:Backtrack SearchPermute: rows in a block, columns in a block,block-rows, block-columnsRenumber: entriesFlip: entire grid All concatenations of these form a group.

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusDefinition: Equivalent SudokusWhat is a Sudoku?Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchTwo Sudoku grids/puzzles are called equivalent if onearises from the other by applying a sequence ofequivalence transformations.

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusDefinition: Equivalent SudokusWhat is a Sudoku?Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchTwo Sudoku grids/puzzles are called equivalent if onearises from the other by applying a sequence ofequivalence transformations.

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusDefinition: Equivalent SudokusWhat is a Sudoku?Solving SudokusConclusionsBacktrack searchSudoku difficultyTwo Sudoku grids/puzzles are called equivalent if onearises from the other by applying a sequence ofequivalence transformations.SymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchWe form equivalence classes or orbits.

Sudoku andMathematicsEquivalence of SudokusMax NeunhöfferSudokusDefinition: Equivalent SudokusWhat is a Sudoku?Solving SudokusConclusionsBacktrack searchSudoku difficultyTwo Sudoku grids/puzzles are called equivalent if onearises from the other by applying a sequence ofequivalence transformations.SymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchWe form equivalence classes or orbits. There are 5 472 730 538 classes (Jarvis/Russell 2006)http://www.afjarvis.staff.shef.ac.uk/sudoku/

Sudoku andMathematicsMax NeunhöfferSudokusWhat is a Sudoku?Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack SearchSymmetry BreakingWe “break the symmetry” by considering exactly one fromeach equivalence class.

Sudoku andMathematicsMax NeunhöfferSudokusWhat is a Sudoku?Symmetry BreakingWe “break the symmetry” by considering exactly one fromeach equivalence class. Consider only the first block row:1We can renumber to get this left hand 3 3-block:Solving SudokusConclusionsBacktrack searchSudoku difficultySymmetryHow many grids?Equivalent SudokusSymmetry BreakingOpen problems16 CluesHow many clues?Unavoidable SetsThe Hitting Set ProblemBacktrack Search1 2 3 4 6 8 9 5 74 5 6 9 1 7 8 3 27 8 9 3 5 2 1 4 6

Sudoku andMathematicsMax NeunhöfferSudokusWhat is a Sudoku?Symmetry BreakingWe “break the symmetry” by considering exactly one fromeach equivalence class. Consider only the first block row:1We can renumber to get this left hand 3 3-block:Solving Sudokus1 2 3 4 6 8 9 5 74 5 6 9 1 7 8 3 27 8 9 3 5 2 1 4 6ConclusionsBacktrack searchSudok

Sudoku and Mathematics Max Neunhöffer University of St Andrews Edinburgh 21 January 2011. Sudoku and Mathematics Max Neunhöffer Sudokus What is a Sudoku? Solving Sudokus Conclusions Backtrack search Sudoku difficulty Symmetry How many grids? Eq