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