SudokuWiki
SudokuWiki.org
Strategies for Popular Number Puzzles

Sudoku Solver - Version History

Thanks to feedback I've now added a sanity check when you enter numbers. If there is a conflict - ie the same number in a row, column or box - it will hightlight those squares in red. You'll notice this especially if your choices are wrong and you continue to 'take steps'.

Also in this version is an email button. You can send a link to a friend containing the current board. Note: This is the board *as it looks now* - so you can send completed boards or new boards, whatever is currently shown.

Version 1.00
Version 1.00 one Sunday afternoon in May 2005

New in version 1.06
We now have a back button. Look for the [<<] button next to Take Step. Goes back one step.

New in version 1.07
Added Remote Pairs test.

New in version 1.08
Some extra checks including pointing pairs and pointing triples. Thanks to Phil Jackson for help with these.

New in version 1.09
A new test/strategy called Box/Line Reduction. Thanks to Andrew Pepperdine for this one.

New in version 1.10
Jethro Foreman, from Walton on Thames, has helped me enhance my first pairs test. This eliminates superfluous possibles from squares where pairs are hidden. Before I was only removing possibles from other squares in a box where open pairs were found. Confused? There'll be a explanation page soon.

Just nice to know that after two weeks we're still finding better strategies.

New in version 1.11 (June 28th 2005)
The remote pairs test has been taken a step further and is more generalised. A number of peripheral features have been added and enhanced including the Printable Version.

New in version 1.13 (July 28th 2005)
Don't know what happened to 1.12, but 1.13 now includes a version of the X-Wing strategy and the Sword Fish strategy. I'm calling them the basic version because I'm looking at rows and columns only. Box versions to come, but these are a powerful tests. I've also changed the looping strategy to cope with having all these tests. There can be nasty conflicts if they are run in sucession without chearing up the board first.

New in version 1.14 (August 12th)
I have broken up the trivial tests to seperate showing possibles from checking for single candidates. This makes it clearer which rule has been used and will help people understand the steps being taken.

New in version 1.15 (August 23rd 2005)
Thank-you to Joris S.de Wit of the Netherlands for finding an example which one of the pairs tests didn't catch. To do with those awkward boxes. Well done Joris! Also, Flemming Birkbak of Denmark writes in with a hidden pair I'd not seen before. Big thanks to him also.

August 26rd - I have replaced the example list of Sudoku's with a set of my own from my own generator. There are some normal ones - graded - and some freaks. The two Extreme ones are the worst (highest scoring) of a batch of 33,000. See how you like them. Try them without using the solver first! I dare you.
New in version 1.16 (September 4th 2005)
The swordfish algorithm is now much better, thanks to prompting by Ron Cowpe of Canada who provided a good example. It needed a good re-write as well since it was too slow. I've not found an example SwordFish that it can't detect. Hopefully!

New in version 1.17 (September 20th 2005)
I've split out the triples test from the main pairs tests so its easier to spot. Triples occur in the same row, column or box where you have, for example, 1/5 1/5/8 and 1/8 in three cells. 1,5 and 8 can be removed from any of the remaining 5 cells.

New in version 1.18 (November 7th)
Hidden Triples added. Nasty little beast. Big thanks to Matt Rivers from Northridge, California for sending in a board with a perfect example. Now added to the documentation. Since this goes hand in hand with Hidden Pairs (but is much more complicatied as it requires three numbers not just in threes but say 3/2/2 or 3/3/2). I've put the hidden pairs/triples test on its own. That means combining the naked pairs/triples tests which go together logically.

New in version 1.19 (December 20th 2005)
Y-Wings have been added to the strategy list. Documentation added here.

New in version 1.20 (December 23th)
Thanks to Tim van Kampen for a very fiendish Sudoku,
I've extended Hidden Pairs/Triples to Hidden Quads. Same principle, just four numbers spaced in four cells across a row, column or box.

New in version 1.21 (January 11th)
Added the Import Sudoku button.

New in version 1.22 (February 24th)
Major update. Apart from adding the excellent strategy Aligned Pair Exclusion I've added a report box which gives you all the moves when a strategy executes. Lots of requests for this. Some minor bug fixes as well.

New in version 1.23 (April 22nd)
Prompted by Mike Blake and some of his javacode I've added Type 1 Unique Rectangles. Note: this strategy assumes the Sudoku has a single unique solution. If the answer goes awry then it may not be.

New in version 1.24 (May 1st)
Naked Quads added by demand.

