Problem 2085. Sudoku Solver - Standard 9x9

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Solve a Standard 9x9</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Sudoku\"><w:r><w:t>Sudoku</w:t></w:r></w:hyperlink><w:r><w:t>. Values 1 thru 9 occur in each row, column, and the nine non-overlapping 3x3 matrices starting at the top left corner.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.free-sudoku.com/sudoku.php?dchoix=evil\"><w:r><w:t>Sudoku practice site</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> m, a 9x9 matrix of values 0 thru 9. Unknowns are 0s.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> mout, a 9x9 matrix of values 1 thru 9 that satisfy Sudoku rules.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Scoring:</w:t></w:r><w:r><w:t> Time (msec) to solve the Hard Sudoku</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[m mout\n390701506 398721546\n042890701 542896731\n106540890 176543892\n820600150 829674153\n400138009 457138269\n031002087 631952487\n065087304 965287314\n703065920 713465928\n204309075 284319675]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Sudoku Variations:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Future challenges will involve the Sudoku variations Diagonal, Arrow(Sums), Inequality, Irregular, and others as they present themselves.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Algorithm Spoiler:</w:t></w:r><w:r><w:t> Sudoku's can be readily solved using minimal choice recursion with consistency check. A key step is an index map of all indices that have mutual value exclusion (row,col,3x3), idxmap[81,27]. Another key step is to have an Evolve function that implements all single option values determined by the idxmap. A critical performance enhancement is a Sudoku Consistency Checker that checks for illegal replications of values. Illegal placements by Evolve occur when an incorrect value is asserted into the matrix during recursion trials. The recursive solver finds an idx with minimum options based on idxmap. The values for the idx location are asserted, Evolved, Consistency Checked, and then recursion call if Consistent. When all is Consistent and no unknowns remain the Sudoku is solved. Solution times are in the milli-seconds even for Evil, minimum 17 value, Sudokus.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve a Standard 9x9 <a href = "http://en.wikipedia.org/wiki/Sudoku">Sudoku</a>. Values 1 thru 9 occur in each row, column, and the nine non-overlapping 3x3 matrices starting at the top left corner. <a href = "http://www.free-sudoku.com/sudoku.php?dchoix=evil">Sudoku practice site</a>.Input: m, a 9x9 matrix of values 0 thru 9. Unknowns are 0s.Output: mout, a 9x9 matrix of values 1 thru 9 that satisfy Sudoku rules.Scoring: Time (msec) to solve the Hard SudokuExample:<pre class="language-matlab">m mout
390701506 398721546
042890701 542896731
106540890 176543892
820600150 829674153
400138009 457138269
031002087 631952487
065087304 965287314
703065920 713465928
204309075 284319675
</pre>Sudoku Variations:Future challenges will involve the Sudoku variations Diagonal, Arrow(Sums), Inequality, Irregular, and others as they present themselves.Algorithm Spoiler:
Sudoku's can be readily solved using minimal choice recursion with consistency check. A key step is an index map of all indices that have mutual value exclusion (row,col,3x3), idxmap[81,27]. Another key step is to have an Evolve function that implements all single option values determined by the idxmap. A critical performance enhancement is a Sudoku Consistency Checker that checks for illegal replications of values. Illegal placements by Evolve occur when an incorrect value is asserted into the matrix during recursion trials. The recursive solver finds an idx with minimum options based on idxmap. The values for the idx location are asserted, Evolved, Consistency Checked, and then recursion call if Consistent. When all is Consistent and no unknowns remain the Sudoku is solved. Solution times are in the milli-seconds even for Evil, minimum 17 value, Sudokus.

Solve a Standard 9x9 <http://en.wikipedia.org/wiki/Sudoku Sudoku>. Values 1 thru 9 occur in each row, column, and the nine non-overlapping 3x3 matrices starting at the top left corner. <http://www.free-sudoku.com/sudoku.php?dchoix=evil Sudoku practice site>.

*Input:* m, a 9x9 matrix of values 0 thru 9. Unknowns are 0s.

*Output:* mout, a 9x9 matrix of values 1 thru 9 that satisfy Sudoku rules.

*Scoring:* Time (msec) to solve the Hard Sudoku

*Example:*

m         mout
  390701506 398721546
  042890701 542896731
  106540890 176543892
  820600150 829674153
  400138009 457138269
  031002087 631952487
  065087304 965287314
  703065920 713465928
  204309075 284319675

*Sudoku Variations:*

Future challenges will involve the Sudoku variations Diagonal, Arrow(Sums), Inequality, Irregular, and others as they present themselves.

*Algorithm Spoiler:*
Sudoku's can be readily solved using minimal choice recursion with consistency check. A key step is an index map of all indices that have mutual value exclusion (row,col,3x3), idxmap[81,27]. Another key step is to have an Evolve function that implements all single option values determined by the idxmap. A critical performance enhancement is a Sudoku Consistency Checker that checks for illegal replications of values. Illegal placements by Evolve occur when an incorrect value is asserted into the matrix during recursion trials. The recursive solver finds an idx with minimum options based on idxmap. The values for the idx location are asserted, Evolved, Consistency Checked, and then recursion call if Consistent. When all is Consistent and no unknowns remain the Sudoku is solved. Solution times are in the milli-seconds even for Evil, minimum 17 value, Sudokus.

Solve

Solution Stats

118 Solutions
31 Solvers

Last Solution submitted on Mar 10, 2021

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Alex on 30 Jul 2020

This is a fun problem. Does the scoring based on time use no longer work?

Johanna Richter on 2 Oct 2020

i dont really get how the size of some problems is determined so small even though they have a really complex code when checking :/

took me like 3 hours to do, but it finally worked out,
definitely a challenge!!

Problem Recent Solvers31

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!