SuDoKu Analysis in Mathematica

Hagai Agmon-Snir, Israel
hagai@techie.com; agmonsnir@gmail.com

June 2005, version 1.0

In the last few weeks, SuDoKu has become very popular in Israel. Just for the fun of it, I made this notebook, in teh very few hours of spate time I found. It is enjoyable to see how easy Mathematica handles SuDoKu algorithms, including advanced logical-deduction schemes, using its various computation approaches. I used comparably straightforward Mathematica, without any aspiration of an expert. This can be used as a tool for learning Mathematica. This is not intended to be a "black-box" package. Instead, it can be used to trace the algorithms behind SudoKu analysis.
Of course, I will be delighted to get feedback and improvements. I am sure there are many things to correct and change.

Inits - examples of sudoku puzzles to be used in the examples below

sudoku=({{0, 0, 0, 0, 0, 1, 0, 8, 0}, {2, 0, 5, 6, 0, 0, 0, 0, 4}, {0, 8, 0, 7, 0, 0, 0, 3, 0}, {0, 5, 1, 0, 0, 0, 0, 9, 0}, {0, 0, 0, 0, 9, 2, 0, 0, 8}, {0, 0, 2, 5, 0, 0, 7, 0, 0}, {4, 3, 0, 0, 1, 0, 0, 0, 6}, {0, 0, 7, 9, 6, 0, 0, 4, 3}, {0, 0, 0, 0, 0, 0, 0, 0, 0}})

sudokuerror=({{0, 0, 0, 0, 0, 1, 0, 8, 0}, {2, 0, 5, 6, 0, 0, 0, 0, 4}, {0, 8, 0, 7, 0, 0, 0, 3, 0}, {0, 5, 1, 0, 0, 0, 0, 9, 0}, {0, 0, 0, 0, 9, 2, 1, 0, 8}, {0, 0, 2, 5, 0, 0, 7, 0, 0}, {4, 3, 0, 0, 1, 0, 0, 0, 6}, {0, 0, 7, 9, 6, 0, 0, 4, 3}, {0, 0, 0, 0, 0, 0, 0, 0, 0}})

sudokuillegal=({{0, 0, 0, 0, 1, 1, 0, 8, 0}, {2, 0, 5, 6, 0, 0, 0, 0, 4}, {0, 8, 0, 7, 0, 0, 0, 3, 0}, {0, 5, 1, 0, 0, 0, 0, 9, 0}, {0, 0, 0, 0, 9, 2, 1, 0, 8}, {0, 0, 2, 5, 0, 0, 7, 0, 0}, {4, 3, 0, 0, 1, 0, 0, 0, 6}, {0, 0, 7, 9, 6, 0, 0, 4, 3}, {0, 0, 0, 0, 0, 0, 0, 0, 0}})

sudoku3a=({{0, 0, 0, 0, 5, 4, 9, 0, 0}, {0, 0, 8, 2, 0, 0, 0, 7, 0}, {3, 0, 5, 0, 0, 0, 0, 0, 2}, {0, 0, 1, 0, 0, 3, 6, 8, 0}, {7, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 9, 0, 6, 1, 0, 0, 4}, {0, 0, 3, 0, 9, 8, 0, 4, 0}, {0, 0, 0, 7, 0, 0, 0, 0, 6}, {0, 5, 2, 0, 0, 0, 0, 1, 0}})

sudokujune232005=({{0, 0, 6, 0, 0, 5, 7, 0, 3}, {0, 0, 0, 4, 0, 0, 0, 8, 0}, {0, 0, 0, 9, 3, 0, 0, 0, 0}, {0, 4, 0, 0, 0, 0, 2, 0, 1}, {0, 0, 1, 0, 0, 0, 3, 0, 0}, {6, 0, 5, 0, 0, 0, 0, 4, 0}, {0, 0, 0, 0, 1, 4, 0, 0, 0}, {0, 1, 0, 0, 0, 9, 0, 0, 0}, {2, 0, 4, 3, 0, 0, 6, 0, 0}})

sudokujune242005hard=({{8, 0, 1, 9, 0, 0, 0, 0, 5}, {0, 7, 0, 0, 0, 0, 0, 6, 0}, {0, 0, 0, 5, 6, 0, 2, 0, 0}, {0, 5, 0, 0, 0, 0, 0, 0, 6}, {0, 0, 0, 4, 3, 8, 0, 0, 0}, {3, 0, 0, 0, 0, 0, 0, 9, 0}, {0, 0, 9, 0, 7, 5, 0, 0, 0}, {0, 2, 0, 0, 0, 0, 0, 7, 0}, {5, 0, 0, 0, 0, 9, 4, 0, 1}})

sudokuadvanced=({{1, 0, 0, 0, 2, 0, 0, 0, 3}, {9, 0, 0, 1, 0, 0, 0, 0, 8}, {6, 0, 0, 0, 0, 4, 0, 0, 2}, {4, 3, 0, 7, 0, 0, 0, 0, 5}, {7, 0, 2, 0, 6, 0, 4, 0, 1}, {8, 0, 0, 4, 0, 1, 0, 9, 0}, {2, 0, 0, 9, 0, 0, 0, 0, 0}, {3, 0, 0, 0, 0, 8, 0, 0, 4}, {5, 0, 0, 0, 7, 0, 0, 0, 9}})

Initial functions and preset variables

subgridanchors - a vector of anchor cells within subgrids - to be used for transforming subgrid number (1-9) into cells range

subgridanchors = {{1, 1}, {1, 4}, {1, 7}, {4, 1}, {4, 4}, {4, 7}, {7, 
          1}, {7, 4}, {7, 7}}

extract3columns[m,range] - returns selected columns of m

