From Puzzles to Graphs: Coloring Your Way Through Sudoku

Alejandra Ortiz Duran

SUDOKU Puzzle

In Sudoku, you fill a 9×9 grid with numbers 1 to 9 so that every row, column, and 3×3 box has each number only once.

SlideView[{Grid[ConstantArray[" ",{9,9}],Frame->All,Spacings->{1.4,1}],

Grid[Partition[ToString[#]&/@Range[81],9],Frame->All,Dividers->{Thread[{4,7}->Directive[Thickness[2]]],Thread[{4,7}->Directive[Thickness[2]]]},Spacings->{.8,1}],

Grid[Partition[ToString[#]&/@Range[81],9],Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{.8,1}],

Grid[ConstantArray[" ",{9,9}],Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1}],Grid[ConstantArray[" ",{9,9}],Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{},{2->ColorData[97,"ColorList"][[1]]}}]  ,

Grid[{{" "," "," "," "," "," "," "," "," "},{"1","2","3","4","5","6","7","8","9"},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{},{2->ColorData[97,"ColorList"][[1]]}}] ,


Grid[{{" "," "," "," "," "," "," "," "," "},{"7","3","2","9","1","6","5","8","4"},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{},{2->ColorData[97,"ColorList"][[1]]}}] ,

Grid[ConstantArray[" ",{9,9}],Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{2->ColorData[97,"ColorList"][[1]]},{}}] ,
Grid[{{" ","1"," "," "," "," "," "," "," "},{" ","2"," "," "," "," "," "," "," "},{" ","3"," "," "," "," "," "," "," "},{" ","4"," "," "," "," "," "," "," "},{" ","5"," "," "," "," "," "," "," "},{" ","6"," "," "," "," "," "," "," "},{" ","7"," "," "," "," "," "," "," "},{" ","8"," "," "," "," "," "," "," "},{" ","9"," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{2->ColorData[97,"ColorList"][[1]]},{}}] ,


Grid[{{" ","6"," "," "," "," "," "," "," "},{" ","5"," "," "," "," "," "," "," "},{" ","9"," "," "," "," "," "," "," "},{" ","4"," "," "," "," "," "," "," "},{" ","2"," "," "," "," "," "," "," "},{" ","1"," "," "," "," "," "," "," "},{" ","8"," "," "," "," "," "," "," "},{" ","7"," "," "," "," "," "," "," "},{" ","3"," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{2->ColorData[97,"ColorList"][[1]]},{}}] ,

Grid[ConstantArray[" ",{9,9}],Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{None,None,{{{1,3},{1,3}}->ColorData[97,"ColorList"][[1]]}}] ,

Grid[{{"1","2","3"," "," "," "," "," "," "},{"4","5","6"," "," "," "," "," "," "},{"7","8","9"," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{None,None,{{{1,3},{1,3}}->ColorData[97,"ColorList"][[1]]}}] ,

Grid[{
{"4","9","6"," "," "," "," "," "," "},
{"1","8","3"," "," "," "," "," "," "},{"7","5","2"," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{None,None,{{{1,3},{1,3}}->ColorData[97,"ColorList"][[1]]}}] ,

Grid[{{" "," "," "," "," "," "," "," "," "},{"7","8","2","9","1","6","5","8","4"},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{},{2->ColorData[97,"ColorList"][[1]]},{{2,2}->ColorData[97,"ColorList"][[4]],{2,8}->ColorData[97,"ColorList"][[4]]}}],

Show[Rasterize[Grid[{{" "," "," "," "," "," "," "," "," "},{"7","8","2","9","1","6","5","8","4"},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{},{2->ColorData[97,"ColorList"][[1]]},{{2,2}->ColorData[97,"ColorList"][[4]],{2,8}->ColorData[97,"ColorList"][[4]]}}],"Image",ImageSize->237],Graphics[{Red,Circle[{80,380},20],Circle[{392,380},20]}],Graphics[{CapForm["Round"],Red,Thickness[.05],Line[{{0+150,4+150},{499-150,460-150}}],Line[{{-0+150,459-150},{480-150,-0+150}}]}]
],

Grid[{{" ","6"," "," "," "," "," "," "," "},{" ","7"," "," "," "," "," "," "," "},{" ","9"," "," "," "," "," "," "," "},{" ","4"," "," "," "," "," "," "," "},{" ","2"," "," "," "," "," "," "," "},{" ","1"," "," "," "," "," "," "," "},{" ","8"," "," "," "," "," "," "," "},{" ","7"," "," "," "," "," "," "," "},{" ","3"," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{2->ColorData[97,"ColorList"][[1]]},{},{{2,2}->ColorData[97,"ColorList"][[4]],{8,2}->ColorData[97,"ColorList"][[4]]}}] ,

Show[Rasterize[Grid[{{" ","6"," "," "," "," "," "," "," "},{" ","7"," "," "," "," "," "," "," "},{" ","9"," "," "," "," "," "," "," "},{" ","4"," "," "," "," "," "," "," "},{" ","2"," "," "," "," "," "," "," "},{" ","1"," "," "," "," "," "," "," "},{" ","8"," "," "," "," "," "," "," "},{" ","7"," "," "," "," "," "," "," "},{" ","3"," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{2->ColorData[97,"ColorList"][[1]]},{},{{2,2}->ColorData[97,"ColorList"][[4]],{8,2}->ColorData[97,"ColorList"][[4]]}}],"Image",ImageSize->237],Graphics[{Red,Circle[{80,380},20],Circle[{80,80},20]}],Graphics[{CapForm["Round"],Red,Thickness[.05],Line[{{0+150,4+150},{499-150,460-150}}],Line[{{-0+150,459-150},{480-150,-0+150}}]}]
],

Grid[{
{"4","9","6"," "," "," "," "," "," "},
{"1","8","3"," "," "," "," "," "," "},{"7","5","9"," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{None,None,{{{1,3},{1,3}}->ColorData[97,"ColorList"][[1]],{1,2}->ColorData[97,"ColorList"][[4]],{3,3}->ColorData[97,"ColorList"][[4]]}}] ,

Show[Rasterize[Grid[{
{"4","9","6"," "," "," "," "," "," "},
{"1","8","3"," "," "," "," "," "," "},{"7","5","9"," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "},{" "," "," "," "," "," "," "," "," "}},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{None,None,{{{1,3},{1,3}}->ColorData[97,"ColorList"][[1]],{1,2}->ColorData[97,"ColorList"][[4]],{3,3}->ColorData[97,"ColorList"][[4]]}}],"Image",ImageSize->237],Graphics[{Red,Circle[{80,430},20],Circle[{130,332},20]}],Graphics[{CapForm["Round"],Red,Thickness[.05],Line[{{0+150,4+150},{499-150,460-150}}],Line[{{-0+150,459-150},{480-150,-0+150}}]}]
]
}]

SUDOKU Strategies

The game starts with some numbers already filled in, and the player must figure out the missing ones. To do this, different strategies can be used, such as cross-hatching or counting, by checking which numbers are already in the same row, column, or box.

SlideView[{ 
Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{},{},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],{{1,3},{7,9}}->ColorData[97,"ColorList"][[3]],{3,9}->ColorData[97,"ColorList"][[8]],{1,3}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{},{1->ColorData[97,"ColorList"][[3]],3->ColorData[97,"ColorList"][[3]]},{{1,3}->ColorData[97,"ColorList"][[8]],{3,9}->ColorData[97,"ColorList"][[8]],{2,4}->ColorData[97,"ColorList"][[7]],{2,5}->ColorData[97,"ColorList"][[7]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{5->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]],3->ColorData[97,"ColorList"][[3]]},{{1,3}->ColorData[97,"ColorList"][[8]],{3,9}->ColorData[97,"ColorList"][[8]],{2,4}->ColorData[97,"ColorList"][[7]],{4,5}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,4,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ },{},{{1,3}->ColorData[97,"ColorList"][[8]],{3,9}->ColorData[97,"ColorList"][[8]],{2,4}->ColorData[97,"ColorList"][[7]],{4,5}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ },{},{{1,1}->ColorData[97,"ColorList"][[7]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]],{1,6}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]],{1,6}->ColorData[97,"ColorList"][[8]],{2,1}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]],{1,6}->ColorData[97,"ColorList"][[8]],{2,1}->ColorData[97,"ColorList"][[8]],{1,3}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]],{1,6}->ColorData[97,"ColorList"][[8]],{2,1}->ColorData[97,"ColorList"][[8]],{1,3}->ColorData[97,"ColorList"][[8]],{1,5}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]],{1,6}->ColorData[97,"ColorList"][[8]],{2,1}->ColorData[97,"ColorList"][[8]],{1,3}->ColorData[97,"ColorList"][[8]],{1,5}->ColorData[97,"ColorList"][[8]],{7,1}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{7,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]],{1,6}->ColorData[97,"ColorList"][[8]],{2,1}->ColorData[97,"ColorList"][[8]],{1,3}->ColorData[97,"ColorList"][[8]],{1,5}->ColorData[97,"ColorList"][[8]],{7,1}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]],{1,6}->ColorData[97,"ColorList"][[8]],{2,1}->ColorData[97,"ColorList"][[8]],{1,3}->ColorData[97,"ColorList"][[8]],{1,5}->ColorData[97,"ColorList"][[8]],{7,1}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]],{1,6}->ColorData[97,"ColorList"][[8]],{2,1}->ColorData[97,"ColorList"][[8]],{1,3}->ColorData[97,"ColorList"][[8]],{1,5}->ColorData[97,"ColorList"][[8]],{7,1}->ColorData[97,"ColorList"][[8]],{4,1}->ColorData[97,"ColorList"][[8]],{3,3}->ColorData[97,"ColorList"][[8]],{1,4}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{0,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]],{1,6}->ColorData[97,"ColorList"][[8]],{2,1}->ColorData[97,"ColorList"][[8]],{1,3}->ColorData[97,"ColorList"][[8]],{1,5}->ColorData[97,"ColorList"][[8]],{7,1}->ColorData[97,"ColorList"][[8]],{4,1}->ColorData[97,"ColorList"][[8]],{3,3}->ColorData[97,"ColorList"][[8]],{2,2}->ColorData[97,"ColorList"][[8]],{1,4}->ColorData[97,"ColorList"][[8]],{1,7}->ColorData[97,"ColorList"][[8]]}}],

Grid[((puzzle=(Map[ToString,{{7,0,4,8,5,2,9,0,0},{3,9,0,0,0,6,0,8,0},{0,0,8,0,0,0,5,7,4},

{8,7,3,0,4,0,0,5,6},{0,0,0,1,6,8,0,4,0},{1,4,0,7,0,0,0,0,0},

{6,2,9,0,0,0,7,0,0},{0,3,0,6,8,7,0,0,2},{0,0,7,0,0,3,0,0,5}},{2}]))/.{"0"->" "}),Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{{ 1->ColorData[97,"ColorList"][[3]]},{1->ColorData[97,"ColorList"][[3]]},{{{1,3},{1,3}}->ColorData[97,"ColorList"][[3]],
{1,1}->ColorData[97,"ColorList"][[7]],{6,1}->ColorData[97,"ColorList"][[8]],{1,6}->ColorData[97,"ColorList"][[8]],{2,1}->ColorData[97,"ColorList"][[8]],{1,3}->ColorData[97,"ColorList"][[8]],{1,5}->ColorData[97,"ColorList"][[8]],{7,1}->ColorData[97,"ColorList"][[8]],{4,1}->ColorData[97,"ColorList"][[8]],{3,3}->ColorData[97,"ColorList"][[8]],{2,2}->ColorData[97,"ColorList"][[8]],{1,4}->ColorData[97,"ColorList"][[8]],{1,7}->ColorData[97,"ColorList"][[8]]}}]
}
]

Graph Approach

Another way to solve Sudoku is by using graph theory. Here, each cell is treated as a node, and connections are made based on their positions in the grid.

SlideView[{  Rasterize[Grid[ConstantArray[" ",{9,9}],Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.3,.8}],"Image",ImageSize->251],Grid[ConstantArray[Graph[Range[1],{},ImageSize->25,VertexSize->.9],{9,9}],Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{.2,0}]  ,Grid[ConstantArray[Graph[Range[1],{},ImageSize->25,VertexSize->.9],{9,9}],Frame->All,Dividers->{White,White},Spacings->{.2,0}]}]

Graph Approach

To represent connections based on shared rows, columns, or blocks, we use edges to link each node to every other node in the same row, column, and box. By establishing these connections each node is connected in the following way:

Graph Approach

ResourceFunction["SudokuGraph"][3,]

Graph Coloring

By transforming a Sudoku puzzle into a graph, we can frame it as a vertex coloring problem. In vertex coloring, each vertex is assigned a color from a minimal set, ensuring that adjacent nodes have different colors. This approach solves the same problem under the same constraints as the original Sudoku puzzle.

g=Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,1\[UndirectedEdge]4,2\[UndirectedEdge]4,3\[UndirectedEdge]4}];

SlideView[{g=Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,1\[UndirectedEdge]4,2\[UndirectedEdge]4,3\[UndirectedEdge]4},VertexSize->.1,VertexLabels->Placed[Automatic,Center],GraphLayout->"GridEmbedding"];Graph[g,VertexSize->.2,VertexLabels->Placed[Automatic,Center]],HighlightGraph[g,{1,1\[UndirectedEdge]2,1\[UndirectedEdge]3},VertexLabels->Placed[Automatic,Center],PlotTheme->"Minimal",VertexStyle->{1->ColorData[97,"ColorList"][[1]]}],HighlightGraph[g,{1},VertexStyle->{1->ColorData[97,"ColorList"][[1]]},PlotTheme->"Minimal"],HighlightGraph[g,{1,2,1\[UndirectedEdge]2,2\[UndirectedEdge]3,2\[UndirectedEdge]4},VertexStyle->{1->ColorData[97,"ColorList"][[1]],2->ColorData[97,"ColorList"][[1]]},PlotTheme->"Minimal"],HighlightGraph[g,{1,2,1\[UndirectedEdge]2,2\[UndirectedEdge]3,2\[UndirectedEdge]4},VertexStyle->{1->ColorData[97,"ColorList"][[1]],2->ColorData[97,"ColorList"][[4]]},PlotTheme->"Minimal"],HighlightGraph[g,{1,2,1\[UndirectedEdge]3,3\[UndirectedEdge]4,3\[UndirectedEdge]2,3},VertexStyle->{1->ColorData[97,"ColorList"][[1]],2->ColorData[97,"ColorList"][[4]],3->ColorData[97,"ColorList"][[1]]},PlotTheme->"Minimal"],HighlightGraph[g,{1,2,1\[UndirectedEdge]3,3\[UndirectedEdge]4,3\[UndirectedEdge]2,3},VertexStyle->{1->ColorData[97,"ColorList"][[1]],2->ColorData[97,"ColorList"][[4]],3->ColorData[97,"ColorList"][[4]]},PlotTheme->"Minimal"],HighlightGraph[g,{1,2,4\[UndirectedEdge]2,1\[UndirectedEdge]4,3\[UndirectedEdge]4,3,4},VertexStyle->{1->ColorData[97,"ColorList"][[1]],2->ColorData[97,"ColorList"][[4]],3->ColorData[97,"ColorList"][[4]],4->ColorData[97,"ColorList"][[1]]},PlotTheme->"Minimal"],HighlightGraph[g,{1,2,4\[UndirectedEdge]2,1\[UndirectedEdge]4,3\[UndirectedEdge]4,3,4},VertexStyle->{1->ColorData[97,"ColorList"][[1]],2->ColorData[97,"ColorList"][[4]],3->ColorData[97,"ColorList"][[4]],4->ColorData[97,"ColorList"][[4]]},PlotTheme->"Minimal"],HighlightGraph[g,{1,2,4\[UndirectedEdge]2,1\[UndirectedEdge]4,3\[UndirectedEdge]4,3,4},VertexStyle->{1->ColorData[97,"ColorList"][[1]],2->ColorData[97,"ColorList"][[4]],3->ColorData[97,"ColorList"][[4]],4->ColorData[97,"ColorList"][[3]]},PlotTheme->"Minimal"],Graph[g,VertexStyle->{1->ColorData[97,"ColorList"][[1]],2->ColorData[97,"ColorList"][[4]],3->ColorData[97,"ColorList"][[4]],4->ColorData[97,"ColorList"][[3]]},PlotTheme->"Minimal"]}]

Graph Coloring

FindVertexColoring[g,{,,,}];

Graph[g,VertexStyle->Thread[VertexList[g]->%],]

Solving one Puzzle

To solve a specific puzzle using the graph coloring approach, we simply integrate the given numbers (hints) into the Sudoku graph.

SlideView[{puzzle={{0,4,3,0,8,0,2,5,0},{6,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,9,4},{9,0,0,0,0,4,0,7,0},{0,0,0,6,0,8,0,0,0},{0,1,0,2,0,0,0,0,3},{8,2,0,5,0,0,0,0,0},{0,0,0,0,0,0,0,0,5},{0,3,4,0,9,0,7,1,0}};
Grid[puzzle/.{0->" "},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1,.8}],puzzle={{0,4,3,0,8,0,2,5,0},{6,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,9,4},{9,0,0,0,0,4,0,7,0},{0,0,0,6,0,8,0,0,0},{0,1,0,2,0,0,0,0,3},{8,2,0,5,0,0,0,0,0},{0,0,0,0,0,0,0,0,5},{0,3,4,0,9,0,7,1,0}};
Grid[puzzle/.{0->" "},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1,.8},Background->{None,None,{{4,8}->ColorData[97,"ColorList"][[1]],{9,7}->ColorData[97,"ColorList"][[7]]}}]}]

