[Community Puzzle] 16x16 Sudoku

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

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.)

#2

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?

#3

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
#4

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?

#5

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)