python - Having trouble making what should be a simple addition to Sudoku solver

Question

I'm having trouble adapting the Sudoku solver from here https://techwithtim.net/tutorials/python-programming/sudoku-solver-backtracking/ to include a diagonal constraint

This is the original code:

board = [
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0]
]

def solve(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find

    for i in range(1,10):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve(bo):
                return True

            bo[row][col] = 0

    return False


def valid(bo, num, pos):
    
    # Check row
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False

    # Check column
    for i in range(len(bo)):
        if bo[i][pos[1]] == num and pos[0] != i:
            return False

    # Check box
    box_x = pos[1] // 3
    box_y = pos[0] // 3

    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x * 3, box_x*3 + 3):
            if bo[i][j] == num and (i,j) != pos:
                return False
                
    return True


def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - - ")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j]) + " ", end="")


def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return (i, j)  # row, col

    return None

print_board(board)
solve(board)
print("______________________")
print_board(board)

Now this is an empty board, it obviously has almost infinite valid solutions and the code will just return the first one it finds - but it will also quickly find the unique solution when you input some actual numbers.

As a coding problem I decided to see if I could add a diagonal constraint: i.e no number repeats in bo[i][i] from i = 0 to i = 8 inclusive (i.e range(0,9) or range(9) - see I know some code!)

So this seemed pretty easy - I just need to add an extra loop in the valid function - how hard can it be?

I tried:

for i in range(9):
        if bo[i][i] == num and (i,i) != pos:
            return False

and many similar variations thereof - and so such luck. I can't get it to work. For this variation it seems to run forever, but if you enter say

board = [
    [1,2,3,4,5,6,7,8,9],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0]
]

Which should easily return a valid diagonal sudoku solution - it just returns the same inputted board as the "solution" - i.e with 72 blank cells!

Obviously I'm missing something very simple but I'm going crazy working out what it is.

I'm new to python and this is my first post here - so apologise if my forum etiquette is wrong. I appreciate all feedback!

Thank you!

edit: OK. I have a solution that almost works but I'd like to know why there's the one exception and I'd still like to know why my original didn't. Here's what I did

First:

def main_diagonal(bo):
    main_diagonal = []
    for i in range(0,9):
        main_diagonal += str(bo[i][i])
    for i in range(0,9):
        main_diagonal[i] = int(main_diagonal[i])
    return main_diagonal

Then within the valid function add:

for i in range(1,10):
        if main_diagonal(bo).count(i) > 1:
            return False

Now this does very well at stopping numbers repeating in the diagonals, however, there's an exception! The 81st cell, that is bo[8][8] which appears in the main diagonal, can contain a repeated number. Might this be because the original algorithm assumes (correctly) that if the first 80 cells are valid, so is the 81st, whereas here that isn't the case? How do I remove this bug?

This way of counting if the number of appearances of a certain number is greater than 1 is much more intuitive to me than the original code, but I still need to learn why my first attempt didn't work to stop falling into a similar situation down the line.

标签： python