extract3columns[m_, range_] := Map[Take[#, range] &, m]

Examples

extract3columns[sudoku, {4, 6}]

Transpose[%]

extract3columns[%, {4, 6}]

gridcols[c] - returns range of subgrid columns for a given column

gridcols[c_] := 
Switch[
        c, 
1, {1, 3}, 
2, {1, 
          3}, 
3, {1, 3}, 
4, {4, 
          6}, 
5, {4, 6}, 
6, {4, 
          6}, 
7, {7, 9}, 
8, {7, 
          9}, 
9, {7, 9}
]

Examples

Range[gridcols[6][[1]], gridcols[6][[2]]]

subgrid[m,r,c] - returns a subgrid matrix of m that includes cell (r,c)

subgrid[m_, r_, 
        c_] := 
Transpose[
extract3columns[
Transpose[
extract3columns[
m, 
              gridcols[c]
]
], 
          gridcols[r]
]
]

Examples

subgrid[sudoku, 6, 7]

illegalvalues[m,r,c] - returns the illegal values for cell (r,c) of m (note: if (r,c) is non-empty in m - result is meaningless)

illegalvalues[m_, r_, 
        c_] := 
Intersection[
Union[
Intersection[
Union[
m[[r]]
], {1, 2, 3, 4, 5, 6, 7, 8, 
              9}
], 
Intersection[
Union[
(Transpose[
                    m])[[c]]
], {1, 2, 3, 4, 5, 6, 7, 
              8, 9}
], 
Flatten[
            subgrid[m, r, c]]
], 
{1, 2, 
          3, 4, 5, 6, 7, 8, 9}
]

Examples

illegalvalues[sudoku, 1, 2]

legalvalues[m,r,c] - returns the only legal values for cell (r,c) of m (note: if (r,c) is non-empty in m - returns an empty list)

legalvalues[m_, r_, c_] := 
If[
        m[[r, c]] == 0, 
        Complement[{1, 2, 3, 4, 5, 6, 7, 8, 
            9}, 
illegalvalues[m, r, 
            c]
], {}
]

Examples

legalvalues[sudoku, 2, 3]

subgridlegalvalues[m,r,c] - returns a matrix of the legal values for the subgrid of cell (r,c) of m (note: if a cell is non-empty in m - an empty list is provided - reflecting that there are no legalvalues)

subgridlegalvalues[m_, r_, 
        c_] := 
Module[{legalvaluestable}, 
legalvaluestable = 
          Table[legalvalues[m, r1, c1], {r1, 9}, {c1, 
              9}]; 
Transpose[
extract3columns[
Transpose[
extract3columns[
legalvaluestable, 
                gridcols[c]
]
], 
            gridcols[
              r]
]
]
]

Examples

subgridlegalvalues[sudoku, 2, 2]

Checking legality of a matrix/puzzle

rowsCheckTable[m] - return a matrix - in place (n,c) one finds how many times n appears in row c (in m)

rowsCheckTable[
        m_] := 
Table[
Table[
Count[m[[r]], n]
, {r, 
            9}
]
, {n, 
          9}
]

Examples

Length[
        Intersection[
          Union[Flatten[rowsCheckTable[sudokuerror]]], {2, 3, 4, 5, 6, 7, 8, 
            9}]] == 0

Length[
        Intersection[
          Union[Flatten[rowsCheckTable[sudokuillegal]]], {2, 3, 4, 5, 6, 7, 
            8, 9}]] == 0

colsCheckTable[m] - return a matrix - in place (n,c) one finds how many times n appears in column c (in m)

colsCheckTable[m_] := 
rowsCheckTable[
        Transpose[m]]

Examples

colsCheckTable[sudokuillegal]

Length[
        Intersection[
          Union[Flatten[colsCheckTable[sudokuerror]]], {2, 3, 4, 5, 6, 7, 8, 
            9}]] == 0

gridsCheckTable[m] - return a matrix - in place (n,g) one finds how many times n appears in subgrid g (in m)

gridsCheckTable[
        m_] := 
Table[
Table[
Count[
            Flatten[subgrid[m, subgridanchors[[g, 1]], 
                subgridanchors[[g, 2]]]], n]
, {g, 
            9}
]
, {n, 
          9}
]

Examples

gridsCheckTable[sudokuillegal]

Length[
        Intersection[
          Union[Flatten[gridsCheckTable[sudokuillegal]]], {2, 3, 4, 5, 6, 7, 
            8, 9}]] == 0

checkSudokuLegal[m] - returns True if m is legal as sudoku matrix/puzzle (some cells may be empty, e.g. = 0)

checkSudokuLegal[
        m_] := 
Length[
            Intersection[
              Union[Flatten[rowsCheckTable[m]]], {2, 3, 4, 5, 6, 7, 8, 
                9}]] == 
          0  && 
Length[
            Intersection[
              Union[Flatten[colsCheckTable[m]]], {2, 3, 4, 5, 6, 7, 8, 
                9}]] == 
          0  && 
Length[
            Intersection[
              Union[Flatten[gridsCheckTable[m]]], {2, 3, 4, 5, 6, 7, 8, 
                9}]] == 0

Examples

checkSudokuLegal[sudokuerror]

checkSudokuLegal[sudokuillegal]

Analyzing legal values in a matrix

singleCellsTable[m] - return a matrix - in place (r,c) one finds how many legal values are for empty cell (r,c) in m (note: if cell is non-empty, x is put in the matrix)

singleCellsTable[
        m_] := 
Table[
If[
m[[i, j]] == 0, Length[legalvalues[m, i, j]], 
          x
]
, {i, 1, 9}, {j, 1, 
          9}
]

Examples

singleCellsTable[sudokuerror]

singleCellsAnalysis[m,count] - return a list of the positions in m in which the number of legal values is 'count'

singleCellsAnalysis[m_, 
        count_] := 
Position[
singleCellsTable[m]
, count]

Examples

singleCellsAnalysis[sudoku, 1]

singleRowsTable[m] - return a matrix - in place (n,r) one finds how many times n occur as a legal value in row r in m (note: if n appears in row r in m, x is put in the matrix)

singleRowsTable[
        m_] := 
Table[
Table[
If[
            Count[m[[r]], n] == 0, 
Apply[
              Plus, 
Table[
                Count[legalvalues[m, r, c], n]
, {c, 
                  9}]]
, x
], {r, 
            9}
]
, {n, 
          9}
]

Examples

singleRowsTable[sudokuerror]

singleRowsAnalysis[m,count] - return a list of {n,r}-s which show what rows have 'count' occurences of n in their legalvalues

singleRowsAnalysis[m_, 
        count_] := 
Position[
singleRowsTable[m]
, count]

Examples

singleRowsAnalysis[Transpose[sudoku], 1]

singleRowsAnalysis[sudoku, 1]

singleColsTable[m] - return a matrix - in place (n,c) one finds how many times n occur as a legal value in column c in m (note: if n appears in column c in m, x is put in the matrix)

singleColsTable[m_] := 
singleRowsTable[
        Transpose[m]]

Examples

singleColsTable[sudokuerror]

singleColsAnalysis[m,count] - return a list of {n,c}-s which show what columns have 'count' occurences of n in their legalvalues

singleColsAnalysis[m_, count_] := 
singleRowsAnalysis[
        Transpose[m], count]

Examples

singleColsAnalysis[sudoku, 1]

singleGridsTable[m] - return a matrix - in place (n,g) one finds how many times n occur as a legal value in subgrid g in m (note: if n appears in subgrid g in m, x is put in the matrix)

singleGridsTable[
        m_] := 
Table[
Table[
If[
            Count[Flatten[
                  subgrid[m, subgridanchors[[g, 1]], 
                    subgridanchors[[g, 2]]]], n] == 
              0, 
Count[
              Flatten[subgridlegalvalues[m, subgridanchors[[g, 1]], 
                  subgridanchors[[g, 2]]]], n]
, 
            x
], {g, 
            9}
]
, {n, 
          9}
]

Examples

singleGridsTable[sudoku]

singleGridsTable[sudokuerror]

singleGridsAnalysis[m,count] - return a list of {n,g}-s which show what subgrids have 'count' occurences of n in their legalvalues

singleGridsAnalysis[m_, 
        count_] := 
Position[
singleGridsTable[m]
, count]

Examples

singleGridsAnalysis[sudoku, 1]

Basic checks: finding next step

singleCellsAnalysisCount1[m] - return a list of cells in which only one value is legal (each item is {r,c,legalvalue})

singleCellsAnalysisCount1[m_] := 
Map[
        Append[#, 
            First[legalvalues[
                m, #[[1]], #[[2]]]]] &, 
singleCellsAnalysis[m, 1]
]

Examples

singleCellsAnalysisCount1[sudoku]

singleRowsAnalysisCount1[m] - return a list of cells in which only one legal value is possible since this value appears only once in the legal values of the row (each item is {r,c,legalvalue})

singleRowsAnalysisCount1[
        m_] := 
Map[
Part[
            Append[#, 
Position[
                  Table[legalvalues[m, #[[2]], c1], {c1, 
                      9}], 
#[[1]]][[1, 1]]], {2, 
              3, 1}] &, 
singleRowsAnalysis[m, 
          1]
]

Examples

singleRowsAnalysisCount1[Transpose[sudoku]]

singleColsAnalysisCount1[m] - return a list of cells in which only one legal value is possible since this value appears only once in the legal values of the column (each item is {r,c,legalvalue})

singleColsAnalysisCount1[m_] := 
Map[
        Part[#, {2, 1, 3}] &, 
singleRowsAnalysisCount1[
          Transpose[m]]
]

Examples

singleColsAnalysisCount1[sudoku]

singleGridsAnalysisCount1[m] - return a list of cells in which only one legal value is possible since this value appears only once in the legal values of the subgrid (each item is {r,c,legalvalue})

singleGridsAnalysisCount1[
        m_] := 
Module[{tmp}, 
tmp = 
          Map[
Part[
                Append[#, 
Take[Position[
                        subgridlegalvalues[m, 
                          subgridanchors[[#[[2]], 1]], 
                          subgridanchors[[#[[2]], 
                              2]]], #[[1]]]
[[1]], 2]
], {2, 3, 
                  1}] &, 
singleGridsAnalysis[m, 
              1]
]; 
Map[
          Append[(subgridanchors[[#[[1]]]] + #[[2]] - {1, 
                    1}), #[[3]]] &, tmp]
]

Examples

singleGridsAnalysisCount1[sudoku]

Looking for logical contradictions in the puzzle/matrix, based on the legal values table

checkSudokuZeroOptions[m] - returns False if the list of legal values is empty for any empty cell or if a value that is still to be assigned in a structure (row, column or subgrid) does not appear in the legal values lists of the cells in the structure. This means that m has logical contradiction, hence unsolvable.

checkSudokuZeroOptions[
        m_] := 
Length[singleCellsAnalysis[m, 0]] == 
          0  && 
Length[singleRowsAnalysis[m, 0]] == 
          0  && 
Length[singleColsAnalysis[m, 0]] == 
          0  && 
Length[
            singleGridsAnalysis[m, 0]]==0

Examples

checkSudokuZeroOptions[sudokuerror]

checkSudokuZeroOptions[sudoku]

checkSudokuTwoIdenticalOptions[m] - returns False if there is are two identical legal values lists of length 1 in the same structure  (row, column or subgrid). This means that m has logical contradiction, hence unsolvable.
Six aid functions are defined, resembling the "analyzing legal values" section above. Using these functions, checkSudokuTwoIdenticalOptions is easily defined.

singleRowsTableIdenticalOptions[
        m_] := 
Table[
Table[
If[
            Count[m[[r]], n] == 0, 
Count[
              Table[legalvalues[m, r, c], {c, 9}], {n}]
, 
            x
], {r, 
            9}
]
, {n, 
          9}
]

singleRowsAnalysisIdenticalOptions[m_, 
        count_] := 
Position[
singleRowsTableIdenticalOptions[m]
, count]

singleColsTableIdenticalOptions[
        m_] := 
singleRowsTableIdenticalOptions[
        Transpose[m]]

singleColsAnalysisIdenticalOptions[m_, 
        count_] := 
Position[
singleColsTableIdenticalOptions[m]
, count]

singleGridsTableIdenticalOptions[
        m_] := 
Table[
Table[
If[
            Count[Flatten[
                  subgrid[m, subgridanchors[[g, 1]], 
                    subgridanchors[[g, 2]]]], n] == 
              0, 
Count[
              Flatten[subgridlegalvalues[m, subgridanchors[[g, 1]], 
                  subgridanchors[[g, 2]]], 1], {n}]
, 
            x
], {g, 
            9}
]
, {n, 
          9}
]

singleGridsAnalysisIdenticalOptions[m_, 
        count_] := 
Position[
singleGridsTableIdenticalOptions[m]
, count]

checkSudokuTwoIdenticalOptions[
        m_] := 
Length[
            singleRowsAnalysisIdenticalOptions[m, 2]] == 
          0  && 
Length[
            singleColsAnalysisIdenticalOptions[m, 2]] == 
          0  && 
Length[
            singleGridsAnalysisIdenticalOptions[m, 
              2]]==0

Examples

Table[
      If[sudoku[[r1, c1]] == 0, legalvalues[sudoku, r1, c1], 
        x], {r1, 9}, {c1, 9}]

checkSudokuTwoIdenticalOptions[sudoku]

singleGridsTableIdenticalOptions[sudoku]

singleRowsTableIdenticalOptions[sudoku]

singleRowsAnalysisIdenticalOptions[sudoku, 2]

singleColsTableIdenticalOptions[sudoku]

Basic Linear (with no bifurcation) Solution

solveSudokoBasic[m] - attempts to solve m - returning the solution or the final state it managed to create. Based on straightforward four simple logical-deduction ways, hence deterministic. If a solution is found, it is a unique solution and does not require advanced reasoning or bifurcations. It also prints out the process of solution. No checks are made for legality of m or whether it has logical contradictions.
Next step is not arbitrary/random - the first potential next step is taken. A simple upgrade can be to make the algorithm select a random next step out of the potential options for the four logical-deduction ways.

\(solveSudokoBasic[
        m_] := 
Module[{tmp}, 
If[
          Length[\((tmp = singleCellsAnalysisCount1[m])\)] > 
            0, 
Print["Cells ", tmp]; 
          solveSudokoBasic[
            ReplacePart[m, 
              tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                tmp[\([1, 2]\)]}]], 
If[
            Length[\((tmp = singleRowsAnalysisCount1[m])\)] > 
              0, 
Print["Rows ", tmp]; 
            solveSudokoBasic[
              ReplacePart[m, 
                tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                  tmp[\([1, 2]\)]}]], 
If[
              Length[\((tmp = singleColsAnalysisCount1[m])\)] > 
                0, 
Print["Cols ", tmp]; 
              solveSudokoBasic[
                ReplacePart[m, 
                  tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)]}]], 
If[
                Length[\((tmp = singleGridsAnalysisCount1[m])\)] > 
                  0, 
Print["Grids ", tmp]; 
                solveSudokoBasic[
                  ReplacePart[m, 
                    tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                      tmp[\([1, 
                          2]\)]}]], 
m
]
]
]
]
]\)

Examples

checkSudokuLegal[sudoku3a]

checkSudokuZeroOptions[sudoku3a]

tmptmp=solveSudokoBasic[sudoku3a]

checkSudokuLegal[sudoku]

checkSudokuZeroOptions[sudoku]

tmptmp=solveSudokoBasic[sudoku]

MatrixForm[tmptmp]

MatrixForm[sudoku]

MatrixForm[tmptmp - sudoku]

checkSudokuLegal[tmptmp]

Basic Bifurcated Solution

solveSudokoBasicBifurcated[m] - attempts (together with bifurcation[m]) to solve m - returning the solution or the final state it managed to create. In addition to the previous straightforward deterministic four simple logical-deduction ways, bifurcation is used if all these four ways fail. In this version (see a different version in the "Creating sudokus" section below), a solution is not essentially unique. The process of solution is printed out. Because the bifurcation may result in dead-ends, this method does include checks for legality of m and whether it has logical contradictions.
Next step is not arbitrary/random - the first potential next step is taken. A simple upgrade can be to make the algorithm select a random next step out of the potential options for the four logical-deduction ways.

\(\(\(
\)\(
\)\(solveSudokoBasicBifurcated[
        m_] := 
Module[{tmp}, 
If[\(! MemberQ[Flatten[m], 0]\), 
Print["Found! "]; 
          Print[MatrixForm[m]]; 
          m, 
If[\(! checkSudokuLegal[
                m]\), 
Print["Shouldn't happen - illegal matrix found!"]; Print[MatrixForm[m]]; 
            m, 
If[\(! checkSudokuZeroOptions[
                  m]\), 
Print["No way to put a number in one of the structures!"]; Print[MatrixForm[m]]; 
              m, 
If[
                Length[\((tmp = singleCellsAnalysisCount1[m])\)] > 
                  0, 
Print["Cells ", tmp]; 
                solveSudokoBasicBifurcated[
                  ReplacePart[m, 
                    tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                      tmp[\([1, 2]\)]}]], 
If[
                  Length[\((tmp = singleRowsAnalysisCount1[m])\)] > 
                    0, 
Print["Rows ", tmp]; 
                  solveSudokoBasicBifurcated[
                    ReplacePart[m, 
                      tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                        tmp[\([1, 2]\)]}]], 
If[
                    Length[\((tmp = singleColsAnalysisCount1[m])\)] > 
                      0, 
Print["Cols ", tmp]; 
                    solveSudokoBasicBifurcated[
                      ReplacePart[m, 
                        tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                          tmp[\([1, 2]\)]}]], 
If[
                      Length[\((tmp = singleGridsAnalysisCount1[m])\)] > 
                        0, 
Print["Grids ", tmp]; 
                      solveSudokoBasicBifurcated[
                        ReplacePart[m, 
                          tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                            tmp[\([1, 
                                2]\)]}]], 
If[\((tmp = 
                                bifurcation[m])\)[\([1]\)] === 
                          2, 
Print["Found! "]; 
                        Print[MatrixForm[tmp[\([2]\)]]]; 
                        tmp[\([2]\)], 
If[
                          Length[\((tmp[\([2]\)])\)] > 
                            0, 
Print["Bifurcation ", 
                            tmp]; solveSudokoBasicBifurcated[
                            ReplacePart[
                              m, \(tmp[\([2]\)]\)[\([1, 
                                  3]\)], {\(tmp[\([2]\)]\)[\([1, 
                                    1]\)], \(tmp[\([2]\)]\)[\([1, 
                                    2]\)]}]], 
m
]
]
]
]
]
]
]
]
]
]\)\)\)

bifurcation[m] - this is the bifurcation engine of the algorithm. In this version (and this can be easily improved), bifurcation is based only on cells with exactly two legal values (hence, if there aren't such cells - no bifurcation occurs).
To minimize analysis repetitions, bifurcation[m] returns a list {2,solution} if a solution is found and a list {1,alternative selection} when the first selection at the bifurcation fails. The calling function acts according to the first element of the resturning list.
Next bifurcation is not arbitrary/random - the first cell in the list of cells with two legal values is used and the first legal value in it is selected as first guess. A simple upgrade can be to make the algorithm select a random cell in the two-legal-values list and in deciding on the first guess.

\(bifurcation[
        m_] := 
Module[{tmp = singleCellsAnalysis[m, 2], 
          solution, tmplist}, \  (*\ 
          singleCellsAnalysis[m, 2]\ lists\ the\ positions\ of\ non - 
            empty\ cells\ cells\ with\ exactly\ two\ legal\ values\ *) 
If[
          Length[tmp] > 0, 
tmplist = 
            List[List[tmp[\([1, 1]\)], 
                tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                    tmp[\([1, 
                        2]\)]]\)[\([1]\)]]]; 
Print["Checking Bifurcation with ", 
            tmplist]; 
If[
            MemberQ[Flatten[\((solution = 
                    solveSudokoBasicBifurcated[
                      ReplacePart[
                        m, \(legalvalues[m, tmp[\([1, 1]\)], 
                            tmp[\([1, 2]\)]]\)[\([1]\)], {tmp[\([1, 1]\)], 
                          tmp[\([1, 2]\)]}]])\)], 
              0], 
\((tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([2]\)]]]; 
Print["alternative guess chosen ", 
                tmplist]; 
List[1, 
                tmplist])\), 
\((tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([1]\)]]]; 
Print["first guess chosen ", 
                tmplist]; 
List[2, 
                solution])\)
], {1, {}}
]
]\)