Solving one Puzzle

To incorporate the hints, we connect each vertex representing a number to all the neighbors of the vertex with the same number.

puzzle={{0,4,3,0,8,0,2,5,0},{6,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,9,4},{9,0,0,0,0,4,0,7,0},{0,0,0,6,0,8,0,0,0},{0,1,0,2,0,0,0,0,3},{8,2,0,5,0,0,0,0,0},{0,0,0,0,0,0,0,0,5},{0,3,4,0,9,0,7,1,0}};Grid[{{Grid[puzzle/.{0->" "},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1,.8},Background->{None,None,{{4,8}->ColorData[97,"ColorList"][[1]],{9,7}->ColorData[97,"ColorList"][[3]],{7,7}->ColorData[97,"ColorList"][[2]],{7,8}->ColorData[97,"ColorList"][[2]],{7,9}->ColorData[97,"ColorList"][[2]],{8,7}->ColorData[97,"ColorList"][[2]],{8,8}->ColorData[97,"ColorList"][[2]],{8,9}->ColorData[97,"ColorList"][[2]],{9,8}->ColorData[97,"ColorList"][[2]],{9,9}->ColorData[97,"ColorList"][[2]],{1,7}->ColorData[97,"ColorList"][[2]],{2,7}->ColorData[97,"ColorList"][[2]],{3,7}->ColorData[97,"ColorList"][[2]],{4,7}->ColorData[97,"ColorList"][[2]],{5,7}->ColorData[97,"ColorList"][[2]],{6,7}->ColorData[97,"ColorList"][[2]],{9,1}->ColorData[97,"ColorList"][[2]],{9,2}->ColorData[97,"ColorList"][[2]],{9,3}->ColorData[97,"ColorList"][[2]],{9,4}->ColorData[97,"ColorList"][[2]],{9,5}->ColorData[97,"ColorList"][[2]],{9,6}->ColorData[97,"ColorList"][[2]]}}] ,,HighlightGraph[Graph[Range[81],Join[Thread[35\[UndirectedEdge]{61,62,63,70,71,72,80,81,7,16,25,34,43,52,73,74,75,76,77,78}],Thread[79\[UndirectedEdge]{61,62,63,70,71,72,80,81,7,16,25,34,43,52,73,74,75,76,77,78}]],VertexCoordinates->Thread[Flatten[Reverse[Partition[Range[3^4],3^2]]]->Reverse[Table[Reverse[Position[Partition[Range[81],9],i][[1]]],{i,3^4,1,-1}]]],VertexSize->.2],{61,62,63,70,71,72,80,81,7,16,25,34,43,52,61,73,74,75,76,77,78,81,81,35,79,Thread[35\[UndirectedEdge]{61,62,63,70,71,72,80,81,7,16,25,34,43,52,73,74,75,76,77,78}]}
,ImageSize->200,VertexSize->.3,PlotTheme->"Minimal",VertexStyle->{ColorData[97,"ColorList"][[2]],35->ColorData[97,"ColorList"][[1]],79->ColorData[97,"ColorList"][[3]]}]}}]