New in version 1.25 (May 3rd)
You can now edit the numbers in the large Sudoku board and enter more than one number to make changes to the 'notes' or candidates. This will reset the solving stage back to the start (so knock on effects are taken into account).

New in version 1.26 (May 23rd)
Many people have written to me to comment about multiple solutions for a given Sudoku. There are no logical tricks the solver can use to detect this other than not complete correctly. The only way to check this is to perform a brute force analysis which tests every possible legal placement of a number. Computers are good at this and we now have a new yellow button called "Solution Count". Try this on any Sudoku to check if it has a unique solution.

New in version 1.27 (May 28th)
Had some queries about the Extended APE not working. Actually it wasn't included in the solver but that's now changed. All the EAPE examples with work. Because I moved the Y-Wing before APE the normal APE the Y-Wing gets the result first. I'll upload an APE that can't be done with Y-Wing soon.

New in version 1.28 (May 29th)
Designed a much faster Swordfish detection allgorith. Also fixed a bug introduced in 1.27 when APE was extended.

New in version 1.30 (July 7th 2006)
Version 1.30 is a major update since I've found a way to include all the advanced strategies in my off-line C++ solver that were simply not possible to program in Javascript. Much still remains in javascript but its mostly user interface stuff now.

New in version 1.31 (July 13th 2006)
Minor update. Certain formations were not being detected for Type 4/4B Unique Rectangles.
Added Hidden Unique Rectangles. Split out AICs with and without grouped nodes.

New in version 1.32 (July 22th 2006)
Two new Extreme strategies added: Sue-de-Coq and Two Disjoint Almost Locked Sets.

New in version 1.33 (Ausgut 24th 2006)
Fixed the back button bug, added strategy toggle checkboxes.

New in version 1.34 (August 29th 2006)
Changed AIC strategies to return the shorest chain result.

New in version 1.35 (September 9th 2006)
Save button now saves permanently (using a cookie) even if you browse away or close your browser.

New in version 1.36 (September 16th 2006)
Added Multivalue X-Wing strategy and extended the scope of Almost Locked Sets.

New in version 1.37 (September 30th 2006)
Added Death Blossom by Mike Barker.

New in version 1.38 (November 21st 2006)
New Jigsaw Solver released!

New in version 1.39 (December 2nd 2006)
Much faster Advanced Strategies - the solver now continues to search for the first strategy that returns a result (applies to X-Wings and beyond). This will save you a lot of time clicking and ease the server load as well.

New in version 1.40 (March 21st 2007)
New variation of the Hidden Unique Rectangle has been added. Thanks to Mage in France for giving me an
excellent example.

New in version 1.50 (May 25th 2008)
I have added a grading button to this solver. Many people have asked for a grade check to see if their puzzles are accurately graded. Note that different publishers will have very different methods of grading, some good, some poor. For more information on my grading I have a paper on this topic.
Detection of X-Cycles has been improved, thanks to Thomas Kimble for the examples. Other minor accumulated improvements as well.

New in version 1.51 (Feb 1st 2009)
Split out Hidden Unique Rectangles from Unique Rectangles to make it more visible and to provide a link to the strategy from the solver page.

New in version 1.52 (March 1st 2009)
Save and Reload cookie now remembers candidates.

New in version 1.53 (Apr 14th 2009)
Code consolidation and minor bug fixes.

New in version 1.60 (June 13th 2009)
Killer Sudoku Solver released; new method implemented for client-server comms.

New in version 1.62 (Jan 25th 2010)
Chaining strategies that report chains now display those chains as a new graphical element on the big board.

New in version 1.63 (March 3rd 2010)
3D Medusa and much improved forcing chains. A new system of symbolising chains.

New in version 1.64/5 (March 13th 2010)
Fixed a series of bugs with editing candidates in the large board. Added Digit Forcing Chains

New in version 1.64/5 (March 13th 2010)
Fixed a bug to do with unchecking strategies

New in version 1.67 (January 20th 2011)
new navigation (arrows etc) in the small data entry board.

New in version 1.68 (January 26th 2011)
Fixed a bug searching for Hidden Quads in columns (thanks Mats Anderbok!)

New in version 1.69 (Mar 13th 2011)
In response to a query about how a Sudoku puzzle solved differently when rotated, I have added a couple of rotate buttons on the Sudoku and Sudoku X solvers. Infact the original Sudoku was broken and nothing could be said about it, but in general, rotating a puzzle can lead to new insights, especially when solving by pen and paper. My solver will in almost all cases, solve the puzzle in the same way whatever rotation or symetrical transformation is applied. There are exceptions due to the way patterns are searched for - often the search begins in the top left corner and ends in the bottom right - and the first instance of a pattern is returned. I imagine that for some advanced strategies, a rotation may return a different elimination - it depends how many opportunities there are.