Examples

solveSudokoBasic[sudoku]

tmptmp = solveSudokoBasicBifurcated[sudoku]

MatrixForm[tmptmp]

MatrixForm[sudoku]

MatrixForm[tmptmp - sudoku]

checkSudokuLegal[tmptmp]

Advanced Linear (with no bifurcation) Solution

advancedAnalysis[m] - an advanced analysis method that checks for each cell that has exactly two legal values, the consequences of choosing one of these values. It simulates assigning the cell each of the two legal values and then tests the resulting matrix: 1. whether there is a structure in which there is no way to put one of the un-assigned values; 2. whether there is a structure that has two cells that have the same only one legal value. These tests may show a logical contradiction, and in this case, the alternative legal value may be logically assigned to the cell.
Next step is not arbitrary/random - the first potential next step is taken, once a legal value is elimintated in any of the two-legal-values cells. A simple upgrade can be to make the algorithm select a random next step out of the potential options for the analysis.

advancedAnalysis[
        m_] := 
Module[{tmp = singleCellsAnalysis[m, 2], i, 
          m1, returnvalue}, 
returnvalue = {}; 
For[i = 1,  
          i ≤  
            Length[tmp], i++, {
m1 = 
ReplacePart[
                m, legalvalues[m, tmp[[i, 1]], 
                    tmp[[i, 
                        2]]][[1]], 
{tmp[[i, 
                      1]], tmp[[i, 
                      2]]}]; 
If[((! checkSudokuTwoIdenticalOptions[m1])  ||  (! checkSudokuZeroOptions[
                        m1])), {returnvalue = 
                  List[List[tmp[[i, 1]], 
                      tmp[[i, 2]], legalvalues[m, tmp[[i, 1]], 
                          tmp[[i, 2]]][[2]]]]; 
                Break[]}]; 
m1 = 
ReplacePart[
                m, legalvalues[m, tmp[[i, 1]], 
                    tmp[[i, 
                        2]]][[2]], 
{tmp[[i, 
                      1]], tmp[[i, 
                      2]]}]; 
If[((! checkSudokuTwoIdenticalOptions[m1])  ||  (! checkSudokuZeroOptions[
                        m1])), {returnvalue = 
                  List[List[tmp[[i, 1]], 
                      tmp[[i, 2]], legalvalues[m, tmp[[i, 1]], 
                          tmp[[i, 2]]][[1]]]]; 
                Break[];}];
}]; 
returnvalue
]

