CT Scan Backtracking algorithm

#help

c++

Top comments (3)

Start with edge cases e.g values like 0 or 4(where 4 is the length of the row, column or diagonal), because you can fill in those cells without doubts:

4 in 1 4 2 1 →

? ? ? ?
B B B B
? ? ? ?
? ? ? ?

0s in 0 2 2 1 2 1 0 ↘

? ? ? -
B B B B
? ? ? ?
- ? ? ?

0s in 0 1 2 2 2 1 0 ↙

- ? ? -
B B B B
? ? ? ?
- ? ? -

As well second 2 in 0 2 2 1 2 1 0 ↘ is edge case because 2 is the length of the second diagonal

- ? B -
B B B B
? ? ? ?
- ? ? -

Because we filled in some values we got new edge cases, for example 4-th 1 in 0 2 2 1 2 1 0 ↘

- ? B -
B B B B
? ? - ?
- ? ? -

repeat until you fill in all values.

cammm988 • May 11 '19

what if there is no 0's or 4's?

stereobooster • May 16 '19

Sorry was busy. I need to correct myself I said 0 and 4, but instead of 4 should be length of free slots in row, column or diagonal. First diagonal (in any direction) has only one free slot, second diagonal has two slots, etc. Right?

If there are no edge cases (nor 0, nor length of free slots covered), we need to take a guess. Peek any row, column or diagonal with maximum probability, for example we have 2 free slots and we know that there is only one slot should be taken so we can take a guess either it is 1 0 or 0 1 (probability of each case is 50%).

Now you take a guess. Peek one or another case, and memorise that place where you took a guess, then continue solving until you finish or figure out that it is unsolvable. If it is unsolvable you need to return to the place where you took a guess and choose other path.

This process of guessing and abandoning wrong guesses is what they call "backtracking".

I need to say that this algorithm is depth first search, so not sure if it the most effective.

DEV Community

CT Scan Backtracking algorithm

Top comments (3)

Read next

How to Determine if an Integer is a Palindrome on LeetCode

CSS Grid Layout Tutorial

Nueva ventana

Event Loop - Parte 2