New in version 1.70 (March 23rd 2011)
I have added a new strategy, Cage/Unit Overlap, to the Killer Solver - thanks to an example from Marcel Cox.

New in version 1.72 (May 19th 2011)
Added the new solver for Colour Sudoku. This adds to the back end solver machine so it effects every solver - hopefully not negatively. I have also synched the version numbers to 1.72 on all solvers.

New in version 1.73 (June 2nd 2011)
Expanded the number of ways Forcing Chains can get results. Thanks to Steve Kurzhals for inspiring these with some of his analysis of the recent Unsolvables. The documentation is being updated to reflect the additions. I have added a diagram and examples to Digit Forcing Chains and will need to do so for Cell Forcing Chains and Unit Forcing Chains.

New in version 1.74 (June 21st 2011)
I sped up the "Take Step" process by skipping failed strategies and going straight to the first successful one. This applies to the basic strategies which are client-side. If you get "script taking too long" messages from your browser, let me know. It's a bit risky for slower machines and I'd like to find out if this works for everyone.

New in versions 1.75, 1.76, 1.77
Bug fixes and changes to AIC searching, thanks to Andreas von Delius

New in version 1.78 (Oct 3rd 2011)
I have looked again at the basic strategies, something I haven't done for a while. For Pairs, Triples, Quads, Pointing Pairs and Box/Line Reductions - these all now show in green the candidates that contributed to the pattern. This should make searching for them from the textual description redundant and more 'at a glance'. Previously only the eliminated candidates were being show (ones in yellow).

New in version 1.79 (Oct 23rd 2011)
Added a graphical display to show all chain links in Singles Chains (Simple Colouring). This version update also contained new strategy algorithms for 6x6 KenKen.

New in version 1.80 (Dec 3rd 2011)
I have redesigned the way Hidden Singles are handled and merged checking boxes with checking rows and columns. At the same time I've stopped it removing candidates before the scan is complete - which before had a knock-on effect of creating additional Hidden Singles. Either way is harmless but I wanted to remove knock-on effects.

New in version 1.81 (Apr 20rd 2012)
Restored Unique Rectangles to the Sudoku X solver. Added a special kind of Sudoku X Pointng Pair previously found by Simple Colouring. There have been a number of miner fixes to the solver in February and March not worthy of a version increment.

New in version 1.82 (May 10th 2012)
I have redesigned the way cookies are stored and puzzles loaded. You still have a manual save and reload but the solver now automatically saves the board every time it changes. Should you loose the page it will restore the puzzle you were working on. Cookies also retain the difference between clues and solved cells as well.

New in version 1.85 (June 8th 2012)
On the small board for number entry I have added an option that automatically clears off candidates as numbers are added. Also, changes to the small board are automatically saved. To make number entry clearer you can select if you are entering clues or solutions. See What's New for more detail.

New in version 1.86 (July 16th 2012)
I have added Nishio Forcing Chains replacing the old Nishio which never did anything anyway. This is a variety of Digit Forcing Chain where a contradiction is sought with two chains starting with a candidate turned ON. I have also rewritten part of the Grouped Cells to include many more instances. Also added another trap for garbage imput on the Killer solver which was crashing the solver.


New in version 1.87 (August 23rd 2012)
Added some Pointing Pair identification that was missing in previous versions.
Code upgraded so that candidates I highlighted green when the contribute to Pairs, Triples etc.
Automatic saving of the current board position on any change - so you can navigate away.
Still allows the normal Sabe/Reload.
Added Cage Comparison to the killer strategies.

New in version 1.88 (August 24th 2012)
Added the Extended Unique Rectangles strategy to the Sudoku solver.

New in version 1.89 (August 29th 2012)
Version 1.89 is a minor update to fix a bug occuring in Internet Explorer. Probably down to how javascript variables are declared, which is weird.

New in version 1.90 (October 17th 2012)
Killer Sudoku update (internal). Re-wrote Killer Innies/Outies to include more cases and better detection.

New in version 1.91 (November 21th 2012)
Jigsaw Sudoku update (internal). Re-wrote Pointing Pairs for Jigsaws - obvious new case

New in version 1.92 (March 20th 2013)
Solvers update (website and internal). Created the button for hull HTML output from a grade request showing all the steps of the puzzle.