Examples

advancedAnalysis[sudokuadvanced]

solveSudokoAdvanced[m] - using advanced logical analysis when attempts to solve m - returning the solution or the final state it managed to create. Based on straightforward five logical-deduction ways, hence deterministic. If a solution is found, it is a unique solution and does not require bifurcations. It also prints out the process of solution. No checks are made for legality of m or whether it has logical contradictions.
Next step is not arbitrary/random - the first potential next step is taken. A simple upgrade can be to make the algorithm select a random next step out of the potential options for the five logical-deduction ways.

\(solveSudokoAdvanced[
        m_] := 
Module[{tmp}, 
If[
          Length[\((tmp = singleCellsAnalysisCount1[m])\)] > 
            0, 
Print["Cells ", tmp]; 
          solveSudokoAdvanced[
            ReplacePart[m, 
              tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                tmp[\([1, 2]\)]}]], 
If[
            Length[\((tmp = singleRowsAnalysisCount1[m])\)] > 
              0, 
Print["Rows ", tmp]; 
            solveSudokoAdvanced[
              ReplacePart[m, 
                tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                  tmp[\([1, 2]\)]}]], 
If[
              Length[\((tmp = singleColsAnalysisCount1[m])\)] > 
                0, 
Print["Cols ", tmp]; 
              solveSudokoAdvanced[
                ReplacePart[m, 
                  tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)]}]], 