puzzle={{0,4,3,0,8,0,2,5,0},{6,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,9,4},{9,0,0,0,0,4,0,7,0},{0,0,0,6,0,8,0,0,0},{0,1,0,2,0,0,0,0,3},{8,2,0,5,0,0,0,0,0},{0,0,0,0,0,0,0,0,5},{0,3,4,0,9,0,7,1,0}};Grid[{{Grid[puzzle/.{0->" "},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1,.8},Background->{8->ColorData[97,"ColorList"][[2]],4->ColorData[97,"ColorList"][[2]],{{4,8}->ColorData[97,"ColorList"][[3]],{9,7}->ColorData[97,"ColorList"][[1]],{5,7}->ColorData[97,"ColorList"][[2]],{5,9}->ColorData[97,"ColorList"][[2]],{6,9}->ColorData[97,"ColorList"][[2]],{6,7}->ColorData[97,"ColorList"][[2]]}}] ,,HighlightGraph[Graph[Range[81],Join[Thread[35\[UndirectedEdge]{8,17,26,44,53,62,71,80,28,29,30,31,32,33,34,36,43,52,45,54}],Thread[79\[UndirectedEdge]{8,17,26,44,53,62,71,80,28,29,30,31,32,33,34,36,43,52,45,54}]],VertexCoordinates->Thread[Flatten[Reverse[Partition[Range[3^4],3^2]]]->Reverse[Table[Reverse[Position[Partition[Range[81],9],i][[1]]],{i,3^4,1,-1}]]],VertexSize->.2],{8,17,26,44,53,62,71,80,28,29,30,31,32,33,34,36,43,52,45,54,79,35,Thread[79\[UndirectedEdge]{8,17,26,44,53,62,71,80,28,29,30,31,32,33,34,36,43,52,45,54,79,35}]}
,ImageSize->200,VertexSize->.3,PlotTheme->"Minimal",VertexStyle->{ColorData[97,"ColorList"][[2]],35->ColorData[97,"ColorList"][[3]],79->ColorData[97,"ColorList"][[1]]}]}}]

