.. -*- coding: utf-8 -*- .. Copyright (C) 2015,2019, Wolfgang Scherer, .. .. This file is part of HDP Sudoku. .. .. Permission is granted to copy, distribute and/or modify this document .. under the terms of the GNU Free Documentation License, Version 1.3 .. or any later version published by the Free Software Foundation; .. with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. .. A copy of the license is included in the section entitled "GNU .. Free Documentation License". .. inline comments (with du_comment_role) .. role:: rem(comment) .. role:: html(raw) :format: html .. role:: shx(code) :language: sh ################################################## :rem:`|||:sec:|||`\ World's Hardest Sudoku ################################################## .. >>CODD See `the components of a doctoral dissertation and their order `_ .. >>CODD Dedication .. >>CODD Epigraph .. >>CODD Abstract .. compound:: .. \|:here:| .. >>CODD Introduction .. # 5 # I8: 3,9 d: 28 h: 14 8..........36......7..9.2...5...7.......457....71...35..1...568..85...1..9....4.. # 6 # I8: 3,9 # B1: 1,2 => CTR => B1: 6 d: 55 h: 25 8.4....9.9.36.....57649.28..5.3.78......457..4.71..935.41.39568.685.43193958..4.. # 7 # I8: 3,9 + B1: 6 d: 28 h: 23 86.........36......7..9.2...5...7.......457....71...35..1...568..85...1..9....4.. # 8 # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 d: 47 h: 30 869........36.....574391286.52.376....6.457....71..835..1...568..85...1..9581.4.. # 9 # I8: 3,9 + B1: 6 + A2: 5,9 d: 38 h: 30 86.........36......7..9.2.6.5...7.......457....71...35..1...568..85...1..9....4.. # 11 # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 d: 56 h: 35 86.........36......7..9.2.6.5...7.......457..4871...35.31...568.485...1..9....4.. # 12 # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7 d: 40 h: 30 86........136.....574.91286.5...7.......457....71...35..1...568..85...1..95.1.4.. # 13 I8: 2,7 d: 6 h: 14 8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.. # 14 I8: 2,7 # G7: 5 d: 15 h: 25 8.....3....36......7..9.2...5...7.......457.....1...35..1...568..85..91..9....4.3 # 15 I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 d: 15 h: 34 81....3....36.81...7.39128..5...76...8..457.....1..835..1...568.685..91..9..164.3 # 16 I8: 2,7 # G7: 5 + G4: 1,8 d: 18 h: 31 8.....3....36......7..932...5..67.......457.....1..635..1...568..85..91..9....4.3 # 17 I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6 d: 40 h: 41 8.....3..9.36..1..17549328635..678.....8457...8.129635..19..568..85..91..9....4.3 # 18 I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 d: 21 h: 41 8.....3....36......7..932...5..67.....6.457.....1..635..1...568..85..91..9....4.3 # 19 I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8 d: 27 h: 47 8.....3....36.....67.8932.1.5..671841863457.....1..635..1...568.6853.91..9...64.3 # 20 I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9 d: 21 h: 52 8.....3....36..1..175493286.5..678.1.168457...8.129635..19..568..85..91.59...64.3 # 21 I8: 2,7 + G7: 3,9 d: 12 h: 26 8..........36......7..9.2...5...7.......457.....1...3.5.1....68..85...1..9....4.. # 22 I8: 2,7 + G7: 3,9 # A8: 3,4,6 d: 33 h: 34 8..........36......75.9.2...5...7.......457.....1...3.5.1....68..85...17.9....4.. # 23 I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7 d: 33 h: 45 8..........36..8...75.9824..5.387....3..4578.78.1...3.5.1....68..85...173978..4.. # 24 I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 d: 43 h: 40 8..........36......75.9.2...5...7.......457.....1...3.5.1....68..85...17.9....4.. # 25 I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9 d: 63 h: 60 81.7536...43682175675491283.5.9378..36.8457.1.8.12653.5312749684285693177963184.. # save I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 d: 45 h: 45 8..........36......75.9.2...5...7.......457.....1...3.5.1....68..85...17.9....4.. # view* I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL d: 59 h: 54 812753649943682175675491283154237896369845721287169534521974368438526917796318452 ....................... STA Original Sudoku HYP # I8: 3,9 DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 STA # I8: 3,9 + B1: 6 DIS # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 STA # I8: 3,9 + B1: 6 + A2: 5,9 DIS # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 DIS # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7 STA I8: 2,7 HYP I8: 2,7 # G7: 5 DIS I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 STA I8: 2,7 # G7: 5 + G4: 1,8 DIS I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6 STA I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9 STA I8: 2,7 + G7: 3,9 HYP I8: 2,7 + G7: 3,9 # A8: 3,4,6 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 PRF I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL ================================================== :rem:`|||:sec:|||`\ Introduction ================================================== The Telegraph asks: `World's hardest sudoku: can you crack it?`_: .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-input.jpg :scale: 100% :alt: (c) Arto Inkala, http://www.efamol.com/. Reproduced by permission of the author. .. image: The answer is: "Sure thing!" ... If you expect Fruity Loops and Flip-Flop Chains in `Darth Vader`_ style (*I can kill you with a single thought!*), you will be disappointed. However, the method employed is not simple trial and error either. The trial and error process usually offered for sudokus is a depth-first decision tree walk, which is as clueless as it gets. While the usual environment for abstract problems is in fact clueless, sudoku is nothing but all about the clues. Therefore, a - **breadth-first tree walk**\ [#fn_bf]_ with - **lookahead level 1** and - **restart** is a much better choice. Especially, since the sudoku constraints are naturally very loopy and new facts often change the results of previous tests. Although the depth of the search never exceeds 2 decision levels in this example, it does not mean that it is not a lot of work. The method is designed to work well with computer assisted solver programs. The program should have bookmarks, but if not, saving positions in files will do (you never need more than 2 files, unless there is no good undo function, then you will need 3 files). .. `Eddie Izzard- Death Star Canteen - YouTube`_ .. _`Darth Vader`: https://www.youtube.com/watch?v=Sv5iEK-IEzw .. _`Eddie Izzard- Death Star Canteen - YouTube`: https://www.youtube.com/watch?v=Sv5iEK-IEzw .. >>CODD Chapter ================================================== :rem:`|||:sec:|||`\ Notation ================================================== Each chain state is denoted by a marker: - **STA** Status - **INC** Inconclusive - **HYP** Hypothesis - **DIS** Disproof - **PRF** Proof Sudoku cells are denoted as `` (just as with spreadsheets. Or chess, if you wish). A statement about the allowed values of a sudoku cell is made by enumerating the values: | ` =def= : ,,..` E.g. `A2: 4,9,3` is read as: The cell `A2` can hold the values 4, 9 and 3. Special statements are used to emphasize disproof, proof or inconclusivity: - **CTR** stands for a contradiction, which disproves the last hypothesis. - **SOL** stands for a solution, which proves the entire hypothesis/fact chain - **UNS** stands for no further clues Several statements are concatenated with the operator `+`: | ` =def= + + ..` E.g. `A2: 4,9 + B5: 1,6` is read as: The cell `A2` can hold the values 4 and 9, **and** the cell `B5` can hold the values 1 and 6. A hypothetical statement is marked with `#` and introduces a new level of reasoning based on all previous statements and hypotheses: | ` =def= # ` E.g. `# A2: 7,8` is read as: Assuming that `A2` allows the values 7 and 8. The hypothesis/statement (HS) chain `# C3: 6 + B7: 9 # A2: 7,8` is read as: In the context of the assumption that `C3` must have the value 6 and the proven fact that `B7` must have the value 9 in this context, the assumption is made that `A2` can (only) hold the values 7 and 8. A conclusion from a HS chain is denoted by `=>`: ` => ` This defines a Hypothesis/Disproof/Proof chain (HDP chain) ================================================== :rem:`|||:sec:|||`\ Method ================================================== Let me say beforehand, that I never use anything more advanced than single/double column and naked/hidden pair/triple/quad checks (no X-Wing, Swordfish, XY-Wing, XYZ-Wing, never ever a XY-Chain). In fact, the example solution was found in this way. The special feature of this method lies in the structure of the binary decisions. The rest is just following a (tediously exhausting) process without giving in to the desire of finding a shortcut (there is none!). So, here goes ... - All hypotheses are formed based on strictly binary decisions. Therefore, a contradiction in one branch always proves the other branch. - A new hypothesis (**increased depth**) is only formed after an exhaustive search and test of all possible binary decisions (**breadth-first**, **lookahead 1**) within the same level. - If a hypothesis is proved or disproved, all previously examined decisions are re-examined (**restart**). - Both alternatives of a possible decision are **always** examined. If the alternative leads to a contradiction, an unsolved branch is still proved. This reduces the depth of the HDP chain, which is highly desirable. .. Branch1 | Branch2 | Action SOLVED | ??? | finish. The solution proves the correctness of the current HDP chain UNSOLVED | UNSOLVED | no action (resist the temptation to follow one of the branches further!) CTR | UNSOLVED | terminate current level and use branch 2 as a new proven fact in the HPD chain UNSOLVED | CTR | terminate current level and use branch 1 as a new proven fact in the HPD chain CTR | CTR | terminate current and previous and evaluate the contradiction in the context of the new current level +----------+----------+-------------------------------------------------------------------------------------------------------+ | Branch1 | Branch2 | Action | +==========+==========+=======================================================================================================+ | SOLVED | ??? | finish. The solution proves the correctness of the current HDP chain | +----------+----------+-------------------------------------------------------------------------------------------------------+ | ??? | SOLVED | finish. The solution proves the correctness of the current HDP chain | +----------+----------+-------------------------------------------------------------------------------------------------------+ | UNSOLVED | UNSOLVED | no action (resist the temptation to follow one of the branches further!) | +----------+----------+-------------------------------------------------------------------------------------------------------+ | CTR | UNSOLVED | terminate current level and use branch 2 as a new proven fact in the HPD chain | +----------+----------+-------------------------------------------------------------------------------------------------------+ | UNSOLVED | CTR | terminate current level and use branch 1 as a new proven fact in the HPD chain | +----------+----------+-------------------------------------------------------------------------------------------------------+ | CTR | CTR | terminate current and previous and evaluate the contradiction in the context of the new current level | +----------+----------+-------------------------------------------------------------------------------------------------------+ -------------------------------------------------- :rem:`||:sec:||`\ Cell Pair Reduction -------------------------------------------------- Since this is the main method for solving a sudoku, the unqualified term `pair reduction` always refers to `cell pair reduction`. - find all cells allowing exactly two values (pairs) - for each pair: identify all cells (reduction candidates) within each constraint (block,row,column) which also contain the values of the pair - for each pair + reduction candidate: examine the consequences of each alternative by solving the sudoku in the normal manner: - pair + reduction candidate becomes a strongly linked pair (both cells contain the same values) - pair + reduction candidate do not share any values ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|||:sec:|||`\ Cell Pair Example G8: 3,9 candidates: G1, G7, F8, I8 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-cell-pair-000.jpg :scale: 75% :alt: Cell Pair Example G8: 3,9 candidates: G1, G7, F8, I8 :rem:`break` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|||:sec:|||`\ Cell Pair Example Alternative 1: G8: 3,9 # G1: 3,9 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +------------------------------------------------------------------------------------------------+------------------------------------------------------------------------------------------------+ | .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-cell-pair-001.jpg | .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-cell-pair-003.jpg | | :scale: 75% | :scale: 75% | | :alt: Cell Pair Example Alternative 1: G8: 3,9 # G1: 3,9 | :alt: Cell Pair Example Alternative 1: G8: 3,9 # G1: 3,9 solved | | | | | Cell Pair Example Alternative 1: G8: 3,9 # G1: 3,9 | Cell Pair Example Alternative 1: G8: 3,9 # G1: 3,9 solved | +------------------------------------------------------------------------------------------------+------------------------------------------------------------------------------------------------+ .. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|||:sec:|||`\ Cell Pair Example Alternative 1: G8: 3,9 # G1: 3,9 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-cell-pair-001.jpg :scale: 75% :alt: Cell Pair Example Alternative 1: G8: 3,9 # G1: 3,9 :rem:`break` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|||:sec:|||`\ Cell Pair Example Alternative 1: G8: 3,9 # G1: 3,9 solved ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-cell-pair-003.jpg :scale: 75% :alt: Cell Pair Example Alternative 1: G8: 3,9 # G1: 3,9 solved :rem:`break` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|||:sec:|||`\ Cell Pair Example Alternative 2: G8: 3,9 # G1: 1,5,6 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +------------------------------------------------------------------------------------------------+------------------------------------------------------------------------------------------------+ | .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-cell-pair-002.jpg | .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-cell-pair-004.jpg | | :scale: 75% | :scale: 75% | | :alt: Cell Pair Example Alternative 2: G8: 3,9 # G1: 1,5,6 | :alt: Cell Pair Example Alternative 2: G8: 3,9 # G1: 1,5,6 solved | | | | | Cell Pair Example Alternative 2: G8: 3,9 # G1: 1,5,6 | Cell Pair Example Alternative 2: G8: 3,9 # G1: 1,5,6 solved | +------------------------------------------------------------------------------------------------+------------------------------------------------------------------------------------------------+ :rem:`break` .. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|||:sec:|||`\ Cell Pair Example Alternative 2: G8: 3,9 # G1: 1,5,6 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-cell-pair-002.jpg :scale: 75% :alt: Cell Pair Example Alternative 2: G8: 3,9 # G1: 1,5,6 :rem:`break` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|||:sec:|||`\ Cell Pair Example Alternative 2: G8: 3,9 # G1: 1,5,6 solved ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-cell-pair-004.jpg :scale: 75% :alt: Cell Pair Example Alternative 2: G8: 3,9 # G1: 1,5,6 solved :rem:`break` -------------------------------------------------- :rem:`||:sec:||`\ Constraint Pair Reduction -------------------------------------------------- If there are no cell pairs: - find all cells within a constraint which allow for a specific value. - If the number of cells is exactly two (constraint value pair), use the same binary decision method as for cell pair reduction. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|||:sec:|||`\ Constraint Pair Example for Value 5: E1,E2 + G6,I6 + A7,G7 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-constraint-pair-005.jpg :scale: 75% :alt: Constraint Pair Example for Value 5: E1,E2 + G6,I6 + A7,G7 :rem:`break` -------------------------------------------------- :rem:`||:sec:||`\ Fun Effects -------------------------------------------------- The design of the pair reduction algorithm aims to reduce a sudoku to cells which only contain single values or pairs. So it is no surprise, that this eventually succeeds. Here is a full reduction from the sudoku:: ........3..1..9.6..5..8.4.....9...8...867.....1....2....6..7.2..3.8..5..4.......8 The pair chain produces a contradiction for both branches. .. figure:: _static/worlds-hardest-sudoku/xx-tarx0119-work-000.jpg :scale: 75% :alt: Fully reduced cells (DPR A7 = 8,9) Fully reduced cells (DPR A7 = 8,9) -------------------------------------------------- :rem:`||:sec:||`\ Bread-First vs. Depth-First -------------------------------------------------- Based on the following simplified desicion tree, note that eliminating `C4: 1,5,6,8` causes `B5: 3,5,9` to detect a contradiction immediately instead of during resolution of hypothesis `I6: 5,9`. Doing a depth-first walk delivers the following HDP chain:: INC # C4: 2,4 DIS # C4: 2,4 # B5: 2,4 => CTR => B5: 3,5,9 DIS # C4: 2,4 + B5: 3,5,9 # I6: 5,9 => CTR => I6: 3,7,8 DIS # C4: 2,4 + B5: 3,5,9 + I6: 3,7,8 => CTR => C4: 1,5,6,8 DIS C4: 1,5,6,8 => CTR While a breadth-first walk delivers the following HDP chain:: INC # C4: 2,4 DIS # C4: 1,5,6,8 => CTR => C4: 2,4 DIS C4: 2,4 # B5: 2,4 => CTR => B5: 3,5,9 DIS C4: 2,4 + B5: 3,5,9 => CTR .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-tree.png :scale: 75% :alt: Decision Trees :rem:`break` .. .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-tree3.png :scale: 75% :alt: Decision Tree after Elimination of I8 :rem:`break` The scenario is not uncommon, since sudokus have a single solution, which necessarily causes many contradictions in the decision tree. `This sudoku`_ from `menneske.no`_ is a good example, where the benefit of staying on the same level can be seen directly. The reduction pair analysis does not find a solution, since it only evaluates a hypothesis in itself. It does not propagate the consequences from a contradiction in the branches. .. figure:: ../level-medium/zz-menneske-no-06913279-base/zz-menneske-no-06913279-base-pr-000.png :width: 1280px :alt: Pair Reduction Analysis :target: ../level-medium/zz-menneske-no-06913279-base/zz-menneske-no-06913279-base-pr-000.png However, when the consequences of the contradictions are propagated, a new pair `C1: 2,7` is detected, which is used in the hypothesis `C1: 2,7 # B2: 2,7` to reveal the solution: .. figure:: ../level-medium/zz-menneske-no-06913279-base/zz-menneske-no-06913279-base-pr-001.png :width: 1280px :alt: Pair Reduction :target: ../level-medium/zz-menneske-no-06913279-base/zz-menneske-no-06913279-base-pr-001.png .. _`menneske.no`: http://www.menneske.no/sudoku/utskrift.html?number=6913279 .. _`This sudoku`: ../level-medium/zz-menneske-no-06913279-base/zz-menneske-no-06913279-base.html Another advantage of doing a breadth-first walk lies in the possibility of information gathering. For each unsolved decision branch, the number of resulting pairs can be recorded. If all checks reveal no further immediate contradictions, a hypothesis must be formed. In that case it is usually (but not necessarily) advantageous to choose the decision branch resulting in most pairs. If one branch results in 5 pairs and another branch results in 19 pairs, it is definitely good to check the 19-pair branch first. Here is the pair reduction analysis of the *World's Hardest Sudoku*:: # * PAIR REDUCTION .. # * LEVEL 0 PASS 1 ROUND 1 (AUTO SOLVE) (G8) # * 8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.. # * PAIR G8: 3,9 BLK 9 # G7: 3,9,5 # reduction candidate for 3,9 # G7: 3,9 # 3 pairs # I8: 3,9,2,7 # reduction candidate for 3,9 # I8: 3,9 # 7 pairs # * PAIR G8: 3,9 ROW 8 # F8: 3,9,2,4,6 # reduction candidate for 3,9 # F8: 3,9 # 4 pairs # F8: 2,4,6 # 2 pairs # * PAIR G8: 3,9 COL G # G1: 3,9,1,5,6 # reduction candidate for 3,9 # G1: 3,9 # 6 pairs # G1: 1,5,6 # 1 pairs # * UNSOLVED! The decision graph for the first level does not look very promising: .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-pr-000.png :alt: First level pair reduction decision tree :target: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-pr-000.svg However the actual pair reduction that leads to the solution does not exceed level 2 and gives a much better picture: .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-pr-001.png :width: 1280px :alt: DPR Solvable (even without single/double column elimination) :target: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-pr-001.svg .. note:: The fact that sometimes more than one value is allowed/disallowed in a decision branch has nothing to do with the binary nature of the decision. I have a hard time understanding the necessity to consider only single values, which seems to be some sort of quality criterium for certain people. The strictness of a binary decision does not go away, just because more than one possible value is considered. I also do not find it harder to follow the consequences of multiple values than following the consequences of a single value. =================================================== :rem:`|||:sec:|||`\ Hypothesis/Disproof/Proof Chain =================================================== The following hypothesis/disproof/proof chain leads to the solution:: - STA Original Sudoku - HYP # I8: 3,9 - DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 - DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 - STA # I8: 3,9 + B1: 6 - DIS # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 - STA # I8: 3,9 + B1: 6 + A2: 5,9 - DIS # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 - STA I8: 2,7 - HYP I8: 2,7 # G7: 5 - DIS I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 - STA I8: 2,7 # G7: 5 + G4: 1,8 - DIS I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6 - STA I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 - DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8 - DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9 - STA I8: 2,7 + G7: 3,9 - HYP I8: 2,7 + G7: 3,9 # A8: 3,4,6 - DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7 - STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 - DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9 - PRF I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL - STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 Section `HDP Chain Illustrations`_ shows Screenshots for all the stages. I have since automated this algorithm in a first crude manner to allow for automatic classification of hardness. In its current completely unoptimized form, the program comes back with this chain of reasoning (see `Analysis of xx-worlds-hardest-sudoku-work.sdk`_ for automated result): :: DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 DIS # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 DIS # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 DIS # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7 DIS I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 DIS I8: 2,7 # G7: 5 + G4: 1,8 # A4: 2,9 => CTR => A4: 1,3 DIS I8: 2,7 # G7: 5 + G4: 1,8 + A4: 1,3 # A5: 2,9 => CTR => A5: 1,3,6 DIS I8: 2,7 # G7: 5 + G4: 1,8 + A4: 1,3 + A5: 1,3,6 # C5: 2,9 => CTR => C5: 6 DIS I8: 2,7 # G7: 5 + G4: 1,8 + A4: 1,3 + A5: 1,3,6 + C5: 6 => CTR => G7: 3,9 DIS I8: 2,7 + G7: 3,9 # F8: 3,9 # E9: 2,6 => CTR => E9: 1,3,8 DIS I8: 2,7 + G7: 3,9 # F8: 3,9 + E9: 1,3,8 # F9: 2,6 => CTR => F9: 1,3,8 DIS I8: 2,7 + G7: 3,9 # F8: 3,9 + E9: 1,3,8 + F9: 1,3,8 # F7: 3,9 => CTR => F7: 2,4 DIS I8: 2,7 + G7: 3,9 # F8: 3,9 + E9: 1,3,8 + F9: 1,3,8 + F7: 2,4 # A8: 4 => CTR => A8: 2,7 DIS I8: 2,7 + G7: 3,9 # F8: 3,9 + E9: 1,3,8 + F9: 1,3,8 + F7: 2,4 + A8: 2,7 # B1: 1,2 => CTR => B1: 6 DIS I8: 2,7 + G7: 3,9 # F8: 3,9 + E9: 1,3,8 + F9: 1,3,8 + F7: 2,4 + A8: 2,7 + B1: 6 => CTR => F8: 2,4,6 DIS I8: 2,7 + G7: 3,9 + F8: 2,4,6 # B8: 2,4 => CTR => B8: 3,6 DIS I8: 2,7 + G7: 3,9 + F8: 2,4,6 + B8: 3,6 # B6: 2,4 => CTR => B6: 6,8 DIS I8: 2,7 + G7: 3,9 + F8: 2,4,6 + B8: 3,6 + B6: 6,8 # D7: 2,4 => CTR => D7: 7,9 DIS I8: 2,7 + G7: 3,9 + F8: 2,4,6 + B8: 3,6 + B6: 6,8 + D7: 7,9 # F7: 9 => CTR => F7: 2,4 DIS I8: 2,7 + G7: 3,9 + F8: 2,4,6 + B8: 3,6 + B6: 6,8 + D7: 7,9 + F7: 2,4 # B1: 2,4 => CTR => B1: 1,6 DIS I8: 2,7 + G7: 3,9 + F8: 2,4,6 + B8: 3,6 + B6: 6,8 + D7: 7,9 + F7: 2,4 + B1: 1,6 # A8: 3,6,7 => CTR => A8: 2,4 DIS I8: 2,7 + G7: 3,9 + F8: 2,4,6 + B8: 3,6 + B6: 6,8 + D7: 7,9 + F7: 2,4 + B1: 1,6 + A8: 2,4 # A2: 2,4 => CTR => A2: 9 DIS I8: 2,7 + G7: 3,9 + F8: 2,4,6 + B8: 3,6 + B6: 6,8 + D7: 7,9 + F7: 2,4 + B1: 1,6 + A8: 2,4 + A2: 9 # E1: 2,3 => CTR => E1: 5 PRF I8: 2,7 + G7: 3,9 + F8: 2,4,6 + B8: 3,6 + B6: 6,8 + D7: 7,9 + F7: 2,4 + B1: 1,6 + A8: 2,4 + A2: 9 + E1: 5 => SOL STA I8: 2,7 + G7: 3,9 + F8: 2,4,6 + B8: 3,6 + B6: 6,8 + D7: 7,9 + F7: 2,4 + B1: 1,6 + A8: 2,4 + A2: 9 + E1: 5 The `level index of analyzed sudokus`_ lists some sudokus that I have collected and run through my research tool. ================================================== :rem:`|||:sec:|||`\ Harder Than Your Husband ... ================================================== So, the *World's Hardest Sudoku* does not seem so hard after all. And in the context of this algorithm it actually isn't. I have found some `harder puzzles`_, of which `tarx0119`_ is the hardest so far. The initial pair reduction analysis is pretty meager: .. figure:: _static/worlds-hardest-sudoku/xx-tarx0119-work-pr-000.png :alt: Initial Pair Reduction :target: _static/worlds-hardest-sudoku/xx-tarx0119-work-pr-000.svg Here is an actual 2-level pair reduction analysis for the sudoku *tarx0119*: .. figure:: _static/worlds-hardest-sudoku/xx-tarx0119-work-pr-001.png :width: 1280px :alt: Deep Pair Reduction (PRR) is inconclusive :target: _static/worlds-hardest-sudoku/xx-tarx0119-work-pr-001.svg This sudoku requires 1 level of constraint pair reduction and 2 levels of cell pair reduction to be solved. Here is the inital disproof of hypothesis `# A7: 8`: .. figure:: _static/worlds-hardest-sudoku/xx-tarx0119-work-pr-002.png :width: 1280px :alt: Very Deep Constraint Pair Reduction (PRR) yields # A7: 8 => CTR => B7: 8 :target: _static/worlds-hardest-sudoku/xx-tarx0119-work-pr-002.svg After the clue `B7: 8` is detected, the full resolution only requires 2 levels of cell pair reduction. Although there is still only the same lonlely pair available and only one additional clue is detected, the 2-level decision chain presents itself very differently and is now actually quite simple: .. figure:: _static/worlds-hardest-sudoku/xx-tarx0119-work-pr-003.png :width: 1280px :alt: VDCP Check => B7: 8 - This problem is DPR solvable :target: _static/worlds-hardest-sudoku/xx-tarx0119-work-pr-003.svg .. _HDP Chain Illustrations: ======================================================================== :rem:`|||:sec:|||`\ HDP Chain Illustrations for *World's Hardest Sudoku* ======================================================================== .. \|||||:here:||||| -------------------------------------------- :rem:`|||:sec:|||`\ STA Original Sudoku -------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-000.jpg :scale: 75% :alt: Original Sudoku :rem:`break` -------------------------------------- :rem:`|||:sec:|||`\ HYP # I8: 3,9 -------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-001.jpg :scale: 75% :alt: # I8: 3,9 :rem:`break` ------------------------------------------------------------ :rem:`|||:sec:|||`\ DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 ------------------------------------------------------------ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-002.jpg :scale: 75% :alt: # I8: 3,9 # B1: 1,2 => CTR => B1: 6 :rem:`break` .. ------------------------------------------------------------ :rem:`|||:sec:|||`\ DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 ------------------------------------------------------------ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-003.jpg :scale: 75% :alt: # I8: 3,9 # B1: 1,2 => CTR => B1: 6 :rem:`break` ---------------------------------------------- :rem:`|||:sec:|||`\ STA # I8: 3,9 + B1: 6 ---------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-004.jpg :scale: 75% :alt: # I8: 3,9 + B1: 6 :rem:`break` ---------------------------------------------------------------------- :rem:`|||:sec:|||`\ DIS # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 ---------------------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-005.jpg :scale: 75% :alt: # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 :rem:`break` -------------------------------------------------------- :rem:`|||:sec:|||`\ STA # I8: 3,9 + B1: 6 + A2: 5,9 -------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-006.jpg :scale: 75% :alt: # I8: 3,9 + B1: 6 + A2: 5,9 :rem:`break` -------------------------------------------------------------------------------- :rem:`|||:sec:|||`\ DIS # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 -------------------------------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-007.jpg :scale: 75% :alt: # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 :rem:`break` -------------------------------------------------------------------------------- :rem:`|||:sec:|||`\ DIS # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7 -------------------------------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-008.jpg :scale: 75% :alt: # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7 :rem:`break` ------------------------------------ :rem:`|||:sec:|||`\ STA I8: 2,7 ------------------------------------ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-009.jpg :scale: 75% :alt: I8: 2,7 :rem:`break` -------------------------------------------- :rem:`|||:sec:|||`\ HYP I8: 2,7 # G7: 5 -------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-010.jpg :scale: 75% :alt: I8: 2,7 # G7: 5 :rem:`break` ------------------------------------------------------------------ :rem:`|||:sec:|||`\ DIS I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 ------------------------------------------------------------------ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-011.jpg :scale: 75% :alt: I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 :rem:`break` ------------------------------------------------------ :rem:`|||:sec:|||`\ STA I8: 2,7 # G7: 5 + G4: 1,8 ------------------------------------------------------ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-012.jpg :scale: 75% :alt: I8: 2,7 # G7: 5 + G4: 1,8 :rem:`break` ---------------------------------------------------------------------------- :rem:`|||:sec:|||`\ DIS I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6 ---------------------------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-013.jpg :scale: 75% :alt: I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6 :rem:`break` -------------------------------------------------------------- :rem:`|||:sec:|||`\ STA I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 -------------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-014.jpg :scale: 75% :alt: I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 :rem:`break` ------------------------------------------------------------------------------------ :rem:`|||:sec:|||`\ DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8 ------------------------------------------------------------------------------------ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-015.jpg :scale: 75% :alt: I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8 :rem:`break` ------------------------------------------------------------------------------------ :rem:`|||:sec:|||`\ DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9 ------------------------------------------------------------------------------------ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-016.jpg :scale: 75% :alt: I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9 :rem:`break` ---------------------------------------------- :rem:`|||:sec:|||`\ STA I8: 2,7 + G7: 3,9 ---------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-017.jpg :scale: 75% :alt: I8: 2,7 + G7: 3,9 :rem:`break` ---------------------------------------------------------- :rem:`|||:sec:|||`\ HYP I8: 2,7 + G7: 3,9 # A8: 3,4,6 ---------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-018.jpg :scale: 75% :alt: I8: 2,7 + G7: 3,9 # A8: 3,4,6 :rem:`break` -------------------------------------------------------------------------------- :rem:`|||:sec:|||`\ DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7 -------------------------------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-019.jpg :scale: 75% :alt: I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7 :rem:`break` -------------------------------------------------------------------- :rem:`|||:sec:|||`\ STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 -------------------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-020.jpg :scale: 75% :alt: I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 :rem:`break` -------------------------------------------------------------------------------------------- :rem:`|||:sec:|||`\ DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9 -------------------------------------------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-021.jpg :scale: 75% :alt: I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9 :rem:`break` ------------------------------------------------------------------------------ :rem:`|||:sec:|||`\ STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 ------------------------------------------------------------------------------ .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-022.jpg :scale: 75% :alt: I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 :rem:`break` --------------------------------------------------------------------------------- :rem:`|||:sec:|||`\ PRF I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL --------------------------------------------------------------------------------- .. figure:: _static/worlds-hardest-sudoku/xx-worlds-hardest-sudoku-work-023.jpg :scale: 75% :alt: I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL :rem:`break` .. >>CODD Conclusion .. >>CODD Appendix A .. \|:here:| .. >>CODD Notes .. ================================================== .. :rem:`|||:sec:|||`\ Footnotes .. ================================================== :html:`
` .. [#fn_bf] I am well aware, that the algorithm presented is actually called `Iterative deepening depth-first search`_ (IDDFS). However, I wish to make a specific point. IMHO IDDFS is actually a misnomer, since it places emphasis on the depth-first part instead of the more important breadth-first component. Even the Wikipedia author seem to feel the need to expand on the breadth-first nature of IDDFS (emphasis added by me): "IDDFS is *equivalent to breadth-first search*, but uses much less memory; on each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are **first visited** is *effectively breadth-first*." .. _`Iterative deepening depth-first search`: http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search .. \[#] .. >>CODD Reference List/Bibliography .. ================================================== .. :rem:`|||:sec:|||`\ References .. ================================================== .. _`World's hardest sudoku: can you crack it?`: http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html .. _`harder puzzles`: ../ .. _`tarx0119`: ../level-very-deep/xx-tarx0119-base/xx-tarx0119-base.html .. include:: doc_defs.inc .. include:: doc_defs_combined.inc .. .. \||<-snap->|| doc_standalone .. include:: doc/doc_defs_secret.inc .. \||<-snap->|| doc_standalone .. \||<-snap->|| not_doc_standalone .. include:: doc_defs_secret.inc .. \||<-snap->|| not_doc_standalone .. _`Wolfgang Scherer`: wolfgang.scherer@gmx.de