If[
                Length[\((tmp = singleGridsAnalysisCount1[m])\)] > 
                  0, 
Print["Grids ", tmp]; 
                solveSudokoAdvanced[
                  ReplacePart[m, 
                    tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                      tmp[\([1, 2]\)]}]], 
If[
                  Length[\((tmp = advancedAnalysis[m])\)] > 
                    0, 
Print["Advanced ", tmp]; 
                  solveSudokoAdvanced[
                    ReplacePart[m, 
                      tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]}]], 
m
]
]
]
]
]
]\)

Examples

examples

sudokujune242005hard

checkSudokuLegal[sudokujune242005hard]

checkSudokuZeroOptions[sudokujune242005hard]

checkSudokuTwoIdenticalOptions[sudokujune242005hard]

solveSudokoAdvanced[sudokujune242005hard]

MatrixForm[%]

checkSudokuLegal[sudokujune232005]

checkSudokuZeroOptions[sudokujune232005]

checkSudokuTwoIdenticalOptions[sudokujune232005]

solveSudokoAdvanced[sudokujune232005]

solveSudokoAdvanced[sudoku]

Advanced Bifurcated Solution

solveSudokoAdvancedBifurcated[m] - adding the advanced analysis above, attempts (together with bifurcationAdvanced[m]) to solve m - returning the solution or the final state it managed to create. In addition to the straightforward deterministic five logical-deduction ways, bifurcation is used if all these five ways fail. In this version (see a different version in the "Creating sudokus" section below), a solution is not essentially unique. The process of solution is printed out. Because the bifurcation may result in dead-ends, this method does include checks for legality of m and whether it has logical contradictions.
Next step is not arbitrary/random - the first potential next step is taken. A simple upgrade can be to make the algorithm select a random next step out of the potential options for the five logical-deduction ways.

\(\(\(
\)\(
\)\(solveSudokoAdvancedBifurcated[
        m_] := 
Module[{tmp}, 
If[\(! MemberQ[Flatten[m], 0]\), 
Print["Found! "]; 
          Print[MatrixForm[m]]; 
          m, 
If[\(! checkSudokuLegal[
                m]\), 
Print["Shouldn't happen - illegal matrix found!"]; Print[MatrixForm[m]]; 
            m, 
If[\(! checkSudokuZeroOptions[
                  m]\), 
Print["No way to put a number in one of the structures!"]; Print[MatrixForm[m]]; 
              m, 
If[
                Length[\((tmp = singleCellsAnalysisCount1[m])\)] > 
                  0, 
Print["Cells ", tmp]; 
                solveSudokoAdvancedBifurcated[
                  ReplacePart[m, 
                    tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                      tmp[\([1, 2]\)]}]], 
If[
                  Length[\((tmp = singleRowsAnalysisCount1[m])\)] > 
                    0, 
Print["Rows ", tmp]; 
                  solveSudokoAdvancedBifurcated[
                    ReplacePart[m, 
                      tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                        tmp[\([1, 2]\)]}]], 
If[
                    Length[\((tmp = singleColsAnalysisCount1[m])\)] > 
                      0, 
Print["Cols ", tmp]; 
                    solveSudokoAdvancedBifurcated[
                      ReplacePart[m, 
                        tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                          tmp[\([1, 2]\)]}]], 
If[
                      Length[\((tmp = singleGridsAnalysisCount1[m])\)] > 
                        0, 
Print["Grids ", tmp]; 
                      solveSudokoAdvancedBifurcated[
                        ReplacePart[m, 
                          tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                            tmp[\([1, 2]\)]}]], 
If[
                        Length[\((tmp = advancedAnalysis[m])\)] > 
                          0, 
Print["Advanced ", tmp]; 
                        solveSudokoAdvancedBifurcated[
                          ReplacePart[m, 
                            tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                              tmp[\([1, 
                                  2]\)]}]], 
If[\((tmp = 
                                  bifurcationAdvanced[m])\)[\([1]\)] === 
                            2, 
Print["Found! "]; 
                          Print[MatrixForm[tmp[\([2]\)]]]; 
                          tmp[\([2]\)], 
If[
                            Length[\((tmp[\([2]\)])\)] > 
                              0, 
Print["Bifurcation ", 
                              tmp]; 
                            solveSudokoAdvancedBifurcated[
                              ReplacePart[
                                m, \(tmp[\([2]\)]\)[\([1, 
                                    3]\)], {\(tmp[\([2]\)]\)[\([1, 
                                      1]\)], \(tmp[\([2]\)]\)[\([1, 
                                      2]\)]}]], 
m
]
]
]
]
]
]
]
]
]
]
]\)\)\)

bifurcationAdvanced[m] - adaptation of bifurcation[m] to the advanced analysis bifurcation procedure. No important difference, except that this function calls solveSudokoAdvancedBifurcated instad of solveSudokoBasicBifurcated.

\(bifurcationAdvanced[
        m_] := 
Module[{tmp = singleCellsAnalysis[m, 2], 
          solution, tmplist}, \  (*\ 
          singleCellsAnalysis[m, 2]\ lists\ the\ positions\ of\ non - 
            empty\ cells\ cells\ with\ exactly\ two\ legal\ values\ *) 
If[
          Length[tmp] > 0, 
tmplist = 
            List[List[tmp[\([1, 1]\)], 
                tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                    tmp[\([1, 
                        2]\)]]\)[\([1]\)]]]; 
Print["Checking Bifurcation with ", 
            tmplist]; 
If[
            MemberQ[Flatten[\((solution = 
                    solveSudokoAdvancedBifurcated[
                      ReplacePart[
                        m, \(legalvalues[m, tmp[\([1, 1]\)], 
                            tmp[\([1, 2]\)]]\)[\([1]\)], {tmp[\([1, 1]\)], 
                          tmp[\([1, 2]\)]}]])\)], 
              0], 
\((tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([2]\)]]]; 
Print["alternative guess chosen ", 
                tmplist]; 
List[1, 
                tmplist])\), 
\((tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([1]\)]]]; 
Print["first guess chosen ", 
                tmplist]; 
List[2, 
                solution])\)
], {1, {}}
]
]\)

examples

solveSudokoAdvancedBifurcated[sudokujune232005]