Solving one Puzzle

We also add connections between vertices with a given number and all vertices that are assigned a different number.

puzzle={{0,4,3,0,8,0,2,5,0},{6,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,9,4},{9,0,0,0,0,4,0,7,0},{0,0,0,6,0,8,0,0,0},{0,1,0,2,0,0,0,0,3},{8,2,0,5,0,0,0,0,0},{0,0,0,0,0,0,0,0,5},{0,3,4,0,9,0,7,1,0}};
Grid[{{Grid[puzzle/.{0->" "},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1,.8},Background->{None,None,Flatten[{{4,8}->ColorData[97,"ColorList"][[1]],Thread[{{1,2},{1,3},{1,5},{1,7},{1,8},{2,1},{3,6},{3,8},{3,9},{4,1},{4,6},{5,4},{5,6},{6,2},{6,4},{6,9},{7,1},{7,2},{7,4},{8,9},{9,2},{9,3},{9,5},{9,8}}->ColorData[97,"ColorList"][[3]]]}]}],,HighlightGraph[Graph[Range[81],Join[Thread[35\[UndirectedEdge]{2,3,5,7,8,10,24,26,27,28,33,40,42,47,49,54,55,56,58,72,74,75,77,80}]],VertexCoordinates->Thread[Flatten[Reverse[Partition[Range[3^4],3^2]]]->Reverse[Table[Reverse[Position[Partition[Range[81],9],i][[1]]],{i,3^4,1,-1}]]],VertexSize->.2],{2,3,5,7,8,10,24,26,27,28,33,35,40,42,47,49,54,55,56,58,72,74,75,77,80,Thread[35\[UndirectedEdge]{2,3,5,7,8,10,24,26,27,28,33,35,40,42,47,49,54,55,56,58,72,74,75,77,80}]}
,ImageSize->200,VertexSize->.3,PlotTheme->"Minimal",VertexStyle->{ColorData[97,"ColorList"][[3]],35->ColorData[97,"ColorList"][[1]]}]}}]

