# [Community Puzzle] 16x16 Sudoku

Coding Games and Programming Challenges to Code Better

Created by @yoch, validated by @darkhorse64, @Rob-G and @Timinator.
If you have any issues, feel free to ping them.

(CommunityBot did not create this post; maybe the forum was down when the puzzle was approved.)

So far I tried this:

1. First go through the grid to find trivial cell values (cells with only one possible candidate) until there are none left.
2. Then do brute-force backtracking on the remaining grid.

Iâ€™ve managed to speed up the brute-force backtracking considerably, but it is still way to slow to solve test grids 3-6. Grid 3 requires 3,907,366,771 iterations to complete (after filling 5 trivial cell values), taking 82 seconds on my machine.

How can this be improved? What is the required â€śsmartâ€ť backtracking part here? How can I prioritize exploring the candidates during backtracking? Any hints?

Hi,

For Test3 Iâ€™m only making 3 guesses in total so you are missing quite a few in your first step.
Before I have to make any guess my grid looks like that:

.......EB.HALDGN
..N...H.D..JOEFK
E.K.A..J..NOCBHP
BFHCLODNKGPEIMAJ
...JHN.PFO..BLME
.N.K.....I..JGOD
.OM.JIECNB.GHPKA
HB..OD..P.J.NFCI
.HA.ME...D.BKNPC
D..ENB.HAPOL.JI.
NM.B..OAJKE.DHL.
.PL....D.N..EABO
.E.HDC.O...FPKN.
.C..EAN.OL.P.I.H
IA.NG.PMCHKDFOE.
..O.IH.....NAC..

You say you are taking care of cells with only one possible candidate, you also need to use the fact that you know that in each row, col & block every letter appears only once, ie: if you can only place the letter in one cell of the row, col or block, it has to go there.

1 Like

I must be doing something fundamentally wrong then. For grid 3, I am only able to find 10 trivial cell values now (after fixing a silly mistake), after which my grid looks like this:

........B.HALD.N
..N.....D...OEF.
..K.A..J..NO.B.P
.F.CL.D.KGPEIM.J
...JH..P.....L.E
.N.K.....I..JGOD
.OM..IECNB.GHP..
HB...D..P.J.NFCI
.HA.ME......KN.C
D..ENB.H.POL.J..
NM.B..O.JK..DH..
.PL....D.....A.O
.E.HDC.....FPK..
.C..EAN.OL.P.I..
IA.NG.PM..KD.OE.
..O.IH.....NAC..

When testing the trivial cell values, I of course combine what is already in the row plus in the column plus in the block, and if only one letter is missing across all 3, that is the only solution. I go through the whole grid and repeat until I find no more trivial cell values.

How many trivial cell values do you find?

The grid I posted above is after Iâ€™m done with adding all the â€śtrivialâ€ť.

Letâ€™s take the third line after you added the 10 values:

..K.A..J..NO.B.P

You can deduce that E has to go in the first position because:

• It canâ€™t go in position 2 because thereâ€™s already an E in position 2 on line 13
• It canâ€™t go in position 4 because thereâ€™s already an E in position 4 on line 10
• It canâ€™t go in position 6 because thereâ€™s already an E in position 6 on line 9
• It canâ€™t go in position 7 because thereâ€™s already an E in position 7 on line 7
• It canâ€™t go in position 9 or 10 because thereâ€™s already an E the second block (line 4, position 12)
• It canâ€™t go in position 13 or 15 because thereâ€™s already an E the third block (line 2, position 14)