solveSudokoAdvancedBifurcated[sudoku]

Creating Sudokus

Part 1: createSudoku[ ] - creating a legal sudoku matrix.
The method here to create the matrix is simple: we create first three rows, transpose the matrix and create again three first rows. Then we add (with caution) the fourth row. Whenever adding lines fails, the procedure gets back and retry. Statistically, rarely this process does not succeed. 
Assuming this phase has succeeded, the resultant matrix is then used as an input to the basic bifurcating algorithm and usually this results a legal full sudoku matrix. If not, we can always try again. BTW, transposing and adding a fourth line to the transposed matrix often yields unsolvable matrix. We added some printouts to track the process - these can be easily deleted.
Two aid functions are defined for the process.

randompermutation[
        set_] := Permutations[
          set][[Random[
            Integer, {1, Length[Permutations[set]]}]]]

restoptions[set_] := 
      Complement[{1, 2, 3, 4, 5, 6, 7, 8, 9}, set]

Off[General::spell] (* just to stop the warning beeps in defining "createSudoku" *)

Off[General::spell1]

\(\(\(createSudoku[] := 
Module[{line1, line2, line3, 
          line2a, line2b, line2c, line3a, line3b, line3c, i, j = 0, 
          okFlag = False, sudoku1, 
          sudoku2}, 
While[\((\((\(! okFlag\))\)\  && \ \((\((\(j++\))\) < 100)\))\), {
line1 = 
                randompermutation[{1, 2, 3, 4, 5, 6, 7, 8, 
                    9}]; 
i = 0; \ line2c = {}; 
              While[\((\((\((\(i++\))\) < 100)\)\  && \ \((Length[line2c] < 
                        3)\))\), {
line2a = 
                    Take[randompermutation[
                        restoptions[Take[line1, {1, 3}]]], {1, 
                        3}]; 
line2b = 
                    Take[randompermutation[
                        restoptions[Union[Take[line1, {4, 6}], line2a]]], {1, 
                        3}]; 
line2c = 
                    randompermutation[
                      restoptions[
                        Union[Take[line1, {7, 9}], line2a, 
                          line2b]]];
}]; 
If[i ≥ 100, 
                Continue[{}]]; 
i = 0; \ line3c = {}; 
              While[\((\((\((\(i++\))\) < 100)\)\  && \ \((Length[line3c] < 
                        3)\))\), {
line3a = 
                    randompermutation[
                      restoptions[
                        Union[Take[line1, {1, 3}], 
                          line2a]]]; 
line3b = 
                    randompermutation[
                      restoptions[
                        Union[Take[line1, {4, 6}], line2b, 
                          line3a]]]; 
line3c = 
                    randompermutation[
                      restoptions[
                        Union[Take[line1, {7, 9}], line2c, line3a, 
                          line3b]]];
}]; 
If[i ≥ 100, 
                Continue[{}]]; 
sudoku1 = 
                Table[Table[
                    0, {r, 9}, {c, 
                      9}]
]; 
sudoku1 = 
                ReplacePart[sudoku1, line1, 1]; 
line2 = 
                Join[line2a, line2b, line2c]; 
line3 = 
                Join[line3a, line3b, line3c]; 
sudoku1 = 
                ReplacePart[sudoku1, line2, 2]; 
sudoku1 = 
                ReplacePart[sudoku1, line3, 3]; 
sudoku1 = 
                Transpose[sudoku1]; 
line1 = 
                Join[Take[sudoku1[\([1]\)], {1, 3}], 
                  Take[randompermutation[
                      restoptions[Take[sudoku1[\([1]\)], {1, 3}]]], {1, 
                      6}]]; 
i = 0; \ line2c = {}; 
              While[\((\((\((\(i++\))\) < 100)\)\  && \ \((Length[line2c] < 
                        3)\))\), {
line2a = 
                    Take[sudoku1[\([2]\)], {1, 
                        3}]; 
line2b = 
                    Take[randompermutation[
                        restoptions[Union[Take[line1, {4, 6}], line2a]]], {1, 
                        3}]; 
line2c = 
                    randompermutation[
                      restoptions[
                        Union[Take[line1, {7, 9}], line2a, 
                          line2b]]];
}]; 
If[i ≥ 100, 
                Continue[{}]]; 
i = 0; \ line3c = {}; 
              While[\((\((\((\(i++\))\) < 100)\)\  && \ \((Length[line3c] < 
                        3)\))\), {
line3a = 
                    Take[sudoku1[\([3]\)], {1, 
                        3}]; 
line3b = 
                    randompermutation[
                      restoptions[
                        Union[Take[line1, {4, 6}], line2b, 
                          line3a]]]; 
line3c = 
                    randompermutation[
                      restoptions[
                        Union[Take[line1, {7, 9}], line2c, line3a, 
                          line3b]]];
}]; 
If[i ≥ 100, 
                Continue[{}]]; 
okFlag = 
                True;
}]
If[
            j ≥ 10, {Return[{}]}]; 
sudoku1 = 
          ReplacePart[sudoku1, line1, 1]; 
line2 = 
          Join[line2a, line2b, line2c]; 
line3 = 
          Join[line3a, line3b, line3c]; 
sudoku1 = 
          ReplacePart[sudoku1, line2, 2]; 
sudoku1 = 
          ReplacePart[sudoku1, line3, 
            3]; 
Print["End of phase 1"]; 
Print[
          MatrixForm[
            sudoku1]]; 
Print["is the matrix legal? - ", checkSudokuLegal[sudoku1]]; 
okFlag = False; 
        j = 0; 
While[\((\((\(! okFlag\))\)\  && \ \((\((\(j++\))\) < 10)\))\), {
sudoku2 = sudoku1; 
            sudokutmp1243 = sudoku2; 
If[
              Length[legalvalues[sudoku2, 4, 4]] == 0, Continue[], 
              sudoku2 = 
                ReplacePart[
                  sudoku2, \(legalvalues[sudoku2, 4, 
                      4]\)[\([Random[
                        Integer, {1, 
                          Length[legalvalues[sudoku2, 4, 4]]}]]\)], {4, 
                    4}]]; 
If[
              Length[legalvalues[sudoku2, 4, 5]] == 0, Continue[], 
              sudoku2 = 
                ReplacePart[
                  sudoku2, \(legalvalues[sudoku2, 4, 
                      5]\)[\([Random[
                        Integer, {1, 
                          Length[legalvalues[sudoku2, 4, 5]]}]]\)], {4, 
                    5}]]; 
If[
              Length[legalvalues[sudoku2, 4, 6]] == 0, Continue[], 
              sudoku2 = 
                ReplacePart[
                  sudoku2, \(legalvalues[sudoku2, 4, 
                      6]\)[\([Random[
                        Integer, {1, 
                          Length[legalvalues[sudoku2, 4, 6]]}]]\)], {4, 
                    6}]]; 
If[
              Length[legalvalues[sudoku2, 4, 7]] == 0, Continue[], 
              sudoku2 = 
                ReplacePart[
                  sudoku2, \(legalvalues[sudoku2, 4, 
                      7]\)[\([Random[
                        Integer, {1, 
                          Length[legalvalues[sudoku2, 4, 7]]}]]\)], {4, 
                    7}]]; 
If[
              Length[legalvalues[sudoku2, 4, 8]] == 0, Continue[], 
              sudoku2 = 
                ReplacePart[
                  sudoku2, \(legalvalues[sudoku2, 4, 
                      8]\)[\([Random[
                        Integer, {1, 
                          Length[legalvalues[sudoku2, 4, 8]]}]]\)], {4, 
                    8}]]; 
If[
              Length[legalvalues[sudoku2, 4, 9]] == 0, Continue[], 
              sudoku2 = 
                ReplacePart[
                  sudoku2, \(legalvalues[sudoku2, 4, 
                      9]\)[\([Random[
                        Integer, {1, 
                          Length[legalvalues[sudoku2, 4, 9]]}]]\)], {4, 
                    9}]]; 
okFlag = 
              True
}]; 
If[
          j ≥ 10, 
          Return[{}]]; 
Print["End of phase 2"]; 
Print[
          MatrixForm[
            sudoku2]]; 
Print["is the matrix legal? - ", checkSudokuLegal[sudoku2]]; 
sudoku1 = 
          solveSudokoBasicBifurcated[
            sudoku2]; 
Print["End of phase 3"]; 
Print[
          MatrixForm[
            sudoku1]]; 
Print["is the matrix legal? - ", checkSudokuLegal[
            sudoku1]]; 
sudoku1
]\)\(
\)
    \)\)

