I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Talk:Peaceful chess queen armies

From Rosetta Code

Original Python exhaustive search[edit]

I was experimenting with various things when doing the Python. This is the original:

Exhaustive search.

from itertools import combinations, count
from functools import lru_cache, reduce
 
 
# n-by-n board
n = 5
 
def _2d(n=n):
for i in range(n):
print(' '.join(f'{i},{j}' for j in range(n)))
 
def _1d(n=n):
for i in range(0, n*n, n):
print(', '.join(f'{i+j:2}' for j in range(n)))
 
_bbullet, _wbullet = '\u2022\u25E6'
#_bqueen, _wqueen = 'BW'
_bqueen, _wqueen = '\u265B\u2655'
_bqueenh, _wqueenh = '&#x265b;', '<font color="green">&#x2655;</font>'
_or = set.__or__
 
 
def place(m, n):
"Place m black and white queens, peacefully, on an n-by-n board"
 
# 2-D Board as 1-D array: 2D(x, y) == 1D(t%n, t//n)
board = set(range(n*n))
 
#placements = list(combinations(board, m))
placements = {frozenset(c) for c in combinations(board, m)}
for blacks in placements:
black_attacks = reduce(_or,
(queen_attacks_from(pos, n) for pos in blacks),
set())
#for whites in placements:
for whites in {frozenset(c) for c in combinations(board - black_attacks, m)}:
if not black_attacks & whites:
return blacks, whites
return set(), set()
 
@lru_cache(maxsize=None)
def queen_attacks_from(pos, n=n):
a = set([pos]) # Its position
a.update(range(pos//n*n, pos//n*n+n)) # Its row
a.update(range(pos%n, n*n, n)) # Its column
# Diagonals
x0, y0 = pos%n, pos//n
for x1 in range(n):
# l-to-r diag
y1 = y0 -x0 +x1
if 0 <= y1 < n:
a.add(x1 + y1 * n)
# r-to-l diag
y1 = y0 +x0 -x1
if 0 <= y1 < n:
a.add(x1 + y1 * n)
return a
 
def pboard(black_white=None, n=n):
if black_white is None:
blk, wht = set(), set()
else:
blk, wht = black_white
print(f"## {len(blk)} black and {len(wht)} white queens "
f"on a {n}-by-{n} board:", end='')
for xy in range(n*n):
if xy %n == 0:
print()
ch = ('?' if xy in blk and xy in wht
else _bqueen if xy in blk
else _wqueen if xy in wht
else _bbullet if (xy%n + xy//n)%2 else _wbullet)
print('%s' % ch, end='')
print()
 
def hboard(black_white=None, n=n):
if black_white is None:
blk, wht = set(), set()
else:
blk, wht = black_white
out = (f"<br><b>## {len(blk)} black and {len(wht)} white queens "
f"on a {n}-by-{n} board:</b><br>\n")
out += "<table>\n "
tbl = ''
for xy in range(n*n):
if xy %n == 0:
tbl += '</tr>\n <tr>\n'
ch = ('<span style="color:red">?</span>' if xy in blk and xy in wht
else _bqueenh if xy in blk
else _wqueenh if xy in wht
else "")
bg = "" if (xy%n + xy//n)%2 else ' bgcolor="silver"'
tbl += f' <td style="width:16pt; height:16pt;"{bg}>{ch}</td>\n'
out += tbl[7:]
out += '</tr>\n</table>\n<br>\n'
return out
 
if __name__ == '__main__':
n=2
html = ''
for n in range(2, 7):
print()
queen_attacks_from.cache_clear() # memoization cache
#
for m in count(1):
ans = place(m, n)
if ans[0]:
pboard(ans, n)
html += hboard(ans, n)
else:
comment = f"# Can't place {m}+ queens on a {n}-by-{n} board"
print (comment)
html += f"<b>{comment}</b><br><br>\n\n"
break
print('\n')
html += '<br>\n'
#
m, n = 5, 7
queen_attacks_from.cache_clear()
ans = place(m, n)
pboard(ans, n)
html += hboard(ans, n)
with open('peaceful_queen_armies.htm', 'w') as f:
f.write(html)
Output:

The console output Unicode queen characters display wider than other characters in monospace font so the alternative HTML output is shown below.

# Can't place 1+ queens on a 2-by-2 board


## 1 black and 1 white queens on a 3-by-3 board:


# Can't place 2+ queens on a 3-by-3 board


## 1 black and 1 white queens on a 4-by-4 board:



## 2 black and 2 white queens on a 4-by-4 board:


# Can't place 3+ queens on a 4-by-4 board


## 1 black and 1 white queens on a 5-by-5 board:



## 2 black and 2 white queens on a 5-by-5 board:



## 3 black and 3 white queens on a 5-by-5 board:



## 4 black and 4 white queens on a 5-by-5 board:


# Can't place 5+ queens on a 5-by-5 board


## 1 black and 1 white queens on a 6-by-6 board:



## 2 black and 2 white queens on a 6-by-6 board:



## 3 black and 3 white queens on a 6-by-6 board:



## 4 black and 4 white queens on a 6-by-6 board:



## 5 black and 5 white queens on a 6-by-6 board:


# Can't place 6+ queens on a 6-by-6 board



## 5 black and 5 white queens on a 7-by-7 board:


--Paddy3118 (talk) 10:08, 27 March 2019 (UTC)

Error in solution?[edit]

No solutions for {8,9},{10,14} and some other boards. For {9, 12} correctly:

12 black and 12 white queens on a 9 x 9 board:
B * x * B * x * B
* x W x * x W x *
B * x * B * x * B
* x W x * x W x *
B * x * B * x * B
* x W x * x W x *
B * x * B * x * B
* x W x * x W x *
x W x W x W x W x

I checked C and C++ codes and compare results from https://oeis.org/A250000

Hi, Please sign your contribution bove, thanks. --Paddy3118 (talk) 10:58, 19 January 2020 (UTC)

If you carefully check the wording of the task, it doesn't ask for maximum numbers of armies.
Language implementations might well have implied this though which may need individual mods.
Thanks for spotting it. --Paddy3118 (talk) 10:58, 19 January 2020 (UTC)