puzzle={{0,4,3,0,8,0,2,5,0},{6,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,9,4},{9,0,0,0,0,4,0,7,0},{0,0,0,6,0,8,0,0,0},{0,1,0,2,0,0,0,0,3},{8,2,0,5,0,0,0,0,0},{0,0,0,0,0,0,0,0,5},{0,3,4,0,9,0,7,1,0}};
Grid[{{Grid[puzzle/.{0->" "},Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1,.8},Background->{None,None,Flatten[{{9,7}->ColorData[97,"ColorList"][[1]],Thread[{{1,2},{1,3},{1,5},{1,7},{1,8},{2,1},{3,6},{3,8},{3,9},{4,1},{4,6},{5,4},{5,6},{6,2},{6,4},{6,9},{7,1},{7,2},{7,4},{8,9},{9,2},{9,3},{9,5},{9,8}}->ColorData[97,"ColorList"][[3]]]}]}],,HighlightGraph[Graph[Range[81],Join[Thread[79\[UndirectedEdge]{2,3,5,7,8,10,24,26,27,28,33,40,42,47,49,54,55,56,58,72,74,75,77,80}]],VertexCoordinates->Thread[Flatten[Reverse[Partition[Range[3^4],3^2]]]->Reverse[Table[Reverse[Position[Partition[Range[81],9],i][[1]]],{i,3^4,1,-1}]]],VertexSize->.2],{2,3,5,7,8,10,24,26,27,28,33,79,40,42,47,49,54,55,56,58,72,74,75,77,80,Thread[79\[UndirectedEdge]{2,3,5,7,8,10,24,26,27,28,33,35,40,42,47,49,54,55,56,58,72,74,75,77,80}]}
,ImageSize->200,VertexSize->.3,PlotTheme->"Minimal",VertexStyle->{ColorData[97,"ColorList"][[3]],79->ColorData[97,"ColorList"][[1]]}]}}]