On[General::spell]

On[General::spell1]

Examples

fullsudoku = createSudoku[]

Part 2: creating a legal sudoku puzzle.
There are many ways to create the puzzle from the matrix. In the current version, we use a pattern to select the cells in the puzzle. The pattern can be predefined or be created by randomly pick predecided number of cells (generally or in each subgrid), etc. (practically this means creating a random pattern). If the resulting puzzle is not solved, the pattern and/or the matrix should be changed (this iteration can be easily automated).
The main issue is uniqueness. We add here another version of the bifurcating algorithms in which, if a bifurcation occurs, the two options are checked and the uniqueness can be tested.
Potential future easy improvements: 1. automatic creation of the puzzle (in "one shift-return"); 2. computer answer with regard to uniqueness; 3. checking all potential two-legal-values-cells in bifurcations and looking for a cell in which the path to contradicion is shorter (making it easier for a human solver to find the contradiction).
This part just gives a few initial examples for application. There are many other ways to use the notebook for creating sudoku puzzles.

A version of the bifurcating algorithms that allows (the human reading the printout) to check uniquenss of the solution.

\(\(\(
\)\(
\)\(solveSudokoBasicBifurcatedCheckTwo[
        m_] := 
Module[{tmp}, 
If[\(! MemberQ[Flatten[m], 0]\), 
Print["Found! "]; 
          Print[MatrixForm[m]]; 
          m, 
If[\(! checkSudokuLegal[
                m]\), 
Print["Shouldn't happen - illegal matrix found!"]; Print[MatrixForm[m]]; 
            m, 
If[\(! checkSudokuZeroOptions[
                  m]\), 
Print["No way to put a number in one of the structures!"]; Print[MatrixForm[m]]; 
              m, 
If[
                Length[\((tmp = singleCellsAnalysisCount1[m])\)] > 
                  0, 
Print["Cells ", tmp]; 
                solveSudokoBasicBifurcatedCheckTwo[
                  ReplacePart[m, 
                    tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                      tmp[\([1, 2]\)]}]], 
If[
                  Length[\((tmp = singleRowsAnalysisCount1[m])\)] > 
                    0, 
Print["Rows ", tmp]; 
                  solveSudokoBasicBifurcatedCheckTwo[
                    ReplacePart[m, 
                      tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                        tmp[\([1, 2]\)]}]], 
If[
                    Length[\((tmp = singleColsAnalysisCount1[m])\)] > 
                      0, 
Print["Cols ", tmp]; 
                    solveSudokoBasicBifurcatedCheckTwo[
                      ReplacePart[m, 
                        tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                          tmp[\([1, 2]\)]}]], 
If[
                      Length[\((tmp = singleGridsAnalysisCount1[m])\)] > 
                        0, 
Print["Grids ", tmp]; 
                      solveSudokoBasicBifurcatedCheckTwo[
                        ReplacePart[m, 
                          tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                            tmp[\([1, 
                                2]\)]}]], 
If[\((tmp = 
                                bifurcationCheckTwo[m])\)[\([1]\)] === 
                          2, 
Print["Found! "]; 
                        Print[MatrixForm[tmp[\([2]\)]]]; 
                        tmp[\([2]\)], 
If[
                          Length[\((tmp[\([2]\)])\)] > 
                            0, 
Print["Bifurcation ", 
                            tmp]; solveSudokoBasicBifurcatedCheckTwo[
                            ReplacePart[
                              m, \(tmp[\([2]\)]\)[\([1, 
                                  3]\)], {\(tmp[\([2]\)]\)[\([1, 
                                    1]\)], \(tmp[\([2]\)]\)[\([1, 
                                    2]\)]}]], 
m
]
]
]
]
]
]
]
]
]
]\)\)\)

\(bifurcationCheckTwo[
        m_] := 
Module[{tmp = singleCellsAnalysis[m, 2], 
          solution, tmplist}, \  (*\ 
          singleCellsAnalysis[m, 2]\ lists\ the\ positions\ of\ non - 
            empty\ cells\ cells\ with\ exactly\ two\ legal\ values\ *) 
If[
          Length[tmp] > 0, 
tmplist = 
            List[List[tmp[\([1, 1]\)], 
                tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                    tmp[\([1, 
                        2]\)]]\)[\([1]\)]]]; 
Print["Checking Bifurcation with first guess", 
            tmplist]; 
If[
            MemberQ[Flatten[\((solution = 
                    solveSudokoBasicBifurcatedCheckTwo[
                      ReplacePart[
                        m, \(legalvalues[m, tmp[\([1, 1]\)], 
                            tmp[\([1, 2]\)]]\)[\([1]\)], {tmp[\([1, 1]\)], 
                          tmp[\([1, 2]\)]}]])\)], 
              0], 
\((tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([1]\)]]]; 
Print["first guess was mistaken ", 
                tmplist]; 
tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([2]\)]]]; 
Print["Checking Bifurcation with second guess", 
                tmplist]; 
List[1, 
                tmplist])\), 
\((tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([1]\)]]]; 
Print["first guess was correct ", 
                tmplist]; 
tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([2]\)]]]; 
Print["Checking Bifurcation with second guess", 
                tmplist]; 
List[1, 
                tmplist])\)
], {1, {}}
]
]\)

