4
\$\begingroup\$

I just tried to create a program for the N queens problem.

def print_board() -> None:
    """ Prints the board """

    length = 3 * (SIZE - 1) + SIZE + 4

    print()

    print('-' * length)

    for row in board:
        print('| ' + ' | '.join(row) + ' |')
        print('-' * length)

    print()

def isValid(row: int, col: int) -> bool:
    """ Returns if a cell index is valid """

    return 0 <= row < SIZE and 0 <= col < SIZE

def isSafe(row: int, col: int) -> bool:
    """ Checks if the given index position is safe """

    # Checks if the column is safe
    for i in range(SIZE):
        if i != row and board[i][col] != ' ':
            return False

    # Checks if the row is safe
    for j in range(SIZE):
        if j != col and board[row][j] != ' ':
            return False

    # Checks if the diagonals are safe
    for k in range(SIZE):
        if isValid(row + k, col + k) and board[row + k][col + k] != ' ' or \
           isValid(row - k, col + k) and board[row - k][col + k] != ' ' or \
           isValid(row + k, col - k) and board[row + k][col - k] != ' ' or \
           isValid(row - k, col - k) and board[row - k][col - k] != ' ':

            return False

    return True


def backtrack(row=0, total=0) -> bool:
    """ Backtracks and fills chacks for every possible combination """

    # If all rows are safely filled with queens
    if row == SIZE:
        # print_board()  # Uncomment the code to print the current solution
        # input('Enter to continue... ')

        return 1

    for col in range(SIZE):
        # If the current index is safe, check for the next row
        if isSafe(row, col):
            board[row][col] = 'Q'

            total += backtrack(row + 1)

            board[row][col] = ' '

    return total


def solve() -> None:
    """ Calls backtrack and prints number of solutions """

    total = backtrack()

    print()

    if not total:
        print('No possible solution was found')
    elif total == 1:
        print('There is a total of 1 solution')
    else:
        print(f'There are a total of {total} solutions')


if __name__ == '__main__':
    SIZE = int(input('Enter the size of the board: '))

    board = [[' '] * SIZE for row in range(SIZE)]

    solve()

Though it does work, I'm not satisfied yet.

I want to make this code as short as possible while also following Pep8 rules.

I believe there isn't a faster approach, but if there are any, please enlighten me!

Thank you!

\$\endgroup\$
  • 1
    \$\begingroup\$ Did you notice Naming conventions in PEP8? \$\endgroup\$ – RomanPerekhrest Nov 22 '19 at 15:12
  • \$\begingroup\$ @RomanPerekhrest facepalms I knew I was doing something wrong, this was it. \$\endgroup\$ – Sriv Nov 22 '19 at 18:35
4
\$\begingroup\$

This isn't bad looking code. It's formatted nicely, and I think this is a good use of type hints.

My two main concerns are your naming, and your use of print.


Names should be snake_case according to PEP8. You started adhering to it, then reverted back to camelCase later. It can be a hard change to make if you're used to other languages, but it's proper for Python, and studies have shown that it's easier to read anyways.


I think you're "abusing" print here.

print_board is printing the board instead of returning a representation that can be used elsewhere. I'd change it to format_board (or stringify_board or something similar), and have it return a string instead of forcibly printing the board. It would be a fairly trivial change too. Just concatenate the different printed strings together, replace the print() calls with a "\n", and change your imperative for loop to a list comprehension that you give to join after. It would honestly probably be shorter and cleaner after those changes anyways.

Then elsewhere, like in solve, you're printing the results. I would instead return some kind of indicator value, like an Enum instead of printing there.

Why bother with limiting print? Testing and portability. Say you wanted to programmatically test print_board. You would need to intercept sys.stdin to get the printed text to compare it against a known string. This is both slower and more complicated than just having a function that returns a string in the first place. The same goes for solve. To test that's its operating correctly, you need to verify what it's printing instead of just checking the return value.