Solving one Puzzle

Integrating the hints into the Sudoku graph involves adding these additional connections while maintaining the original connections based on rows, columns, and blocks. This process creates a more interconnected structure that captures the relationships between the given numbers and their constraints.

graphHints[g_] :=

Now we can find a valid solution for the Sudoku puzzle using graph coloring:

sudokuSolve[g_]:=

puzzle={{0,4,3,0,8,0,2,5,0},{6,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,9,4},{9,0,0,0,0,4,0,7,0},{0,0,0,6,0,8,0,0,0},{0,1,0,2,0,0,0,0,3},{8,2,0,5,0,0,0,0,0},{0,0,0,0,0,0,0,0,5},{0,3,4,0,9,0,7,1,0}};

sudokuSolve[puzzle]

Solving one Puzzle

We can also visualize the solution:

sudokuGraphSolve[g_] :=

sudokuGraphSolve[puzzle]

So, by representing Sudoku as a graph and using graph coloring algorithms, we can elegantly assign numbers to the cells, respect all constraints, and obtain a valid solution for the puzzle.

Solving one Puzzle

Even if a Sudoku puzzle has multiple valid solutions or an infinite number of solutions, the graph coloring algorithm will still find a suitable correct solution ensuring that no adjacent vertices have the same color:

puzzle2={{0,0,8,1,7,6,0,2,0},{0,4,0,0,0,9,7,0,0},{0,0,0,0,0,0,0,0,0},{0,7,1,8,0,0,0,0,0},{0,0,0,0,0,0,6,7,9},{0,0,0,5,9,7,0,8,1},{0,0,0,0,2,0,0,0,0},{0,5,9,0,0,0,0,1,0},{0,1,4,6,5,0,3,0,0}};