\(\(\(
\)\(
\)\(solveSudokoAdvancedBifurcatedCheckTwo[
        m_] := 
Module[{tmp}, 
If[\(! MemberQ[Flatten[m], 0]\), 
Print["Found! "]; 
          Print[MatrixForm[m]]; 
          m, 
If[\(! checkSudokuLegal[
                m]\), 
Print["Shouldn't happen - illegal matrix found!"]; Print[MatrixForm[m]]; 
            m, 
If[\(! checkSudokuZeroOptions[
                  m]\), 
Print["No way to put a number in one of the structures!"]; Print[MatrixForm[m]]; 
              m, 
If[
                Length[\((tmp = singleCellsAnalysisCount1[m])\)] > 
                  0, 
Print["Cells ", tmp]; 
                solveSudokoAdvancedBifurcatedCheckTwo[
                  ReplacePart[m, 
                    tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                      tmp[\([1, 2]\)]}]], 
If[
                  Length[\((tmp = singleRowsAnalysisCount1[m])\)] > 
                    0, 
Print["Rows ", tmp]; 
                  solveSudokoAdvancedBifurcatedCheckTwo[
                    ReplacePart[m, 
                      tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                        tmp[\([1, 2]\)]}]], 
If[
                    Length[\((tmp = singleColsAnalysisCount1[m])\)] > 
                      0, 
Print["Cols ", tmp]; 
                    solveSudokoAdvancedBifurcatedCheckTwo[
                      ReplacePart[m, 
                        tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                          tmp[\([1, 2]\)]}]], 
If[
                      Length[\((tmp = singleGridsAnalysisCount1[m])\)] > 
                        0, 
Print["Grids ", tmp]; 
                      solveSudokoAdvancedBifurcatedCheckTwo[
                        ReplacePart[m, 
                          tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                            tmp[\([1, 2]\)]}]], 
If[
                        Length[\((tmp = advancedAnalysis[m])\)] > 
                          0, 
Print["Advanced ", tmp]; 
                        solveSudokoAdvancedBifurcatedCheckTwo[
                          ReplacePart[m, 
                            tmp[\([1, 3]\)], {tmp[\([1, 1]\)], 
                              tmp[\([1, 
                                  2]\)]}]], 
If[\((tmp = 
                                  bifurcationAdvancedCheckTwo[m])\)[\([1]\)] === 
                            2, 
Print["Found! "]; 
                          Print[MatrixForm[tmp[\([2]\)]]]; 
                          tmp[\([2]\)], 
If[
                            Length[\((tmp[\([2]\)])\)] > 
                              0, 
Print["Bifurcation ", 
                              tmp]; solveSudokoAdvancedBifurcatedCheckTwo[
                              ReplacePart[
                                m, \(tmp[\([2]\)]\)[\([1, 
                                    3]\)], {\(tmp[\([2]\)]\)[\([1, 
                                      1]\)], \(tmp[\([2]\)]\)[\([1, 
                                      2]\)]}]], 
m
]
]
]
]
]
]
]
]
]
]
]\)\)\)

\(bifurcationAdvancedCheckTwo[
        m_] := 
Module[{tmp = singleCellsAnalysis[m, 2], 
          solution, tmplist}, \  (*\ 
          singleCellsAnalysis[m, 2]\ lists\ the\ positions\ of\ non - 
            empty\ cells\ cells\ with\ exactly\ two\ legal\ values\ *) 
If[
          Length[tmp] > 0, 
tmplist = 
            List[List[tmp[\([1, 1]\)], 
                tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                    tmp[\([1, 
                        2]\)]]\)[\([1]\)]]]; 
Print["Checking Bifurcation with first guess", 
            tmplist]; 
If[
            MemberQ[Flatten[\((solution = 
                    solveSudokoAdvancedBifurcatedCheckTwo[
                      ReplacePart[
                        m, \(legalvalues[m, tmp[\([1, 1]\)], 
                            tmp[\([1, 2]\)]]\)[\([1]\)], {tmp[\([1, 1]\)], 
                          tmp[\([1, 2]\)]}]])\)], 
              0], 
\((tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([1]\)]]]; 
Print["first guess was mistaken ", 
                tmplist]; 
tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([2]\)]]]; 
Print["Checking Bifurcation with second guess", 
                tmplist]; 
List[1, 
                tmplist])\), 
\((tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([1]\)]]]; 
Print["first guess was correct ", 
                tmplist]; 
tmplist = 
                List[List[tmp[\([1, 1]\)], 
                    tmp[\([1, 2]\)], \(legalvalues[m, tmp[\([1, 1]\)], 
                        tmp[\([1, 
                            2]\)]]\)[\([2]\)]]]; 
Print["Checking Bifurcation with second guess", 
                tmplist]; 
List[1, 
                tmplist])\)
], {1, {}}
]
]\)

Examples

pattern=({{0, 1, 0, 1, 0, 1, 0, 1, 0}, {1, 1, 0, 0, 1, 0, 0, 1, 1}, {0, 0, 1, 0, 1, 0, 1, 0, 0}, {1, 0, 0, 0, 1, 0, 0, 0, 1}, {0, 1, 1, 1, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 1, 0, 1, 0, 1, 0, 0}, {1, 1, 0, 0, 1, 0, 0, 1, 1}, {0, 1, 0, 1, 0, 1, 0, 1, 0}})

MatrixForm[pattern /.  0 -> " "]

fullsudoku = createSudoku[]

fullsudoku = {{2, 9, 3, 8, 6, 4, 5, 1, 7}, {7, 8, 1, 5, 2, 3, 4, 6, 
          9}, {5, 4, 6, 7, 9, 1, 2, 8, 3}, {3, 5, 2, 4, 1, 6, 9, 7, 8}, {9, 
          7, 8, 2, 3, 5, 1, 4, 6}, {6, 1, 4, 9, 7, 8, 3, 2, 5}, {8, 2, 7, 1, 
          5, 9, 6, 3, 4}, {4, 3, 5, 6, 8, 2, 7, 9, 1}, {1, 6, 9, 3, 4, 7, 8, 
          5, 2}}

MatrixForm[fullsudoku*pattern]

fullsudokusolution = 
      solveSudokoBasicBifurcatedCheckTwo[fullsudoku*pattern]

MatrixForm[%]

fullsudokusolution - fullsudoku

solved = {0};
fullsudoku = createSudoku[];
\(\(While[
        MemberQ[Flatten[solved], 
          0], 
Print["Selecting random pattern and checking whether the result is solvable"]; 
randompattern = Table[0, {r, 9}, {c, 9}]; 
placeslist = 
          Flatten[Table[{r, c}, {r, 9}, {c, 9}], 1]; 
For[
          i = 0, i < 
            36, \(i++\), {
randomplace = 
              Random[Integer, {1, 
                  Length[placeslist]}]; 
randompattern = 
              ReplacePart[randompattern, 1, 
                placeslist[\([randomplace]\)]]; 
placeslist = Drop[placeslist, {randomplace}];
}]; 
solved = 
          solveSudokoAdvanced[
            fullsudoku*
              randompattern]
];\)\)
Print["found a solvable sudoku puzzle"];

MatrixForm[solved]

solved - fullsudoku

MatrixForm[solved*randompattern]

MatrixForm[% /.  0 -> " "]

patternThirds=({{1, 0, 1, 0, 1, 0, 1, 0, 1}, {0, 1, 0, 1, 1, 1, 0, 1, 0}, {1, 0, 1, 0, 1, 0, 1, 0, 1}, {0, 1, 0, 1, 1, 1, 0, 1, 0}, {1, 1, 1, 1, 0, 1, 1, 1, 1}, {0, 1, 0, 1, 1, 1, 0, 1, 0}, {1, 0, 1, 0, 1, 0, 1, 0, 1}, {0, 1, 0, 1, 1, 1, 0, 1, 0}, {1, 0, 1, 0, 1, 0, 1, 0, 1}})

MatrixForm[patternThirds /.  0 -> " "]

fullsudoku = createSudoku[]

solveSudokoBasicBifurcatedCheckTwo[fullsudoku*patternThirds]