how to check every 3 x 3 box in sudoku?-CodePudding

I am trying to build a sudoku solver without much googling around. Right now, I am working on a function to test whether the board is valid, which I will use later in a loop. This is what the function currently looks like.

def valid(board):

    s = 0

    for row in board:
        if row.count('1') == 1 and row.count('2') == 1 and row.count('3') == 1 and row.count('4') == 1 and row.count('5') == 1 and row.count('6') == 1 and row.count('7') == 1 and row.count('8') == 1 and row.count('9') == 1:
            s  = 1

    for column in range(len(board)):
        if i[column].count('1') == 1 and i[column].count('2') == 1 and i[column].count('3') == 1 and i[column].count('4') == 1 and i[column].count('5') == 1 and i[column].count('6') == 1 and i[column].count('7') == 1 and i[column].count('8') == 1 and i[column].count('9') == 1:
            s  = 1

    for r in range(3):
        for c in range(3):
            print(board[r][c], end = '')

    if s == 18:
        print('valid')
    else:
        print('no')

The valid board I am using to test is this array of arrays:

example = [['4','3','5','2','6','9','7','8','1'],['6','8','2','5','7','1','4','9','3'],['1','9','7','8','3','4','5','6','2'],

['8','2','6','1','9','5','3','4','7'],['3','7','4','6','8','2','9','1','5'],['9','5','1','7','4','3','6','2','8'],

['5','1','9','3','2','6','8','7','4'],['2','4','8','9','5','7','1','3','6'], ['7','6','3','4','1','8','2','5','9']]

I am certain this is not the most efficient way to go about this but I am really just trying to understand the problem. So, when a row has each number 1-9 appear once, I add 1 to my s variable. When each column meets the same criteria, I also add 1 to my s variable. So when each row and column has numbers 1-9 appear once in them, my s variable should be 18, but this does not make the board valid as I still have to check each 3x3 box meets their own criteria. In the end, the s variable should be equal to 27 for the board to be valid.

The code I have tried to make the 3x3 boxes print will only print the first 3x3 box, how can I make it repeat for each 3x3 box? Can anyone help me with this issue? Thanks for the help.

Edit: I guess the brute force method would look like this:

    for r in range(3):
        for c in range(3):
            print(board[r][c], end = '')
    print('\n')
    for r in range(3):
        for c in range(3,6):
            print(board[r][c], end = '')
    print('\n')
    for r in range(3):
        for c in range(6,9):
            print(board[r][c], end = '')

    print('\n')
    print('\n')
    
    for r in range(3,6):
        for c in range(3):
            print(board[r][c], end = '')
    print('\n')
    for r in range(3,6):
        for c in range(3,6):
            print(board[r][c], end = '')
    print('\n')
    for r in range(3,6):
        for c in range(6,9):
            print(board[r][c], end = '')
    print('\n')

    print('\n')
    for r in range(6,9):
        for c in range(3):
            print(board[r][c], end = '')
    print('\n')
    for r in range(6,9):
        for c in range(3,6):
            print(board[r][c], end = '')
    print('\n')
    for r in range(6,9):
        for c in range(6,9):
            print(board[r][c], end = '')
    print('\n')

edit 2, I found a better way to do this:

def three(board):

    for row in range(0, 9, 3):
        for col in range(0, 9, 3):

            b = board[row][col]   board[row][col 1]   board[row][col 2]   board[row 1][col]   board[row 1][col 1]   board[row 1][col 2]   board[row 2][col]   board[row 2][col 1]   board[row 2][col 2]
            print(b)
            # test if valid...

this yielded me this result:

^ this is every 3x3 within the board.

CodePudding user response：

Each 3x3 box consists of three sub-lists. For instance, the top-left box consists of these three sub-lists:

board[0][0:3]
board[1][0:3]
board[2][0:3]

The one in the center looks like this:

board[3][3:6]
board[4][3:6]
board[5][3:6]

To visit all 9 boards you can thus loop all columns that are multiples of 3, and all rows that are multiples of 3. Here each box is just the concatenation of those three sub-lists:

for row in range(0, 9, 3):
    for column in range(0, 9, 3):
        box = (board[row][column:column 3]
               board[row 1][column:column 3]
               board[row 2][column:column 3])
        # do something with box