sudokuGraphSolve[puzzle2]

Solving one Puzzle

Graph coloring can also be used to determine whether a Sudoku puzzle has a valid solution. This is achieved by examining the vertex chromatic number, which represents the minimum number of colors needed to color the graph so that no two adjacent vertices share the same color.

puzzle2={{5,1,6,8,4,9,7,3,2},{3,0,7,6,0,5,0,0,0},{8,0,9,7,0,0,0,6,5},{1,3,5,0,6,0,9,0,7},{4,7,2,5,9,1,0,0,6},{9,6,8,3,7,0,0,5,0},{2,5,3,1,8,6,0,7,4},{6,8,4,2,0,7,5,0,0},{7,9,1,0,5,0,6,0,8}};

VertexChromaticNumber[graphHints[puzzle2]]

sudokuSolutionQ[g_]:=

sudokuSolutionQ[puzzle2]

Phistomefel Ring

The Phistomefel Ring is a property of all Sudoku puzzles in which the digits appearing in the red area are exactly the same as those appearing in the green area.

Grid[ConstantArray[" ",{9,9}],Frame->All,Dividers->{Thread[{1,4,7,10}->Directive[Thickness[3]]],Thread[{1,4,7,10}->Directive[Thickness[3]]]},Spacings->{1.4,1},Background->{None,None,{{{3,7},{3,3}}->ColorData[97,"ColorList"][[4]],{{3,7},{7,7}}->ColorData[97,"ColorList"][[4]],{{7,7},{3,7}}->ColorData[97,"ColorList"][[4]],{{3,3},{3,7}}->ColorData[97,"ColorList"][[4]],{{1,2},{1,2}}->ColorData[97,"ColorList"][[3]],{{8,9},{8,9}}->ColorData[97,"ColorList"][[3]],{{1,2},{8,9}}->ColorData[97,"ColorList"][[3]],{{8,9},{1,2}}->ColorData[97,"ColorList"][[3]]}}]