Forcing use of print also prevents you from using these function in any other context, like a Tkinter UI.

Return the data and let the caller decide how they want to use it.

If you really want a print_board function for convenience, just make a wrapper:

def print_board() -> None:
    print(format_board())

Lastly, instead of using strings to indicate piece types, I'd use an Enum. Right now, you have a strong "Q" to indicate a queen on the board. Strings can be easily typo'd though; enums can't. If the only two valid board piece options are an empty space and a queen, you should use an enum to not only make that explicitly stated, but to enforce it. Entering an invalid enum invalid enum value will lead to an error instead of code-dependant effects that may end lead to silent failures.


I also realized just as I was about to submit this that your print_board and backtrack functions are relying on the global board defined in the "main". Don't do this! If those functions require data like board, that data should be explicitly passed in as arguments. If you wanted to test those functions, you wouldn't be able to just generate a dummy board in the console and pass it in. You would need to modify the global, run the function, then remember to modify to global again before further testing. The less relience you have on global variables, the easier your code will be to test and comprehend. Ideally, functions should accept as arguments all the data that they require, and return all data that they produce. This isn't always feasible, but it's a good design choice to pick unless you have a good reason to rely on globals (like board) and side-effects (like print).



Now that I'm on my full computer, I'm able to take a better look at the code and play with it a little more.