As you already have a solution for a row, that solution can also serve for this "flattened" box -- which also has 9 elements.

To avoid code repetition, it is better to put the row-verification logic in a little function. Then you can call that function for each row, for each column and for each "flattened" box.

The counting you do with s works fine, but consider that as soon as you find an invalid section in your board, it is of no use to continue checking others. In that case you can just break out and immediately return out of the function, indicating it is not a valid board. If such an exit never happens and execution reaches the end of the function, you don't need to check a counter any more. The mere fact you didn't exit earlier means that the board is valid. So drop that counter.

Your function should better not print the outcome, but just return a boolean indicating whether the board is valid or not. Leave it to the caller what to do with that information.

Let's see what the function looks like at this point:

def valid(board):
    def is_complete(line):
        return line.count('1') == 1 and line.count('2') == 1 and line.count('3') == 1 and line.count('4') == 1 and line.count('5') == 1 and line.count('6') == 1 and line.count('7') == 1 and line.count('8') == 1 and line.count('9') == 1
    
    for row in board:
        if not is_complete(row):
            return False

    for column in range(9):
        line = [row[column] for row in board]
        if not is_complete(line):
            return False

    for row in range(0, 9, 3):
        for column in range(0, 9, 3):
            line = (board[row][column:column 3]
                    board[row 1][column:column 3]
                    board[row 2][column:column 3])
            if not is_complete(line):
                return False
    return True

So is_complete is that little function that performs the verification logic for one section of 9 cells. It just returns the boolean expression, which evaluates to True of False.

The above works fine. Now it is time look at the verification logic in the is_complete function. Calling count nine times is not efficient. It is more efficient to collect all values into a single set and verify that this set has 9 values.

Secondly, the loops that have return False exit points can be written using the all or any function

This leads to the following improvement:

def valid(board):
    def is_complete(line):
        return len(set(line)) == 9
    
    if not all(is_complete(row) for row in board):
        return False

    if not all(is_complete([row[column] for row in board]) for column in range(9)):
        return False

    if not all(is_complete(board[row][column:column 3]
                            board[row 1][column:column 3]
                            board[row 2][column:column 3])
                for row in range(0, 9, 3)
                for column in range(0, 9, 3)):
        return False
    return True

CodePudding user response：

In your "brute force" method, you have, in order:
for r in range(0,3) 3 times,
for r in range(3,6) 3 times,
for r in range(6,9) 3 times.
See a pattern? You can introduce another variable that increases by 3 each time (or increases by 1, but you multiply it by 3 before using it).

Then, inside each of these loops, you have the exact same situation but with c instead of r. You can introduce yet another variable for that. And when I say "introduce another variable", it's really more like "write an additional loop with its own index variable.

Note that you can write a for loop like this:

for i in [0, 3, 6]:

CodePudding user response：

Functions are always good to use when reapeating things. You already have already understood the main idea, so i just made a function you can run every combination through.

def testbox(row, column):
    for r in range(row, row 3):
        print()
        for c in range(column, column 3):
            print(example[r][c], sep=' ', end='')
    print('\n')


for r in [0, 3, 6]:
    for c in [0, 3, 6]:
        testbox(r, c)

CodePudding user response：

I am not certain whether this is the best approach, but I managed to do it like this:

def validate_part(part_list):
    if type(part_list[0]) != int:
        part_list = [int(part) for part in part_list]
    num_list = list(range(1, 10))
    filled = True
    for num in num_list:
        if num not in part_list:
            filled = False
    return filled


def valid(board):
    col_list = [[] for col in range(1,10)]
    square_list = []
    check_list = {"row":[], "col":[], "square":[]}

    for idx,row in enumerate(board):
        for num in range(len(row)):
            col_list[idx].append(row[num])
        check_list["row"].append(validate_part(row))

    for col in col_list:
        check_list["col"].append(validate_part(col))

    for i in range(0,len(board),3):
        part = board[i:i 3]
        squares = [[] for s in range(3)]
        for row in range(len(part)):
            iter = 0
            for col in range(0,len(part[row]),3):
                squares[iter]  = part[row][col:col 3]
                iter  = 1

        square_list  = squares
        
    for square in square_list:
        check_list["square"].append(validate_part(square))
        
    if False not in check_list["row"] and False not in check_list["col"] and False not in check_list["square"]:
        return True
    else:
        return False