New in version 1.93 (May 21th 2013)
Sudoku solver update (internal). Re-wrote the Forcing Chains strategies to improve detection (new cases) and the language of the result. Added 3D Medusa Rule 7.

New in version 1.94 (May 21th 2013)
Fixed some bugs in the Killer solver and improved the text returned from Cage Combinations. Made sure the 'last remaining cell' in a cage was correctly being identified and now shows on the Hidden Singles stage.

New in version 1.95 (June 3rd 2013)
Added Double Pointing Pairs and Double Line/Box Reduction to the Jigsaw Solver. Improved the output of Jigsaw Pointing Pairs.

New in version 1.96 (July 20th 2013)
Greatly expanded WXYZ-Wings detection - makes is actually worth having in the list now! Separated and moved XYZ-Wings to tough strategies. Internally I could junk the Y-Wing algorithm and use the XYZ-Wing algorithm with a simple switch to search for bi-value hinges.

New in version 1.97 (July 22th 2013)
Added a tool to show strong links on the board. Under the strategy list.

New in version 1.98 (Sept 26th 2013)
Fixed Naked/Hidden Pairs/Triples to stop knock-on Pairs/Triples but allow multiple independent instances. See What's new for more info.

New in version 1.99 (April 9th 2014)
Unchecked strategies are now saved in a cookie.

Rolled over version numbers to 2.x now I'm over a hundred versions!

New in version 2.01 (August 25th 2015)
Added a clue+solved cell count; added a show bi-value cells checkbox.

New in version 2.02 (Sept/Oct 2015)
Mainly under the hood enhancements to Killer Sudoku

New in version 2.03 (November 12th 2015)
Added Windoku Sovler

New in version 2.04 (March 26th 2016)
Taken advantage of the new approach to Windoku "windows" to make the Windoku solver much more powerful. Some other minor bugs fixed along the way.

New in version 2.05 (October 27th 2016)
Added Exocet and Double Exocet, or at least the parts I understand. There are a good number of eliminations set out by the inventors of this strategy - but I have yet to understood them all.

November 2016: (Changes not requiring a version increment) Extended UR Type 3 to triples and Added UR Type 2C

New in version 2.06 (September 8th 2017)
Added an elimination for Killers where the cage dog-leg allows a Naked Pair to eliminate in the other two corners of the rectangle formed by a diagonal pattern. Thanks to JohnNoneDoe for the example.

Nov 19th 2017: Found out I was missing a certain way to link Grouped cells in X-Cycles and AICs thanks to an example from Patrick Fischer. Solver updated under the hood.

New in version 2.06 (January 23rd 2019)
Added Using Unique Rectangles as Links in Chains

New in version 2.07 (September 28th 2019)
Added Gurth's Theorem as a strategy for the main Sudoku solver.

New in version 2.08 (November 29th 2019)
Added detection for SK Loops in the main Sudoku solver.


Update to version 2.08 (April 29th 2020)
Added a new type of link which will turn up in all chaining strategies. I don't know what to call it so the page has been called AICs with Exotic Links.

Updated version 2.08 (January 30th 2021)
Added Type 5 to Unique Rectangles

Updated version 2.09 (December 12th 2021)
Added Triple and Quad Fireworks

Updated version 2.10 (October 8th 2023)
Added the ability to cycle through different chains if more than one is found at any stage. More on the Whats New page. Also in the last year: Solve Path now uses strategy exclusions (the checkboxes); Expanded HUR Type 1 to get more if symmetrical; Added EUR Type 4

Updated version 2.11 (October 14th 2023)
Rectangle Elimination replaces Empty Rectangles

27th January 2024
Added Type 2 Extended Unique Rectangles.




Comments

Comments
Talk

... by: Lizelle

Thursday 3-Sep-2015
I love your website. Visit it every now and again when desperate and it always helps. You must be blooming brilliant, Andrew. Regards, L
Andrew Stuart writes:
Thanks Lizelle! - [Del]
Add to this Thread

... by: Steven Haver

Saturday 27-Apr-2013
The "import" function, where we manually key all 81 squares, would be a little easier to use if there were a tick mark every 9 positions; to help confirm that each row is properly aligned.
Andrew Stuart writes:
I'm using a simple browser input box, nothing fancy. Your suggestion is a good one and I'd have to create a special pop up input form, not a huge task. I always use a text editor to prepare nine rows and then concatenate them. - [Del]
Add to this Thread
Article created on 13-April-2008. Views: 251614
This page was last modified on 29-April-2020.
All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Syndicated Puzzles, Privacy, 2007-2024