First, here's the enum usage that I was referring to. Ignore my previous suggestion for solve. I realized that an enum wasn't really appropriate there (I'll show my alternate suggestion after). Basically, BoardSquare represents the total possible states of each square on the board, along with the string representations that they have:

from enum import Enum

class BoardSquare(Enum):  # A square on the board can either be a queen, or an empty space
    QUEEN = "Q"
    EMPTY = " "

With that, I decided to use some slightly more advanced type hinting and created an alias for the board:

from typing import List

Board = List[List[BoardSquare]]  # A Board is a list of lists of board squares

This, combined with the enum ensures that nothing except a QUEEN or EMPTY is ever put into a board. Attempting to do so will cause a warning. This helps prevent typos:

board: Board = [[BoardSquare.EMPTY] * side_length for _ in range(side_length)]
board[1][2] = "SOME INVALID DATA"  # Causes an "Unexpected types" warning

And here's my format_board that I came up with:

# A helper to neaten up format_board
def _format_row(row: List[BoardSquare]) -> str:
    return '| ' + ' | '.join(square.value for square in row) + ' |'  # .value is the string defined in the enum


def format_board(board: Board) -> str:
    """ Formats the board as a string """
    board_length = len(board)  # Instead of relying on the global SIZE, I'd just compute it
    print_side_length = 3 * (board_length - 1) + board_length + 4

    top_bottom_str = '-' * print_side_length  # Might as well save this instead of writing the same thing twice.

    # I'll admit, this got a little more convoluted than I thought it would. It's just nested called to `join `though.
    return top_bottom_str + "\n" \
           + '\n'.join(_format_row(row) + '\n' + top_bottom_str for row in board)

Yes, as the comments note, this got a little longer than I though it would. The need to translate the enum into a string using the generator expression necessitated breaking off the formatting of each row into its own function for readability.

After going around and touching up some other stuff (see the comments), here's the full code that I ended up with:

from typing import List
from enum import Enum


class BoardSquare(Enum):  # A square on the board can either be a queen, or an empty space
    QUEEN = "Q"
    EMPTY = " "


Board = List[List[BoardSquare]]  # A Board is a list of lists of board squares


# Make it easier to create a new board for testing purposes
def new_board(side_length: int) -> Board:
    return [[BoardSquare.EMPTY] * side_length for _ in range(side_length)]


# A helper to neaten up format_board
def _format_row(row: List[BoardSquare]) -> str:
    return '| ' + ' | '.join(square.value for square in row) + ' |'  # .value is the string defined in the enum


def format_board(board: Board) -> str:
    """ Formats the board as a string """
    board_length = len(board)  # Instead of relying on the global SIZE, I'd just compute it
    print_side_length = 3 * (board_length - 1) + board_length + 4

    top_bottom_str = '-' * print_side_length  # Might as well save this instead of writing the same thing twice.

    # I'll admit, this got a little more convoluted than I thought it would. It's just nested called to `join `though.
    return top_bottom_str + "\n" \
           + '\n'.join(_format_row(row) + '\n' + top_bottom_str for row in board)


def print_board(board: Board) -> None:
    """ Prints the board """
    print(format_board(board))


def is_valid(row: int, col: int) -> bool:
    """ Returns if a cell index is valid """
    return 0 <= row < GLOBAL_SIZE and 0 <= col < GLOBAL_SIZE


def is_safe(row: int, col: int) -> bool:
    """ Checks if the given index position is safe """
    # Checks if the column is safe
    for i in range(GLOBAL_SIZE):
        if i != row and global_board[i][col] != BoardSquare.EMPTY:
            return False

    # Checks if the row is safe
    for j in range(GLOBAL_SIZE):
        if j != col and global_board[row][j] != BoardSquare.EMPTY:
            return False

    # Checks if the diagonals are safe
    for k in range(GLOBAL_SIZE):
        if is_valid(row + k, col + k) and global_board[row + k][col + k] != BoardSquare.EMPTY or \
           is_valid(row - k, col + k) and global_board[row - k][col + k] != BoardSquare.EMPTY or \
           is_valid(row + k, col - k) and global_board[row + k][col - k] != BoardSquare.EMPTY or \
           is_valid(row - k, col - k) and global_board[row - k][col - k] != BoardSquare.EMPTY:

            return False

    return True


def backtrack(row=0, total=0) -> int:  # I changed this to int. It was bool before, but that was wrong
    """ Backtracks and fills checks for every possible combination """
    # If all rows are safely filled with queens
    if row == GLOBAL_SIZE:
        # print_board(global_board)  # Uncomment the code to print the current solution
        # input('Enter to continue... ')
        return 1

    for col in range(GLOBAL_SIZE):
        # If the current index is safe, check for the next row
        if is_safe(row, col):
            global_board[row][col] = BoardSquare.QUEEN  # Use the enums values here instead
            total += backtrack(row + 1)
            global_board[row][col] = BoardSquare.EMPTY

    return total


def report_solution() -> None:
    """ Calls backtrack and prints number of solutions """
    total = backtrack()

    print()

    if not total:
        print('No possible solution was found')

    elif total == 1:
        print('There is a total of 1 solution')

    else:
        print(f'There are a total of {total} solutions')


if __name__ == '__main__':
    GLOBAL_SIZE = int(input('Enter the size of the board: '))

    global_board = new_board(GLOBAL_SIZE)

    report_solution()
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I'm on my phone, so this is going to be a relatively poor review. Not at all! This is one of the best reviews I've ever gotten! But, could you please explain how to use Enum here? I don't quite understand how to use them. \$\endgroup\$ – Sriv Nov 23 '19 at 5:52
  • 1
    \$\begingroup\$ Just search for "Python enum". \$\endgroup\$ – Roland Illig Nov 23 '19 at 6:11
  • \$\begingroup\$ @RolandIllig I did, but I'm not quite sure how to use it here. \$\endgroup\$ – Sriv Nov 23 '19 at 6:35
  • \$\begingroup\$ Ah, ok, you should always tell from the beginning when you did search, and what you found, and what you didn't understand. Otherwise we assume (by experience) that you are too lazy to search. :) \$\endgroup\$ – Roland Illig Nov 23 '19 at 6:38
  • \$\begingroup\$ @Srivaths This afternoon (I just woke up), I'm going to fix this review up a bit, including some examples. I'll message you. \$\endgroup\$ – Carcigenicate Nov 23 '19 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.