Queens on chessboard solved randomly in Python

Question

The idea is to try solve the "queen problem" by totally placing the queens totally random in each row of the chess board, and see how many repetitions it takes to solve it. The chess board can be any size.

My idea is to create s lists, each containing s "empty" characters (underscores). Then for each line randomly pick a position to insert the queen ("I" value) and then mark all the positions below and diagonally down (I'm going row-by-row, so I don't have to bother about rows above) with X. if in any iteration the randomly chosen position for the queen matches with position of any X in that row, I start the new chessboard from scratch.

I have something like this, but it seems to get stuck on line 19 (marked with a comment), but it doesn't give me any error. What can be wrong? Also, is my solution (apart that line) correct?

from random import *


#Success flag
success = 0

#Trials counter
trials = 0


s = input ("enter board size\n")
s = int(s)
block = 1 #blockade
queen = 2 #queen
board = [[0 for x in range(s)] for y in range(s)] 

while success == 0:
    for y in range (0, s-1):
        pos = randint(0,s-1)    #line 19
        if board[y][pos] != block:
            board[y][pos] = queen
            a = 1
            for z in range (y, s-2):
                board[z + 1][pos] = block
                if pos - a >= 0:
                    board[z + 1][pos - a] = block
                if pos + a <= s-1:
                    board[z + 1][pos + a] = block
                a = a + 1
            success = 1
        else:
            success = 0


#Printing board
for y in range (0, s-1):
    print (board[y])

print ("Number of trials:\n")
print (trials)

Answer 1

Some issues:

• The second argument to the range function represents the first number that will not be visited, so most of the time you have it one short.
• You need to exit the loop on y at a failed attempt: you don't want to continue with the next row, but restart
• You need to reset the board after each failed attempt, or otherwise put: before each attempt
• You should build in some safety to exit if no solution is found after many iterations, otherwise you risk it to get stuck. For input 1, 2 or 3, there is no solution.
• The trials number is never increased
• Instead of blindly choosing a position, you'd better only select from among the available positions (not blocked), or you will be going for an amazing number of trials: for size 8, it would not be unusual to need 100 000 trials without this filtering in place!

See the corrected code, with comments where I made changes:

import random

s = input ("enter board size\n")
s = int(s)
trials = 0
block = 1
queen = 2
# add some maximum to the number of attempts
max_trials = 100000 
success = 0

# add safety measure to avoid infinite looping
while success == 0 and trials <= max_trials:
    # initialise board before every trial
    board = [[0 for x in range(s)] for y in range(s)]
    # assume success until failure
    success = 1
    # count trials
    trials += 1 
    for y in range (0, s): # use correct range
        # get the fields that are still available in this row
        available = [x for x, i in enumerate(board[y]) if i == 0]
        if len(available) == 0:
            success = 0
            # exit for loop, you want to start a next trial
            break
        # choose a random position among available spots only
        pos = available[random.randint(0, len(available)-1)]    
        board[y][pos] = queen
        a = 1
        for z in range (y+1, s): # use correct range
            board[z][pos] = block
            if pos - a >= 0:
                board[z][pos - a] = block
            if pos + a < s:
                board[z][pos + a] = block
            a = a + 1

for y in range (0, s): # use correct range
    print (board[y])

print ("Number of trials:", trials)

Answer 2

After you try different row and fail this time, you have to create a new empty board and if success is 0, you should break the for loop as following.

while success == 0:
    board = [[0 for x in range(s)] for y in range(s)]
    for y in range (0, s):
        pos = randint(0,s-1)    #line 19
        if board[y][pos] != block:
            board[y][pos] = queen
            for i in range(y+1, s):
                board[i][pos] = block
            success = 1
        else:
            success = 0
            break
    trials += 1

You can follow the same logic to implement diagonal cases.

Answer 3

Here is a short solution based on doing arithmetic on the coordinates of the placed queens:

import random, itertools

def clashes(p,q):
    a,b = p
    c,d = q
    return a == c or b == d or abs(a-c) == abs(b-d)

def solution(queens):
    #assumes len(queens) == 8
    return not any(clashes(p,q) for p,q in itertools.combinations(queens,2)) 

def randSolve():
    counter = 0
    while True:
        counter += 1
        queens = [(i,random.randint(1,8)) for i in range(1,9)]
        if solution(queens): return counter, queens

print(randSolve())

Last time I ran it I got:

(263528, [(1, 4), (2, 7), (3, 3), (4, 8), (5, 2), (6, 5), (7, 1), (8, 6)])

meaning that the first solution was encountered after 263527 failures. On average, you can expect to go through 182360 failures before you get a success.