Phistomefel Ring

By extracting the relevant vertices from the Sudoku graph, we can isolate the associated subgraph.

SlideView[{green={1,2,10,11,8,9,17,18,64,65,73,74,71,72,80,81};
red={21,30,39,48,57,22,23,24,25,34,43,52,61,60,59,58};g=ResourceFunction["SudokuGraph"][3,VertexSize->.4,VertexLabels->Placed[Automatic,Center],VertexStyle->White,ImageSize->300],Graph[g,VertexSize->.4,VertexLabels->Placed[Automatic,Center],VertexStyle->Join[Thread[red->ColorData[97,"ColorList"][[4]]],Thread[green->ColorData[97,"ColorList"][[3]]]],ImageSize->300],

Subgraph[g,Join[red,green],VertexSize->.4,VertexLabels->Placed[Automatic,Center],VertexStyle->Join[Thread[red->ColorData[97,"ColorList"][[4]]],Thread[green->ColorData[97,"ColorList"][[3]]]]],

Subgraph[g,Join[red,green],VertexSize->.4,VertexLabels->Placed[Automatic,Center]]}]

Phistomefel Ring

For this subgraph, we can determine a coloring, which then allows us to observe how the colors correspond exactly.

;Graph[Subgraph[g,Join[green,red]],]

Sort[green/.]
Sort[red/.]

Conclusion

We have explored how graph theory and graph coloring techniques can be applied to solve Sudoku puzzles. By representing Sudoku as a graph and using graph coloring algorithms, we can elegantly assign numbers to the cells, respect all constraints, and obtain a valid solution for the puzzle.

Graph theory and graph coloring have broad applications beyond Sudoku, and can be applied to other combinatorial problems and optimization challenges. Graph theory techniques offer valuable tools for solving puzzles and addressing real-world problems in a structured and systematic manner.