How to solve problems with backtracking

Problem:

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

The play field

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 

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert