1

This is my python program to solve the 8-queens problem. Everything is working except the final step of printing the solved board. I use recursion/backtracking to fill the board with queens until a solution is found. The board object that holds the solution is self, which is a reference to b1, so I assume that b1, the original board I initialized, would be updated to contain the final solved board, and would print the solution using printBoard. However, b1 is not being updated and is holding a failed board when I print it for some unknown reason.

edit: added placeQueen in solve

EMPTY = 0
QUEEN = 1
RESTRICTED = 2

class Board:

    # initializes a 8x8 array
    def __init__ (self):
        self.board = [[EMPTY for x in range(8)] for y in range(8)]

    # pretty prints board
    def printBoard(self):
        for row in self.board:
            print(row)

    # places a queen on a board
    def placeQueen(self, x, y):
        # restricts row
        self.board[y] = [RESTRICTED for i in range(8)]

        # restricts column
        for row in self.board:
            row[x] = RESTRICTED

        # places queen
        self.board[y][x] = QUEEN

        self.fillDiagonal(x, y, 0, 0, -1, -1)   # restricts top left diagonal
        self.fillDiagonal(x, y, 7, 0, 1, -1)    # restructs top right diagonal
        self.fillDiagonal(x, y, 0, 7, -1, 1)    # restricts bottom left diagonal
        self.fillDiagonal(x, y, 7, 7, 1, 1)     # restricts bottom right diagonal

    # restricts a diagonal in a specified direction
    def fillDiagonal(self, x, y, xlim, ylim, xadd, yadd):
        if x != xlim and y != ylim:
            self.board[y + yadd][x + xadd] = RESTRICTED
            self.fillDiagonal(x + xadd, y + yadd, xlim, ylim, xadd, yadd)

    # recursively places queens such that no queen shares a row or
    # column with another queen, or in other words, no queen sits on a
    # restricted square. Should solve by backtracking until solution is found.
    def solve(self, col):

        if col == -1:
            return True

        for i in range(8):
            if self.board[i][col] == EMPTY:
                temp = self.copy()

                self.placeQueen(col, i)
                if self.solve(col - 1):
                    return True

                temp.board[i][col] = RESTRICTED
                self = temp.copy()

        return False

    # deep copies a board onto another board
    def copy(self):
        copy = Board()

        for i in range(8):
            for j in range (8):
                copy.board[j][i] = self.board[j][i]

        return copy


b1 = Board()
b1.solve(7)
b1.printBoard()

I know that my actual solver is working, because when I add a printBoard like so:

if col == -1:
    self.printBoard()
    return True

in the solve method, a solved board is printed. In short, why is the self instance of a board not updating b1?

ggorlen
  • 44,755
  • 7
  • 76
  • 106
sucks-at-javascript
  • 35
  • 6
  • What do you think `copy` does? How are you using it? – Scott Hunter Nov 26 '19 at 20:59
  • I suggest changing `copy()` to just copy the 8x8 array, and then instead of trying to set `self`, just reset the 8x8 array to the saved array. – John Anderson Nov 26 '19 at 21:03
  • 1
    I think the error is you are reassigning the self variable inside your function to the return result of temp.copy(). Python creates a new variable self and that's it. So your reference to the original object is lost. If you want to change the self object, update one of its properties, instead of reassigning the result. – Arun Nov 26 '19 at 21:04
  • Thanks for your suggestions. I was missing a `placeQueen` call in solve, I just made an error in copying my code and deleting some comments. – sucks-at-javascript Nov 26 '19 at 22:49
  • I was using copy as a way to "copy" a Board object's board into another Board object. I did so in order to have a saved board in case I wanted to undo a queen's placement during the backtracking, if that makes sense. – sucks-at-javascript Nov 26 '19 at 22:52
  • It does, but as my post points out, it's a poor way to do this. Feel free to benchmark my version against your (working) version and run it up to, say, `n=16`. You'll likely see that the heap allocations totally destroy the performance. Let me know if they don't and I'll stand corrected. – ggorlen Nov 26 '19 at 23:08

2 Answers2

1

I believe your problem is related to redefining self in the solve method, andi'm not even sure why you're doing that.

See this question for more details: Is it safe to replace a self object by another object of the same type in a method?

Reassigning self like you're doing is not reassigning the "b1" reference. So when you reference b1 again and do printBoard, you're referencing a different object than what "self.printBoard()" will be referencing by the time solve is done.

I would step back and ask yourself why you're replacing self to begin with, and what this gains you. You likely don't need too and shouldn't be doing it either.

TheKewlStore
  • 304
  • 1
  • 6
1

I'm not sure how this works since placeQueen is never called. As such, I don't see that adding a print as suggested presents a finished board (I see it as empty). [note: the latest update fixes this]

Using the restricted squares idea could work, but the way it's implemented here (without an undo option) is inefficient; copying a whole new Board object for every inner loop is very expensive. For all the trouble, we could just as well perform an iterative conflict check per move which at least saves the allocation and garbage collection costs of a new heap object.

As far as returning the completed board result, use a return value of self or self.board and None on failure rather than True and False.

A few other points:

  • Since solving a puzzle doesn't require state and we can (hopefully) agree that copying the board is inefficient, I'm not sure if there's much point in allowing an __init__ method. The class is nice as an encapsulation construct and we should hide static variables like EMPTY, QUEEN, etc inside the Board class regardless of whether the class is static or instantiated.
  • If you do decide to keep the class stateful, printBoard should not produce side effects--override __str__ instead.
  • Don't hardcode size literals such as 8 throughout the code; this makes the class rigid, difficult to maintain and prone to typos and off-by-one errors. Use len(self.board) instead and provide parameters liberally.
  • fillDiagonal doesn't need to be recursive. Consider using list comprehensions or numpy to simplify this matrix traversal logic.
  • Use snake_case variable names and docstrings instead of hashtag comments per PEP-8. If you feel compelled to write a comment like # restricts column, consider moving the relevant chunk to a function called restrict_column(...) and skip the comment.

Here's an initial rewrite that implements a few of these points:

class Board:
    EMPTY = 0
    QUEEN = 1
    DIRS = [(x, y) for x in range(-1, 2) for y in range(-1, 2) if x]

    def __init__ (self, size=8):
        self.board = [[Board.EMPTY] * size for _ in range(size)]

    def __str__(self):
        return "\n".join(map(str, self.board))

    def legal_from(self, row, col, dr, dc):
        while row >= 0 and row < len(self.board) and \
              col >= 0 and col < len(self.board[row]):
            if self.board[row][col] != Board.EMPTY:
                return False

            row += dr; col += dc

        return True

    def legal_move(self, row, col):
        return all([self.legal_from(row, col, *d) for d in Board.DIRS])

    def solve(self, row=0):
        if row >= len(self.board): 
            return self

        for col in range(len(self.board[row])):
            if self.legal_move(row, col):
                self.board[row][col] = Board.QUEEN

                if self.solve(row + 1):
                    return self

                self.board[row][col] = Board.EMPTY

if __name__ == "__main__":
    for result in [Board(i).solve() for i in range(9)]:
        print(result, "\n")

Output:

[1]

None

None

[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]

[1, 0, 0, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 0, 1]
[0, 1, 0, 0, 0]
[0, 0, 0, 1, 0]

[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0]

[1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0]

[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]
ggorlen
  • 44,755
  • 7
  • 76
  • 106