# How to solve problems with backtracking

Problem:

In the last round of dungeons and dragons the DM told us a riddle:

The goal ist to fill it out in a way, that in every row and in every column and in every diagonal line no two letters appear twice.

As the nerd I am, I solved the problem with a backtracking algorithm:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate („backtracks“) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Wikipedia, 13.04.2021

Code:

```problem = [ ["A" ,"B" ,"C" ,"D" ,"E" ,"F" ],
[None,None,None,None,None,None],
[None,None,False,False,None,None],
[None,None,False,False,None,None],
[None,None,None,None,None,None],
[None,None,None,None,None,None] ]

def isRow(p,r,v) : # Checks, if the value v is in p at row r
for i in p[r] :
if i == v : return True
return False

def isColumn(p,c,v) : # Checks, if the value v is in p at column c
for i in range(6) :
if p[i][c] == v : return True
return False

def isDiagonal(p,r,c,v) :  # Checks, if the value v is in p in the diagonals from position r and c
pos = [r-1,c-1]	# Check the top left values
while pos >= 0 and pos >= 0 :
if p[pos][pos] == v : return True
pos = [pos-1,pos-1]

pos = [r-1,c+1]	# Check the top right values
while pos >= 0 and pos <= 5 :
if p[pos][pos] == v : return True
pos = [pos-1,pos+1]

pos = [r+1,c+1] # Check the bottom right values
while pos <= 5 and pos <= 5 :
if p[pos][pos] == v : return True
pos = [pos+1,pos+1]

pos = [r+1,c-1] # Check the right left values
while pos <= 5 and pos >= 0 :
if p[pos][pos] == v : return True
pos = [pos+1,pos-1]

return False

def res(p,r=0,c=0) :
values = ["A","B","C","D","E","F"]
if r == 5 and c == 5 : # If last Value
if p[r][c] == None : # And it is empty
for v in values : # Check for every value
if not (isRow(p,r,v) + isColumn(p,c,v) + isDiagonal(p,r,c,v)) : # Checks, if v can be placed at (r,c)
p[r][c] = v # Insert value

for j in p : # Does the printing and formatting
str = "   "
for k in j :
if k == False : str += "  "
else : str += k + " "
print(str)
print()

p[r][c] = None # Resets the position for cleaning
elif p[r][c] == None :
for v in values :
if not (isRow(p,r,v) + isColumn(p,c,v) + isDiagonal(p,r,c,v)) :
p[r][c] = v
if c == 5 : res(p,r+1,0) # If last value in row jump one down
else : res(p,r,c+1) # else next value
p[r][c] = None
else :
if c == 5 : res(p,r+1,0)
else : res(p,r,c+1)

res(problem)```

Result:

```   A B C D E F
C F E B A D
E A     F B
B D     C E
F C B E D A
D E A F B C

A B C D E F
C F E B A D
E A     F B
B D     C E
F C B E D A
D E F A B C

A B C D E F
D E A F B C
B C     D A
F D     C E
C A E B F D
E F D C A B

A B C D E F
D E A F B C
B C     D E
F D     C A
C A E B F D
E F D C A B

A B C D E F
D E A F B C
F C     D A
B D     C E
C A B E F D
E F D C A B

A B C D E F
D E A F B C
F C     D A
B D     C E
C A E B F D
E F D C A B

A B C D E F
D E A F B C
F C     D E
B D     C A
C A E B F D
E F D C A B

A B C D E F
D E F A B C
F C     D A
B D     C E
C A B E F D
E F D C A B

A B C D E F
D E F A B C
F C     D A
B D     C E
C A E B F D
E F D C A B

A B C D E F
D E F B A C
F C     D B
B A     C E
C D B E F A
E F A C B D

A B C D E F
D E F B C A
F C     D B
B D     A E
C A B E F D
E F D A B C

A B C D E F
D F E A B C
E C     D A
B D     F E
F A B E C D
C E D F A B

A B C D E F
D F E B A C
E A     D B
B C     F E
F D B E C A
C E A F B D

A B C D E F
D F E B A C
E A     F B
B C     D E
F D B E C A
C E A F B D

A B C D E F
D F E B A C
E A     F B
B C     D E
F D B E C A
C E F A B D

A B C D E F
D F E B A C
E C     D B
B A     F E
F D B E C A
C E A F B D

A B C D E F
D F E B A C
E C     D B
B D     F A
F E B A C D
C A D F B E

A B C D E F
D F E B A C
E C     D B
F A     C E
C D F E B A
B E A C F D

A B C D E F
D F E B A C
E C     D B
F D     C A
C E F A B D
B A D C F E

A B C D E F
D F E B A C
E C     F B
B A     D E
F D B E C A
C E A F B D

A B C D E F
D F E B C A
E C     D B
F D     A E
C A F E B D
B E D A F C

A B C D E F
F D E A B C
E C     D A
B F     C E
C A B E F D
D E F C A B

A B C D E F
F D E B A C
E C     D B
B F     C A
C E B A F D
D A F C B E

A B C D E F
F D E B C A
E C     D B
B F     A E
C A B E F D
D E F A B C ```