Skip to content

Instantly share code, notes, and snippets.

@axiomsofchoice

axiomsofchoice/algebraic.py

Last active February 1, 2016 09:57
Show Gist options
  • Save axiomsofchoice/1682be79af8863cb0041 to your computer and use it in GitHub Desktop.
Save axiomsofchoice/1682be79af8863cb0041 to your computer and use it in GitHub Desktop.
Download ZIP
Solution to "Algebraic" from Stage 5 of Director GCHQ's Christmas Puzzle 2015
Raw
algebraic.py
#!/usr/bin/env python
"""
Solution to "Algebraic" from Stage 5 of Director GCHQ's Christmas Puzzle 2015.
==============================================================================
http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Director%27s-Christmas-puzzle-2015.aspx
Puzzle Crown Copyright.
SPOILER ALERT - If you're attempting the puzzle and you don't want to find out
any hints do not read ahead!
This is an almost verbatim version of the script I used to find all the winning boards of this puzzle (for I've included some code such as print statements that it might be useful to tidy up; also some comments may be incorrect in places; I completed it around 01/01/2016 after which I've forgotten some of the reasoning). At the time of writing (31/01/2016) I'm not entirely sure it's the complete solution to the puzzle but it is as far as I could get with it.
The first part of the code is a collection of functions (plus a few unit tests) that do the bulk of the work to brute-force a solution. In the latter part of the code we run different stages of solution searching. Between each stage lists of candidate solutions are written out to files to make it quicker to re-run a stage. As you we see the partial solutions from previous stages are used to build a set of heuristics that can be used to filter the candidates into the following stage. These heuristics took quite a bit of trial and error.
-----------
The MIT License (MIT)
Copyright (c) 2015-2016 Dan Hagon.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
"""
import itertools
######################
# Problem definition #
######################
# Note we use R for Knight (and not rook - my mistake as I'm not a strong chess player) and C for Castle.
# Use index() to map letters to encodings.
encodingMap = "PRBCKQ"
assert len(encodingMap) == 6
# Left operands (2 rows of 4 columns)
left_operand = [
[['__','wB','wQ','bB'],['__','bR','__','bP']],
[['wK','__','wC','bC'],['__','__','__','__']],
[['__','bR','__','__'],['wB','__','wP','bK']],
[['bQ','__','wQ','__'],['wC','__','__','__']],
[['wP','__','__','__'],['__','wC','wR','bP']],
[['bK','wR','__','wP'],['__','__','__','wK']],
[['__','__','wK','bC'],['wB','__','__','wC']],
[['__','bK','bR','wP'],['__','wB','wC','wR']],
[['__','__','__','__'],['__','__','wB','bQ']]
]
# Right operands (4 rows of 2 columns)
right_operand = [
[['wB','bC'],['__','bR'],['__','__'],['__','__']],
[['__','bB'],['__','bQ'],['__','wK'],['__','__']],
[['wK','__'],['__','__'],['bC','bP'],['wR','bK']],
[['bK','bB'],['bR','bQ'],['bP','bC'],['wK','__']],
[['bP','bB'],['bQ','__'],['wR','__'],['__','wQ']],
[['bK','__'],['bB','__'],['wR','__'],['__','__']],
[['bR','bB'],['__','bC'],['__','wC'],['__','__']],
[['wP','__'],['__','bP'],['bQ','__'],['wC','bP']],
[['__','wR'],['__','wQ'],['__','bR'],['bK','__']]
]
assert len(left_operand) == len(right_operand)
##########################################
# Implementation of board multiplication #
##########################################
def dolookup(perm, l, r, guessedBoard=None):
"""Performs a mutliplication using the provided table."""
if guessedBoard and not \
guessedBoard[encodingMap.index(l)][encodingMap.index(r)] == "*":
return guessedBoard[encodingMap.index(l)][encodingMap.index(r)]
else:
return perm[encodingMap.index(l)][encodingMap.index(r)]
def chessmult(L, R, perm, qerm, justPrintFactors=False, \
guessedWhite=None, guessedBlack=None):
"""Mutliply two chess board lists using the provided multiplication tables.
"""
# Need to explicitly create the board here to avoid duplicate object refs.
board = [
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]
]
# Rows of L...
for i in range(2):
# ...then colums of L.
for j in range(4):
# Columns of R...
for k in range(2):
# ...then row of R.
for l in range (4):
#print board
#print k+(j*2), (i*4)+l
#assert board[(i*4)+l][k+(j*2)] == 0
#print
if L[i][j][0] == 'w' and R[l][k][0] == 'w':
if justPrintFactors:
if guessedWhite and not \
guessedWhite[encodingMap.index(L[i][j][1])][encodingMap.index(R[l][k][1])] == "*":
board[(i*4)+l][k+(j*2)] = "w" + \
dolookup(perm, L[i][j][1], R[l][k][1], \
guessedWhite) + "_"
else:
board[(i*4)+l][k+(j*2)] = "w" + \
L[i][j][1] + R[l][k][1]
else:
#print L[i][j][1], R[l][k][1], \
# dolookup(perm, L[i][j][1], R[l][k][1])
board[(i*4)+l][k+(j*2)] = "w" + \
dolookup(perm, L[i][j][1], R[l][k][1])
elif L[i][j][0] == 'b' and R[l][k][0] == 'b':
if justPrintFactors:
if guessedBlack and not \
guessedBlack[encodingMap.index(L[i][j][1])][encodingMap.index(R[l][k][1])] == "*":
board[(i*4)+l][k+(j*2)] = "b" + \
dolookup(perm, L[i][j][1], R[l][k][1], \
guessedBlack) + "_"
else:
board[(i*4)+l][k+(j*2)] = "b" + \
L[i][j][1] + R[l][k][1]
else:
board[(i*4)+l][k+(j*2)] = "b" + \
dolookup(qerm, L[i][j][1], R[l][k][1])
else:
if justPrintFactors:
board[(i*4)+l][k+(j*2)] = "___"
else:
board[(i*4)+l][k+(j*2)] = "__"
return board
########################################################################
# Tests for code that determines valid boards (in terms of just kings) #
########################################################################
failingboard1 = [
# 2 white; 1 black
[['__', '__', 'wK', '__', 'wK', '__', '__', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bC'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', 'bK', '__', '__', '__', 'bC'],
['__', '__', '__', 'bB', '__', '__', '__', 'bR'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bK'],
['__', 'wK', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'bR', 'bR', '__', '__', '__', '__'],
['__', '__', '__', 'bQ', '__', '__', '__', '__'],
['wP', '__', '__', '__', 'wK', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'bR', 'bK'],
['wC', '__', '__', '__', 'wR', '__', '__', 'bB']],
# 1 white; 1 black
[['bC', 'bR', '__', '__', '__', '__', '__', '__'],
['bP', 'bK', '__', '__', '__', '__', '__', '__'],
['bQ', 'bB', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', 'wC', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['wK', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['wR', '__', '__', '__', '__', '__', '__', '__'],
['__', 'wQ', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'bP', 'bB'],
['__', '__', '__', '__', '__', '__', 'bK', '__'],
['__', '__', 'wK', '__', 'wB', '__', '__', '__'],
['__', '__', '__', 'wB', '__', 'wP', '__', '__']],
# 1 white; 1 black
[['bK', '__', '__', '__', '__', '__', '__', '__'],
['bP', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'wK', '__', '__', '__', 'wR', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'wQ', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', 'bK', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bK'],
['__', '__', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', 'wQ', '__', '__', '__', '__', '__', 'wP'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', 'wP', '__'],
['__', '__', '__', 'bK', '__', 'bR', '__', '__'],
['__', '__', 'bC', '__', 'bP', '__', '__', '__'],
['__', '__', '__', 'bQ', '__', 'bR', 'wC', '__'],
['__', '__', 'wB', '__', 'wC', '__', 'wR', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'wQ', '__', 'wP', '__', 'wK', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', 'wK', '__', '__'],
['__', '__', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', 'bP'],
['__', '__', '__', '__', '__', '__', 'bK', '__']]
]
failingboard2 = [
# 1 white; 1 black
[['__', '__', 'wK', '__', 'wR', '__', '__', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bC'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', 'bK', '__', '__', '__', 'bC'],
['__', '__', '__', 'bB', '__', '__', '__', 'bR'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bK'],
['__', 'wK', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'bR', 'bR', '__', '__', '__', '__'],
['__', '__', '__', 'bQ', '__', '__', '__', '__'],
['wP', '__', '__', '__', 'wK', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'bR', 'bK'],
['wC', '__', '__', '__', 'wR', '__', '__', 'bB']],
# 1 white; 1 black
[['bC', 'bR', '__', '__', '__', '__', '__', '__'],
['bP', 'bK', '__', '__', '__', '__', '__', '__'],
['bQ', 'bB', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', 'wC', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['wK', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['wR', '__', '__', '__', '__', '__', '__', '__'],
['__', 'wQ', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'bP', 'bB'],
['__', '__', '__', '__', '__', '__', 'bK', '__'],
['__', '__', 'wK', '__', 'wB', '__', '__', '__'],
['__', '__', '__', 'wB', '__', 'wP', '__', '__']],
# 1 white; 1 black
[['bK', '__', '__', '__', '__', '__', '__', '__'],
['bP', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'wK', '__', '__', '__', 'wR', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'wQ', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', 'bK', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bK'],
['__', '__', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', 'wQ', '__', '__', '__', '__', '__', 'wP'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', 'wP', '__'],
['__', '__', '__', 'bK', '__', 'bR', '__', '__'],
['__', '__', 'bC', '__', 'bP', '__', '__', '__'],
['__', '__', '__', 'bQ', '__', 'bR', 'wC', '__'],
['__', '__', 'wB', '__', 'wC', '__', 'wR', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'wQ', '__', 'wP', '__', 'wK', '__']],
# 1 white; 0 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', 'wK', '__', '__'],
['__', '__', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', 'bP'],
['__', '__', '__', '__', '__', '__', 'bR', '__']]
]
passingboard = [
# 1 white; 1 black
[['__', '__', 'wK', '__', 'wR', '__', '__', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bC'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', 'bK', '__', '__', '__', 'bC'],
['__', '__', '__', 'bB', '__', '__', '__', 'bR'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bK'],
['__', 'wK', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'bR', 'bR', '__', '__', '__', '__'],
['__', '__', '__', 'bQ', '__', '__', '__', '__'],
['wP', '__', '__', '__', 'wK', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'bR', 'bK'],
['wC', '__', '__', '__', 'wR', '__', '__', 'bB']],
# 1 white; 1 black
[['bC', 'bR', '__', '__', '__', '__', '__', '__'],
['bP', 'bK', '__', '__', '__', '__', '__', '__'],
['bQ', 'bB', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', 'wC', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['wK', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['wR', '__', '__', '__', '__', '__', '__', '__'],
['__', 'wQ', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'bP', 'bB'],
['__', '__', '__', '__', '__', '__', 'bK', '__'],
['__', '__', 'wK', '__', 'wB', '__', '__', '__'],
['__', '__', '__', 'wB', '__', 'wP', '__', '__']],
# 1 white; 1 black
[['bK', '__', '__', '__', '__', '__', '__', '__'],
['bP', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'wK', '__', '__', '__', 'wR', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'wQ', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', 'bR', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bK'],
['__', '__', '__', '__', '__', 'wK', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', 'wQ', '__', '__', '__', '__', '__', 'wP'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', 'wP', '__'],
['__', '__', '__', 'bK', '__', 'bR', '__', '__'],
['__', '__', 'bC', '__', 'bP', '__', '__', '__'],
['__', '__', '__', 'bQ', '__', 'bR', 'wC', '__'],
['__', '__', 'wB', '__', 'wC', '__', 'wR', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'wQ', '__', 'wP', '__', 'wK', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', 'wK', '__', '__'],
['__', '__', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', 'bP'],
['__', '__', '__', '__', '__', '__', 'bK', '__']]
]
passingboardJustWhite = [
# 1 white; 1 black
[['__', '__', 'wK', '__', 'wR', '__', '__', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bC'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', 'bK', '__', '__', '__', 'bC'],
['__', '__', '__', 'bB', '__', '__', '__', 'bR'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 0 black
[['__', '__', '__', '__', '__', '__', '__', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bR'],
['__', 'wK', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'bR', 'bR', '__', '__', '__', '__'],
['__', '__', '__', 'bQ', '__', '__', '__', '__'],
['wP', '__', '__', '__', 'wK', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'bR', 'bK'],
['wC', '__', '__', '__', 'wR', '__', '__', 'bB']],
# 1 white; 1 black
[['bC', 'bR', '__', '__', '__', '__', '__', '__'],
['bP', 'bK', '__', '__', '__', '__', '__', '__'],
['bQ', 'bB', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', 'wC', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['wK', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['wR', '__', '__', '__', '__', '__', '__', '__'],
['__', 'wQ', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'bP', 'bB'],
['__', '__', '__', '__', '__', '__', 'bK', '__'],
['__', '__', 'wK', '__', 'wB', '__', '__', '__'],
['__', '__', '__', 'wB', '__', 'wP', '__', '__']],
# 1 white; 1 black
[['bK', '__', '__', '__', '__', '__', '__', '__'],
['bP', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'wK', '__', '__', '__', 'wR', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'wQ', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', 'bR', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bK'],
['__', '__', '__', '__', '__', 'wK', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', 'wQ', '__', '__', '__', '__', '__', 'wP'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', 'wP', '__'],
['__', '__', '__', 'bK', '__', 'bR', '__', '__'],
['__', '__', 'bC', '__', 'bP', '__', '__', '__'],
['__', '__', '__', 'bQ', '__', 'bR', 'wC', '__'],
['__', '__', 'wB', '__', 'wC', '__', 'wR', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'wQ', '__', 'wP', '__', 'wK', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', 'wK', '__', '__'],
['__', '__', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', 'bP'],
['__', '__', '__', '__', '__', '__', 'bK', '__']]
]
passingboardJustBlack = [
# 1 white; 1 black
[['__', '__', 'wK', '__', 'wR', '__', '__', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bC'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', 'bK', '__', '__', '__', 'bC'],
['__', '__', '__', 'bB', '__', '__', '__', 'bR'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bK'],
['__', 'wK', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 0 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'bR', 'bR', '__', '__', '__', '__'],
['__', '__', '__', 'bQ', '__', '__', '__', '__'],
['wP', '__', '__', '__', 'wR', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'bR', 'bK'],
['wC', '__', '__', '__', 'wR', '__', '__', 'bB']],
# 1 white; 1 black
[['bC', 'bR', '__', '__', '__', '__', '__', '__'],
['bP', 'bK', '__', '__', '__', '__', '__', '__'],
['bQ', 'bB', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', 'wC', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['wK', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['wR', '__', '__', '__', '__', '__', '__', '__'],
['__', 'wQ', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'bP', 'bB'],
['__', '__', '__', '__', '__', '__', 'bK', '__'],
['__', '__', 'wK', '__', 'wB', '__', '__', '__'],
['__', '__', '__', 'wB', '__', 'wP', '__', '__']],
# 1 white; 1 black
[['bK', '__', '__', '__', '__', '__', '__', '__'],
['bP', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'wK', '__', '__', '__', 'wR', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', 'wQ', '__'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', 'bR', 'bQ'],
['__', '__', '__', '__', '__', '__', '__', 'bK'],
['__', '__', '__', '__', '__', 'wK', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', 'wQ', '__', '__', '__', '__', '__', 'wP'],
['__', '__', '__', '__', '__', '__', '__', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', 'wP', '__'],
['__', '__', '__', 'bK', '__', 'bR', '__', '__'],
['__', '__', 'bC', '__', 'bP', '__', '__', '__'],
['__', '__', '__', 'bQ', '__', 'bR', 'wC', '__'],
['__', '__', 'wB', '__', 'wC', '__', 'wR', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', 'wQ', '__', 'wP', '__', 'wK', '__']],
# 1 white; 1 black
[['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', '__'],
['__', '__', '__', '__', '__', 'wK', '__', '__'],
['__', '__', '__', '__', '__', 'wR', '__', '__'],
['__', '__', '__', '__', '__', '__', '__', 'bP'],
['__', '__', '__', '__', '__', '__', 'bK', '__']]
]
def checkboards(boards, justWhites=True, justBlacks=True):
"""Check all boards have exactly one each of black/white king.
"""
for b in boards:
#print b
numKingWhite = 0
numKingBlack = 0
for r in b:
for c in r:
if c[1] == 'K':
if justWhites and c[0] == 'w':
numKingWhite += 1
elif justBlacks and c[0] == 'b':
numKingBlack += 1
# More than one king found on at least one board
if (justWhites and numKingWhite > 1) \
or (justBlacks and numKingBlack > 1):
return False
# Board found without exactly one king each
if (justWhites and not(numKingWhite == 1)) \
or (justBlacks and not(numKingBlack == 1)):
return False
# All boards pass the test
return True
# Test that the function checkboards() really does catch the number of Kings.
assert checkboards(failingboard1, justWhites=True, justBlacks=True) == False
assert checkboards(failingboard2, justWhites=True, justBlacks=True) == False
assert checkboards(passingboard, justWhites=True, justBlacks=True) == True
assert checkboards(passingboardJustWhite, justWhites=True, justBlacks=False) == True
assert checkboards(passingboardJustWhite, justWhites=False, justBlacks=True) == False
assert checkboards(passingboardJustBlack, justWhites=True, justBlacks=False) == False
assert checkboards(passingboardJustBlack, justWhites=False, justBlacks=True) == True
####################################################################
# Build all possible permutations of (valid) multiplication tables #
####################################################################
def nextletterinrow(rowsabove, n, q, my_nextrow):
# n is number of rows above and q is distance along row (to be filled)
#assert len(rowsabove) == n
# Make a new copy
nextrow = [m for m in my_nextrow]
#print "nextrow[:(q-1)] %s" % nextrow[:(q-1)]
possibleletters = [l for l in encodingMap if \
not(l in [rowsabove[i][q] for i in range(n)])\
and not(l in nextrow[:(q)])]
#print "possibleletters %s" % possibleletters
if q == 5:
if len(possibleletters) == 1 and not (possibleletters[0] in \
[rowsabove[i][q] for i in range(n)]):
nextrow[q] = possibleletters[0]
#print "found one"
yield nextrow
else:
#print "backtrack"
pass
else:
for s in possibleletters:
#print "rowsabove %s" % rowsabove
assert not (s in [rowsabove[i][q] for i in range(n-1)])
nextrow[q] = s
#print "nextrow inner %s" % nextrow
for inner in nextletterinrow(rowsabove, n, q+1, nextrow):
yield inner
# The reason why each row and column must always have all elements:
# https://en.wikipedia.org/wiki/Cayley_table#Permutations
# https://en.wikipedia.org/wiki/Cancellation_property
# Interesting associativity test:
# https://en.wikipedia.org/wiki/Light%27s_associativity_test
# Wondering how to compute the number of combinations. Perhaps Hook numbers can help? https://www.youtube.com/watch?v=vgZhrEs4tuk&feature=youtu.be
# Turns out formulae for number of latin squares is hard to come up with: https://en.wikipedia.org/wiki/Latin_square
def doRowNN(rowsabove, n):
"""Compute each of the valid permutations of the current row given the previous."""
nextrow = [rowsabove[i][n] if i < n else '' for i in range(6)]
#print "nextrow %s" % nextrow
for lin in nextletterinrow(rowsabove, n, n, nextrow):
yield lin
def doallmultperms():
"""Compute all valid permutations of multiplication tables."""
#count = 0
for newrow in itertools.permutations(encodingMap):
row1 = list(newrow)
#print
#print " %s" % row1
#print list(row1)
#for row2 in doRow2(row1):
for row2 in doRowNN([row1],1):
for row3 in doRowNN([row1,row2],2):
for row4 in doRowNN([row1,row2,row3],3):
for row5 in doRowNN([row1,row2,row3,row4],4):
for row6 in doRowNN([row1,row2,row3,row4,row5],5):
##pass
#print
#for mr in [row1,row2,row3,row4,row5,row6]:
# print mr
#exit(0)
#count += 1
yield [row1,row2,row3,row4,row5,row6]
#This yields: 328320
#print count
def determineallpermutations():
"""
Outputs all possible multiplication tables out to a csv file.
Should give a csv file with 328320 lines
"""
f = open("correct_ones.csv", 'w')
count = 0
for p in doallmultperms():
if not(count % 1000):
print count
#print ["".join(i) for i in p]
#for r in range(6):
# print p[r]
#for r in range(6):
# print (['_']*r)+p[r][r:]
f.write("%s,%s,%s,%s,%s,%s\n" % tuple(["".join(i) for i in p]))
count += 1
f.close()
print count
#############################################################################
# Multiplication Table Filters (applied one per stage; see later for notes) #
#############################################################################
def findallkingletons():
"""
Stage 0.
Filters the original list of permutations to find just the ones that have one king of each colour per board (this is done separately for white and black).
"""
f = open("correct_ones.csv", 'r')
gw = open("correct_ones_white_kings.csv", 'w')
gb = open("correct_ones_black_kings.csv", 'w')
count = 0
numcorrectw = 0
numcorrectb = 0
numbersofkings = dict()
for fline in f.readlines():
if not(count % 1000):
print count
p = fline[:-1].split(",")
# Determine the distribution of kings across all tables (this was useful whilst we were manually computing possible king positions in the multiplication table)
# Gives {3: 176400, 4: 140400, 5: 10800, 6: 720}
numkings = 0
for r in range(6):
#print p[r][r:]
for c in p[r][r:]:
if c == "K":
numkings += 1
if numkings not in numbersofkings:
numbersofkings[numkings] = 1
else:
numbersofkings[numkings] += 1
#print numkings
#print p
# Check each possible king position to see which multiplication tables fit the pattern
boards = [chessmult(left_operand[i], right_operand[i], p, p) \
for i in range(len(left_operand))]
# Gives 11760 possible solutions.
if checkboards(boards, justWhites=True, justBlacks=False):
# Everything points to this being the right pattern
"""
whitekingpositions = [
['*', 'K', '*', '*', '*', '*'],
['_', '*', '*', '*', '*', '*'],
['_', '_', '*', '*', '*', 'K'],
['_', '_', '_', '*', 'K', '*'],
['_', '_', '_', '_', '*', '*'],
['_', '_', '_', '_', '_', '*']
]
"""
# Find anything that does not conform to this pattern (finds nothing)
if not( p[0][1] == "K" and \
p[2][5] == "K" and \
p[3][4] == "K"):
for r in range(6):
print (['_']*r)+["K" if c == "K" else "*" for c in p[r][r:]]
gw.write(fline)
numcorrectw += 1
# Gives 3120 possible solutions
if checkboards(boards, justWhites=False, justBlacks=True):
# Everything points to this being the right pattern
"""
blackkingpositions = [
['K', '*', '*', '*', '*', '*'],
['_', '*', '*', '*', '*', 'K'],
['_', '_', '*', 'K', '*', '*'],
['_', '_', '_', '*', '*', '*'],
['_', '_', '_', '_', 'K', '*'],
['_', '_', '_', '_', '_', '*']
]
"""
# Find anything that does not conform to this pattern (finds nothing)
if not( p[0][0] == "K" and \
p[1][5] == "K" and \
p[2][3] == "K" and \
p[4][4] == "K"):
for r in range(6):
print (['_']*r)+["K" if c == "K" else "*" for c in p[r][r:]]
gb.write(fline)
numcorrectb += 1
# Count the number of kings in the multiplication table
#for r in range(6):
# print (['_']*r)+["K" if c == "K" else "*" for c in p[r][r:]]
#continue
count += 1
print count, numcorrectw, numcorrectb
print numbersofkings
def filterforcheckmate():
"""
Stage 1.
Filter all the boards with just one king by those where the king is not in check mate. This is mostly eye-balled.
"""
fw = open("correct_ones_white_kings.csv", 'r')
fb = open("correct_ones_black_kings.csv", 'r')
gw = open("correct_ones_white_kings_not_mate.csv", 'w')
gb = open("correct_ones_black_kings_not_mate.csv", 'w')
count = 0
numcorrectw = 0
for fline in fw.readlines():
if not(count % 1000):
print count
count += 1
p = fline[:-1].split(",")
boards = [chessmult(left_operand[i], right_operand[i], p, p) \
for i in range(len(left_operand))]
assert checkboards(boards, justWhites=True, justBlacks=False)
# On board (5 and 6), 8 (middle two) and 9
# Reduces from 11760 to 1352
if \
not(p[encodingMap.index("R")][encodingMap.index("R")] in "BQ") and \
not(p[encodingMap.index("C")][encodingMap.index("P")] in "QC") and \
p[encodingMap.index("P")][encodingMap.index("C")] != "R" and \
not(p[encodingMap.index("B")][encodingMap.index("R")] in "QB") and \
True:
numcorrectw += 1
gw.write(fline)
fw.close()
gw.close()
print numcorrectw
print
count = 0 # Reset the count
numcorrectb = 0
for fline in fb.readlines():
if not(count % 1000):
print count
count += 1
p = fline[:-1].split(",")
boards = [chessmult(left_operand[i], right_operand[i], p, p) \
for i in range(len(left_operand))]
assert checkboards(boards, justWhites=False, justBlacks=True)
# Find anything that does conforms to these patterns, which define valid boards given that king positions are known.
# On board 2 we cannot have a black rook (C*Q) as other black piece
# On board 3 we cannot have the black piece able to take the white king
# On board 4 we cannot have the black piece directly above the white king able to more horizontally or vertically
# On board 7 we cannot have the black pieces closest to the white queen be rooks
# On board 8 we cannot have a black piece that can move diagonally (R*P) and take the white queen (black is moving down board so is valid here)
# On board 9 we cannot have a black rook (Q*K) as other black piece
# Redcues down to 56
if \
p[encodingMap.index("C")][encodingMap.index("Q")] != "R" and \
p[encodingMap.index("K")][encodingMap.index("C")] != "R" and \
not(p[encodingMap.index("Q")][encodingMap.index("P")] in "QC") and \
p[encodingMap.index("C")][encodingMap.index("R")] != "R" and \
p[encodingMap.index("C")][encodingMap.index("C")] != "R" and \
not(p[encodingMap.index("R")][encodingMap.index("P")] in "BQP") and \
p[encodingMap.index("Q")][encodingMap.index("K")] != "R" and \
True:
gb.write(fline)
numcorrectb += 1
fb.close()
gb.close()
print numcorrectb
def filterforvalidpawns():
"""
Stage 2.
Filter all the boards without illegal positions for pawns. This is mostly eye-balled, though could be automated fairly easily.
Find anything that does conforms to these patterns, which define valid boards given that no pawns can be along rows 1 and 8 for b and w resp.
https://en.wikipedia.org/wiki/Pawn_(chess)
"""
fw = open("correct_ones_white_kings_not_mate.csv", 'r')
fb = open("correct_ones_black_kings_not_mate.csv", 'r')
gw = open("correct_ones_white_pawns_valid.csv", 'w')
gb = open("correct_ones_black_pawns_valid.csv", 'w')
numcorrectw = 0
for fline in fw.readlines():
p = fline[:-1].split(",")
boards = [chessmult(left_operand[i], right_operand[i], p, p) \
for i in range(len(left_operand))]
assert checkboards(boards, justWhites=True, justBlacks=False)
# Board 1, 3, 5 (two), 8 (last four).
if \
p[encodingMap.index("B")][encodingMap.index("B")] != "P" and \
p[encodingMap.index("B")][encodingMap.index("R")] != "P" and \
p[encodingMap.index("C")][encodingMap.index("Q")] != "P" and \
p[encodingMap.index("R")][encodingMap.index("Q")] != "P" and \
p[encodingMap.index("P")][encodingMap.index("P")] != "P" and \
p[encodingMap.index("B")][encodingMap.index("C")] != "P" and \
p[encodingMap.index("C")][encodingMap.index("C")] != "P" and \
p[encodingMap.index("R")][encodingMap.index("C")] != "P" and \
True:
numcorrectw += 1
gw.write(fline)
fw.close()
gw.close()
print numcorrectw
print
numcorrectb = 0
for fline in fb.readlines():
p = fline[:-1].split(",")
boards = [chessmult(left_operand[i], right_operand[i], p, p) \
for i in range(len(left_operand))]
assert checkboards(boards, justWhites=False, justBlacks=True)
# Board 4 (first two), 7, 9.
if \
p[encodingMap.index("Q")][encodingMap.index("K")] != "P" and \
p[encodingMap.index("Q")][encodingMap.index("B")] != "P" and \
p[encodingMap.index("C")][encodingMap.index("R")] != "P" and \
p[encodingMap.index("Q")][encodingMap.index("K")] != "P" and \
True:
gb.write(fline)
numcorrectb += 1
fb.close()
gb.close()
print numcorrectb
def filterforknownpositions():
"""
Stage 3.
These rules come from a consideration of mate in 1, taking each multiplication table separately. This is mostly eye-balled.
"""
fw = open("correct_ones_white_pawns_valid.csv", 'r')
fb = open("correct_ones_black_pawns_valid.csv", 'r')
gw = open("correct_ones_white_known_positions.csv", 'w')
gb = open("correct_ones_black_known_positions.csv", 'w')
numcorrectw = 0
for fline in fw.readlines():
p = fline[:-1].split(",")
boards = [chessmult(left_operand[i], right_operand[i], p, p) \
for i in range(len(left_operand))]
assert checkboards(boards, justWhites=True, justBlacks=False)
# Board 1 the probable winning move is for the white King to move down down-left or down-right. In all cases this requires bRC is not Q or C and that bBR is not a Q or C (nor B or R, which might block the other white piece). For this to work we need wBB to be Q or C.
# Board 2 possibilities for other white Only C and Q (for wKK) makes sense here.
# Board 4 is won by wQK (=R) moving up 2 and left 3; requires bQB not be a R, bQQ not be a P,B or Q and bQC not be a Q or C.
# Board 6: if wP can move up one, preventing bK moving right (but bKB must not be a C or Q (which it doesn't appear to be)); wKR must then be a B to prevent bK from moving right-down.
# Board 7: is probably won if wBC is a B or Q and wK moves to the left-up or right-down. This can only work if bCC is a B or Q (both alternatives for bCR and wCC are acceptable here).
# Board 9: can be won by wBR (=C) moving right to the edge of he board. It doesn't matter if bQK is Q or C (the only options left) as neither will help.
if \
p[encodingMap.index("B")][encodingMap.index("B")] in "QC" and \
p[encodingMap.index("K")][encodingMap.index("K")] in "QC" and \
p[encodingMap.index("Q")][encodingMap.index("K")] == "R" and \
p[encodingMap.index("K")][encodingMap.index("R")] in "BQ" and \
p[encodingMap.index("B")][encodingMap.index("C")] in "BQ" and \
p[encodingMap.index("B")][encodingMap.index("R")] in "QC" and \
True :
numcorrectw += 1
gw.write(fline)
fw.close()
gw.close()
print numcorrectw
numcorrectb = 0
for fline in fb.readlines():
p = fline[:-1].split(",")
boards = [chessmult(left_operand[i], right_operand[i], p, p) \
for i in range(len(left_operand))]
assert checkboards(boards, justWhites=False, justBlacks=True)
# These rules come from a consideration of mate in 1.
# Board 1 the probable winning move is for the white King to move down down-left or down-right. In all cases this requires bRC is not Q or C and that bBR is not a Q or C (nor B or R, which might block the other white piece). For this to work we need wBB to be Q or C.
# Board 2 possibilities for other black any piece that can move diagonally to save the black king are not allow so Only P and C for (bCQ) makes sense here. (This is trumped by board 4)
# Board 4 is won by wR moving up 2 and left 3; requires bQB not be a R, bQQ not be a P,B or Q and bQC not be a Q or C.
# Board 7: is probably won if wBC is a B or Q and wK moves to the left-up or right-down. This can only work if bCC is a B or Q (both alternatives for bCR and wCC are acceptable here).
if \
not(p[encodingMap.index("B")][encodingMap.index("R")] in "QCBR") and \
not(p[encodingMap.index("R")][encodingMap.index("C")] in "QC") and \
p[encodingMap.index("C")][encodingMap.index("Q")] in "PC" and \
p[encodingMap.index("Q")][encodingMap.index("B")] != "R" and \
not(p[encodingMap.index("Q")][encodingMap.index("Q")] in "PBQ") and \
not(p[encodingMap.index("Q")][encodingMap.index("C")] in "QC") and \
p[encodingMap.index("C")][encodingMap.index("C")] in "BQ" and \
True :
gb.write(fline)
numcorrectb += 1
fb.close()
gb.close()
print numcorrectb
def filterforcrosspositions():
"""
Stage 4.
Finally find the combination of multiplication tables that result in valid boards.
"""
gw = open("correct_ones_white_known_positions.csv", 'r')
gb = open("correct_ones_black_known_positions.csv", 'r')
sw = open("solution_white.csv", 'w')
sb = open("solution_black.csv", 'w')
ps = [] # White tables
qs = [] # Black tables
for fline in gw.readlines():
ps.append( fline[:-1].split(",") )
for gline in gb.readlines():
qs.append( gline[:-1].split(",") )
for p in ps:
for q in qs:
boards = [chessmult(left_operand[i], right_operand[i], p, q) \
for i in range(len(left_operand))]
# Board 3: is probably won by white king castling with the bottom left castle; wPK needs to be either Q or B so that bC next to bK is unable to move down and block.
# Board 5: if bK were to move vertically up only wPQ would be able to take it so wPQ is probably not moved and is therefore likely to be either Q or C; similarly wRQ probably prevents bK from moving bottom-right so is either Q or B (which requires bPQ to not be a R).
# Board 8: the winning move appears to be wP near the centre takes bC to the top-right. This requires wPP to be either Q or B to prevent the bC next to it taking the wP; also wCC needs to be Q or C to prevent bK moving up or down.
if \
p[encodingMap.index("P")][encodingMap.index("K")] in "QB" and \
p[encodingMap.index("P")][encodingMap.index("Q")] in "QC" and \
p[encodingMap.index("C")][encodingMap.index("Q")] in "QC" and \
p[encodingMap.index("R")][encodingMap.index("Q")] in "QB" and \
p[encodingMap.index("P")][encodingMap.index("P")] in "QB" and \
p[encodingMap.index("C")][encodingMap.index("C")] in "QC" and \
True :
#print "--------------------"
prettyprintboard(boards, showColRows=True)
# Pretty print the multiplication tables
print "White"
print
print [r for r in encodingMap]
print
for r in range(6):
print (['_']*r)+[c for c in p[r][r:]], encodingMap[r]
print
print "Black"
print
print [r for r in encodingMap]
print
for r in range(6):
print (['_']*r)+[c for c in q[r][r:]], encodingMap[r]
print
# Save out solution.
sw.write("%s,%s,%s,%s,%s,%s\n" % tuple(["".join(i) for i in p]))
sb.write("%s,%s,%s,%s,%s,%s\n" % tuple(["".join(i) for i in q]))
gw.close()
gb.close()
sw.close()
sb.close()
######################################################################
# Printing functions that allow us to test the current configuration #
# and gain insight on what's going on #
######################################################################
def listpossiblepiecess(f1,f2):
"""
List the possible pieces for each location in the multiplication tables.
"""
# Track some possible values for each position in the multiplication table
fw = open(f1, 'r')
fb = open(f2, 'r')
possiblew = [
[dict(), dict(), dict(), dict(), dict(), dict()],
[dict(), dict(), dict(), dict(), dict(), dict()],
[dict(), dict(), dict(), dict(), dict(), dict()],
[dict(), dict(), dict(), dict(), dict(), dict()],
[dict(), dict(), dict(), dict(), dict(), dict()],
[dict(), dict(), dict(), dict(), dict(), dict()]
]
possibleb = [
[dict(), dict(), dict(), dict(), dict(), dict()],
[dict(), dict(), dict(), dict(), dict(), dict()],
[dict(), dict(), dict(), dict(), dict(), dict()],
[dict(), dict(), dict(), dict(), dict(), dict()],
[dict(), dict(), dict(), dict(), dict(), dict()],
[dict(), dict(), dict(), dict(), dict(), dict()]
]
print "White"
for fline in fw.readlines():
p = fline[:-1].split(",")
boards = [chessmult(left_operand[i], right_operand[i], p, p) \
for i in range(len(left_operand))]
assert checkboards(boards, justWhites=True, justBlacks=False)
for i in range(len(possiblew)):
for j in range(len(possiblew[0])):
posValue = p[i][j]
if not posValue in possiblew[i][j]:
possiblew[i][j][posValue] = 1
fw.close()
for i in range(len(encodingMap)):
for j in range(len(encodingMap)):
print encodingMap[i], encodingMap[j], possiblew[i][j].keys()
print
print "Black"
for fline in fb.readlines():
p = fline[:-1].split(",")
boards = [chessmult(left_operand[i], right_operand[i], p, p) \
for i in range(len(left_operand))]
assert checkboards(boards, justWhites=False, justBlacks=True)
for i in range(len(possibleb)):
for j in range(len(possibleb[0])):
posValue = p[i][j]
if not posValue in possibleb[i][j]:
possibleb[i][j][posValue] = 1
fb.close()
for i in range(len(encodingMap)):
for j in range(len(encodingMap)):
print encodingMap[i], encodingMap[j], possibleb[i][j].keys()
return (possiblew,possibleb)
def prettyprintmulttable(p):
"""Print a multiplication table in a user-friendly format."""
print list(encodingMap)
#print p
print
for i in range(len(p)):
my_out = []
for j in range(len(p)):
if i > j:
#my_out.append(" ")
my_out.append(dolookup(p, encodingMap[i], encodingMap[j]))
else:
my_out.append(dolookup(p, encodingMap[i], encodingMap[j]))
print my_out
print
def prettyprintboard(board, showColRows=False):
"""Print a multiplied out board in a user-friendly format."""
for b in board:
if showColRows:
print [chr(ord('a')+i)+"_" for i in range(8)]
print
for r in range(len(b)):
row = b[r]
if showColRows:
print row, (8-r)
else:
print row
#print
print
def testthecurrentpositions((possiblew,possibleb)):
"""
Can't recall what this does but it helps build the output shown in the results section below.
Order of columns:
PRBCKQ
Order of rows:
P
R
B
C
K
Q
"""
# Can't recall why this is partially filled in; perhaps I did thi gradually as I built up the solutions stage to stage.
whitekingpositions = [
['*', 'K', 'R', 'P', 'C', '*'],
['K', 'P', 'C', '*', 'B', '*'],
['R', 'C', 'P', 'B', 'Q', 'K'],
['P', '*', 'B', '*', 'K', 'C'],
['C', 'B', 'Q', 'K', '*', '*'],
['*', '*', 'K', 'C', '*', '*']
]
for i in range(len(possiblew)):
for j in range(len(possiblew[0])):
if len(possiblew[i][j].keys()) == 1:
whitekingpositions[i][j] = possiblew[i][j].keys()[0]
else:
whitekingpositions[i][j] = '*'
# Can't recall why this is partially filled in; perhaps I did thi gradually as I built up the solutions stage to stage.
blackkingpositions = [
['K', 'C', 'Q', 'R', 'P', 'B'],
['C', '*', 'P', 'Q', '*', 'K'],
['Q', 'P', '*', 'K', '*', 'C'],
['R', 'Q', 'K', 'B', 'C', 'P'],
['P', '*', '*', 'C', 'K', 'Q'],
['B', 'K', 'C', 'P', 'Q', 'R']
]
for i in range(len(possibleb)):
for j in range(len(possibleb[0])):
if len(possibleb[i][j].keys()) == 1:
blackkingpositions[i][j] = possibleb[i][j].keys()[0]
else:
blackkingpositions[i][j] = '*'
# Seem to recall this prints left and right operands if there is more than one alternative in the mutliplcation table otherwise the known product.
boards = [chessmult(left_operand[i], right_operand[i], \
whitekingpositions, blackkingpositions, \
justPrintFactors=True, \
guessedWhite=whitekingpositions, \
guessedBlack=blackkingpositions) \
for i in range(len(left_operand))]
print
prettyprintboard(boards)
#############################
#### Do computations ########
#############################
# Comment out lines as appropriate to run individual stages of the search rather than all at once.
# Stage 0.
determineallpermutations()
findallkingletons()
# Stage 1.
testthecurrentpositions(listpossiblepiecess("correct_ones_white_kings.csv","correct_ones_black_kings.csv"))
filterforcheckmate()
# Stage 2.
testthecurrentpositions(listpossiblepiecess("correct_ones_white_kings_not_mate.csv","correct_ones_black_kings_not_mate.csv"))
filterforvalidpawns()
# Stage 3.
testthecurrentpositions(listpossiblepiecess("correct_ones_white_pawns_valid.csv","correct_ones_black_pawns_valid.csv"))
filterforknownpositions()
# Stage 4.
testthecurrentpositions(listpossiblepiecess("correct_ones_white_known_positions.csv","correct_ones_black_known_positions.csv"))
filterforcrosspositions()
# Stage 5.
testthecurrentpositions(listpossiblepiecess("solution_white.csv","solution_black.csv"))
####################################
# RESULTS ##########################
####################################
# Including reasons for heuristics #
####################################
# Stage 1 - Make sure no king is in check.
"""
['___', '___', 'wBB', '___', 'wK_', '___', '___', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bBR']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', 'bRC', '___', '___', '___', 'bPC']
['___', '___', '___', 'bRR', '___', '___', '___', 'bPR']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 1: No way for black or white to be in check here.
['___', '___', '___', '___', '___', '___', '___', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bCQ']
['___', 'wKK', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 2: White king is not in check if bCQ != R.
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'bRC', 'bRP', '___', '___', '___', '___']
['___', '___', '___', 'bRK', '___', '___', '___', '___']
['wBK', '___', '___', '___', 'wPK', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'bKC', 'bKP']
['wBR', '___', '___', '___', 'wK_', '___', '___', 'bK_']
# Board 3: White king is not in check if bKC != R.
['bQK', 'bQB', '___', '___', '___', '___', '___', '___']
['bK_', 'bQQ', '___', '___', '___', '___', '___', '___']
['bQP', 'bQC', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', 'wQK', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['wK_', '___', '___', '___', '___', '___', '___', '___']
# Board 4: White king is not in check if bQP != Q or C.
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['wK_', '___', '___', '___', '___', '___', '___', '___']
['___', 'wPQ', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'bK_', 'bPB']
['___', '___', '___', '___', '___', '___', 'bPQ', '___']
['___', '___', 'wCR', '___', 'wRR', '___', '___', '___']
['___', '___', '___', 'wCQ', '___', 'wRQ', '___', '___']
# Board 5: Black king is not in check if wRR != B or Q.
['bK_', '___', '___', '___', '___', '___', '___', '___']
['bKB', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'wRR', '___', '___', '___', 'wK_', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'wKR', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 6: Black king is not in check if wRR != B or Q.
['___', '___', '___', '___', '___', '___', 'bCR', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bCC']
['___', '___', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', 'wBC', '___', '___', '___', '___', '___', 'wCC']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 7: we cannot have the black pieces closest to the white queen (bCR and bCC) be R
['___', '___', '___', '___', '___', '___', 'wPP', '___']
['___', '___', '___', 'bKP', '___', 'bRP', '___', '___']
['___', '___', 'bKQ', '___', 'bK_', '___', '___', '___']
['___', '___', '___', 'bKP', '___', 'bRP', 'wPC', '___']
['___', '___', 'wBP', '___', 'wCP', '___', 'wK_', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'wBC', '___', 'wCC', '___', 'wRC', '___']
# Board 8: we cannot have a black piece bRP that can move down-right; for the black king we cannot have wCP be Q or C and wPC be a R either.
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', 'wBR', '___', '___']
['___', '___', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', 'bK_']
['___', '___', '___', '___', '___', '___', 'bQK', '___']
Board 9: wBR cannot be a Q or B; bQK cannot be a R.
"""
# Stage 2 - remove illegal positions for pawns.
"""
['___', '___', 'wBB', '___', 'wK_', '___', '___', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bBR']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', 'bRC', '___', '___', '___', 'bR_']
['___', '___', '___', 'bRR', '___', '___', '___', 'bC_']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 1: wBB would not be a P since it would have been promoted.
['___', '___', '___', '___', '___', '___', '___', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bCQ']
['___', 'wKK', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 2: none.
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'bRC', 'bC_', '___', '___', '___', '___']
['___', '___', '___', 'bRK', '___', '___', '___', '___']
['wBK', '___', '___', '___', 'wPK', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'bKC', 'bKP']
['wBR', '___', '___', '___', 'wK_', '___', '___', 'bK_']
# Board 3: wBR.
['bQK', 'bQB', '___', '___', '___', '___', '___', '___']
['bK_', 'bQQ', '___', '___', '___', '___', '___', '___']
['bQP', 'bQC', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', 'wQK', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['wK_', '___', '___', '___', '___', '___', '___', '___']
# Board 4: bQK and bQB.
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['wK_', '___', '___', '___', '___', '___', '___', '___']
['___', 'wPQ', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'bK_', 'bPB']
['___', '___', '___', '___', '___', '___', 'bPQ', '___']
['___', '___', 'wCR', '___', 'wRR', '___', '___', '___']
['___', '___', '___', 'wCQ', '___', 'wRQ', '___', '___']
# Board 5: wCQ and wRQ.
['bK_', '___', '___', '___', '___', '___', '___', '___']
['bKB', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'wRR', '___', '___', '___', 'wK_', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'wKR', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 6: none.
['___', '___', '___', '___', '___', '___', 'bCR', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bCC']
['___', '___', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', 'wBC', '___', '___', '___', '___', '___', 'wCC']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 7: bCR.
['___', '___', '___', '___', '___', '___', 'wPP', '___']
['___', '___', '___', 'bKP', '___', 'bC_', '___', '___']
['___', '___', 'bKQ', '___', 'bK_', '___', '___', '___']
['___', '___', '___', 'bKP', '___', 'bC_', 'wPC', '___']
['___', '___', 'wBP', '___', 'wCP', '___', 'wK_', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'wBC', '___', 'wCC', '___', 'wRC', '___']
# Board 8: wPP, wBC, wCC, wRC.
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', 'wBR', '___', '___']
['___', '___', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', 'bK_']
['___', '___', '___', '___', '___', '___', 'bQK', '___']
# Board 9: bQK.
"""
# Stage 3 - Guess probable winning moves, taking each multiplication table separately.
"""
This table shows the current possibilities for each operand pair (obtained from listpossiblepiecess())
White
P P ['Q', 'B', 'R', 'C']
P R ['K']
P B ['Q', 'R', 'C', 'B']
P C ['P']
P K ['Q', 'R', 'C', 'B']
P Q ['Q', 'R', 'C', 'B']
R P ['K']
R R ['P']
R B ['C', 'R']
R C ['Q', 'R', 'B', 'C']
R K ['Q', 'R', 'C', 'B']
R Q ['Q', 'R', 'C', 'B']
B P ['Q', 'R', 'C', 'B']
B R ['C', 'R']
B B ['Q', 'C', 'R', 'B']
B C ['Q', 'C', 'R', 'B']
B K ['P']
B Q ['K']
C P ['P']
C R ['Q', 'R', 'B', 'C']
C B ['Q', 'C', 'R', 'B']
C C ['Q', 'C', 'R', 'B']
C K ['K']
C Q ['Q', 'B', 'R', 'C']
K P ['Q', 'R', 'C', 'B']
K R ['Q', 'R', 'C', 'B']
K B ['P']
K C ['K']
K K ['Q', 'B', 'R', 'C']
K Q ['Q', 'R', 'B', 'C']
Q P ['Q', 'R', 'C', 'B']
Q R ['Q', 'R', 'C', 'B']
Q B ['K']
Q C ['Q', 'B', 'R', 'C']
Q K ['Q', 'R', 'B', 'C']
Q Q ['P']
Black
P P ['K']
P R ['C']
P B ['Q', 'P', 'B']
P C ['R']
P K ['Q', 'P', 'B']
P Q ['P', 'B']
R P ['C']
R R ['Q', 'P', 'B', 'R']
R B ['Q', 'P', 'B']
R C ['Q', 'B']
R K ['Q', 'P', 'B', 'R']
R Q ['K']
B P ['Q', 'P', 'B']
B R ['Q', 'P', 'B']
B B ['Q', 'P', 'C', 'R', 'B']
B C ['K']
B K ['P', 'R', 'B', 'C']
B Q ['Q', 'C', 'R', 'B']
C P ['R']
C R ['Q', 'B']
C B ['K']
C C ['Q', 'P', 'C', 'B']
C K ['Q', 'P', 'C', 'B']
C Q ['Q', 'P', 'C', 'B']
K P ['Q', 'P', 'B']
K R ['Q', 'P', 'B', 'R']
K B ['P', 'R', 'B', 'C']
K C ['Q', 'P', 'C', 'B']
K K ['K']
K Q ['Q', 'C', 'B']
Q P ['P', 'B']
Q R ['K']
Q B ['Q', 'C', 'R', 'B']
Q C ['Q', 'P', 'C', 'B']
Q K ['Q', 'C', 'B']
Q Q ['Q', 'P', 'C', 'R', 'B']
['___', '___', 'wBB', '___', 'wK_', '___', '___', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bBR']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', 'bRC', '___', '___', '___', 'bR_']
['___', '___', '___', 'bRR', '___', '___', '___', 'bC_']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 1 the probable winning move is for the white King to move down down-left or down-right. In all cases this requires bRC is not Q or C and that bBR is not a Q or C (nor B or R, which might block the other white piece). For this to work we need wBB to be Q or C.
['___', '___', '___', '___', '___', '___', '___', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bCQ']
['___', 'wKK', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 2 possibilities for other white Only C and Q (for wKK) makes sense here.
# Board 2 possibilities for other black any piece that can move diagonally to save the black king are not allow so Only P and C for (bCQ) makes sense here.
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'bRC', 'bC_', '___', '___', '___', '___']
['___', '___', '___', 'bRK', '___', '___', '___', '___']
['wP_', '___', '___', '___', 'wPK', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'bKC', 'bKP']
['wBR', '___', '___', '___', 'wK_', '___', '___', 'bK_']
# Board 3: This is too complex to consider at this stage.
['bQK', 'bQB', '___', '___', '___', '___', '___', '___']
['bK_', 'bQQ', '___', '___', '___', '___', '___', '___']
['bQP', 'bQC', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', 'wQK', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['wK_', '___', '___', '___', '___', '___', '___', '___']
# Board 4: is won by wQK (=R) moving up 1 and left 2; requires bQB not be a R, bQQ not be a P,B or Q and bQC not be a Q or C.
# https://en.wikipedia.org/wiki/Knight_(chess)
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['wK_', '___', '___', '___', '___', '___', '___', '___']
['___', 'wPQ', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'bK_', 'bPB']
['___', '___', '___', '___', '___', '___', 'bPQ', '___']
['___', '___', 'wCR', '___', 'wP_', '___', '___', '___']
['___', '___', '___', 'wCQ', '___', 'wRQ', '___', '___']
# Board 5: This is too complex to consider at this stage.
['bK_', '___', '___', '___', '___', '___', '___', '___']
['bKB', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'wP_', '___', '___', '___', 'wK_', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'wKR', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Although this is a rule that involves two multiplication tables we can get away with it only applying to the white table.
# Board 6: if wP can move up one, preventing bK moving right (but bKB must not be a C or Q (which it doesn't appear to be)); wKR must then be a B to prevent bK from moving right-down.
['___', '___', '___', '___', '___', '___', 'bCR', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bCC']
['___', '___', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', 'wBC', '___', '___', '___', '___', '___', 'wCC']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 7: is probably won if wBC is a B or Q and wK moves to the left-up or right-down. This can only work if bCC is a B or Q (both alternatives for bCR and wCC are acceptable here).
['___', '___', '___', '___', '___', '___', 'wPP', '___']
['___', '___', '___', 'bKP', '___', 'bC_', '___', '___']
['___', '___', 'bKQ', '___', 'bK_', '___', '___', '___']
['___', '___', '___', 'bKP', '___', 'bC_', 'wP_', '___']
['___', '___', 'wBP', '___', 'wP_', '___', 'wK_', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'wBC', '___', 'wCC', '___', 'wRC', '___']
# Board 8: This is too complex to consider at this stage.
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', 'wBR', '___', '___']
['___', '___', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', 'bK_']
['___', '___', '___', '___', '___', '___', 'bQK', '___']
# Board 9: can be won by wBR (=C) moving right to the edge of he board. It doesn't matter if bQK is Q or C (the only options left) as neither will help.
"""
# Stage 4 - final set of constraints that take into account both multiplication tables at once. (Doing this at this stage reduces the number of combinations to consider substantially)
"""
White
P P ['Q', 'C']
P K ['Q', 'C', 'B']
P Q ['Q', 'C', 'B']
R K ['Q', 'B']
R Q ['Q', 'B']
C C ['Q', 'C']
C Q ['Q', 'C']
K P ['Q', 'C', 'B']
K R ['Q', 'B']
K K ['Q', 'C']
Q P ['Q', 'C', 'B']
Q R ['Q', 'B']
Q C ['Q', 'C']
['___', '___', '___', '___', '___', '___', '___', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bP_']
['___', 'wKK', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 2: should just drop out
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'bB_', 'bC_', '___', '___', '___', '___']
['___', '___', '___', 'bR_', '___', '___', '___', '___']
['wP_', '___', '___', '___', 'wPK', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'bC_', 'bP_']
['wC_', '___', '___', '___', 'wK_', '___', '___', 'bK_']
# These rules combine two multiplication tables at once.
# Board 3: is probably won by white king castling with the bottom left castle; wPK needs to be either Q or B so that bC next to bK is unable to move down and block.
# https://en.wikipedia.org/wiki/Castling
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['wK_', '___', '___', '___', '___', '___', '___', '___']
['___', 'wPQ', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'bK_', 'bQ_']
['___', '___', '___', '___', '___', '___', 'bB_', '___']
['___', '___', 'wR_', '___', 'wP_', '___', '___', '___']
['___', '___', '___', 'wCQ', '___', 'wRQ', '___', '___']
# These rules combine two multiplication tables at once.
# Board 5: if bK were to move vertically up only wPQ would be able to take it so wPQ is probably not moved and is therefore likely to be either Q or C; similarly wRQ probably prevents bK from moving bottom-right so is either Q or B (which requires bPQ to not be a R).
['bK_', '___', '___', '___', '___', '___', '___', '___']
['bB_', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'wP_', '___', '___', '___', 'wK_', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', 'wKR', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 6: should just drop out
['___', '___', '___', '___', '___', '___', 'bB_', 'bK_']
['___', '___', '___', '___', '___', '___', '___', 'bQ_']
['___', '___', '___', '___', '___', 'wK_', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', 'wB_', '___', '___', '___', '___', '___', 'wCC']
['___', '___', '___', '___', '___', '___', '___', '___']
# Board 7: should just drop out
['___', '___', '___', '___', '___', '___', 'wPP', '___']
['___', '___', '___', 'bP_', '___', 'bC_', '___', '___']
['___', '___', 'bQ_', '___', 'bK_', '___', '___', '___']
['___', '___', '___', 'bP_', '___', 'bC_', 'wP_', '___']
['___', '___', 'wR_', '___', 'wP_', '___', 'wK_', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', '___', '___', '___', '___', '___', '___']
['___', '___', 'wB_', '___', 'wCC', '___', 'wR_', '___']
# These rules combine two multiplication tables at once.
# Board 8: the winning move appears to be wP near the centre takes bC to the top-right. This requires wPP to be either Q or B to prevent the bC next to it taking the wP; also wCC needs to be Q or C to prevent bK moving up or down.
"""
################################################################################
################################################################################
# Completed solution ###########################################################
################################################################################
################################################################################
""""
Final multiplication tables.
White
['P', 'R', 'B', 'C', 'K', 'Q']
['Q', 'K', 'R', 'P', 'B', 'C'] P
['_', 'P', 'C', 'R', 'Q', 'B'] R
['_', '_', 'Q', 'B', 'P', 'K'] B
['_', '_', '_', 'C', 'K', 'Q'] C
['_', '_', '_', '_', 'C', 'R'] K
['_', '_', '_', '_', '_', 'P'] Q
Black
['P', 'R', 'B', 'C', 'K', 'Q']
['K', 'C', 'Q', 'R', 'P', 'B'] P
['_', 'Q', 'P', 'B', 'R', 'K'] R
['_', '_', 'R', 'K', 'B', 'C'] B
['_', '_', '_', 'Q', 'C', 'P'] C
['_', '_', '_', '_', 'K', 'Q'] K
['_', '_', '_', '_', '_', 'R'] Q
--------------------------------------------------------------------------------
Given that title of the puzzle is "Algebraic" and the required solution should be a single word or collection of letters I guess that the right answer will be either a description of the boards or the winning moves in one of the well-known algebraic notations for chess:
https://en.wikipedia.org/wiki/Algebraic_notation_(chess)
https://en.wikipedia.org/wiki/Chess_notation
https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation
https://en.wikipedia.org/wiki/Portable_Game_Notation
Some modules to consider to automate this:
https://python-chess.readthedocs.org/en/latest/pgn.html
https://pypi.python.org/pypi/python-chess
Boards given in Forsyth–Edwards Notation and winning moves given in Algebraic Notation. At this point we switch from the designators used above to the more official forms (although our solution boards continue to be displayed in original format):
K - King
Q - Queen
R - Rook/Castle
B - Bishop
N - Knight
--------------------------------------------------------------------------------
['a_', 'b_', 'c_', 'd_', 'e_', 'f_', 'g_', 'h_']
['__', '__', 'wQ', '__', 'wK', '__', '__', 'bK'] 8
['__', '__', '__', '__', '__', '__', '__', 'bP'] 7
['__', '__', '__', '__', '__', '__', '__', '__'] 6
['__', '__', '__', '__', '__', '__', '__', '__'] 5
['__', '__', '__', 'bB', '__', '__', '__', 'bR'] 4
['__', '__', '__', 'bQ', '__', '__', '__', 'bC'] 3
['__', '__', '__', '__', '__', '__', '__', '__'] 2
['__', '__', '__', '__', '__', '__', '__', '__'] 1
# Board 1 the probable winning move is for the white King to move down down-left or down-right.
2Q1K2k/7p/8/8/3b3n/3q3c/8/8 w -
Ke7# 1-0
['a_', 'b_', 'c_', 'd_', 'e_', 'f_', 'g_', 'h_']
['__', '__', '__', '__', '__', '__', '__', 'bK'] 8
['__', '__', '__', '__', '__', '__', '__', 'bP'] 7
['__', 'wC', '__', '__', '__', 'wK', '__', '__'] 6
['__', '__', '__', '__', '__', '__', '__', '__'] 5
['__', '__', '__', '__', '__', '__', '__', '__'] 4
['__', '__', '__', '__', '__', '__', '__', '__'] 3
['__', '__', '__', '__', '__', '__', '__', '__'] 2
['__', '__', '__', '__', '__', '__', '__', '__'] 1
# Board 2: wC moves up to top row.
7k/7p/1C3K2/8/8/8/8/8 w -
Cb8# 1-0
['a_', 'b_', 'c_', 'd_', 'e_', 'f_', 'g_', 'h_']
['__', '__', '__', '__', '__', '__', '__', '__'] 8
['__', '__', '__', '__', '__', '__', '__', '__'] 7
['__', '__', 'bB', 'bC', '__', '__', '__', '__'] 6
['__', '__', '__', 'bR', '__', '__', '__', '__'] 5
['wP', '__', '__', '__', 'wB', '__', '__', '__'] 4
['__', '__', '__', '__', '__', '__', '__', '__'] 3
['__', '__', '__', '__', '__', '__', 'bC', 'bP'] 2
['wC', '__', '__', '__', 'wK', '__', '__', 'bK'] 1
# Board 3: is probably won by white king castling with the bottom left castle; wPK needs to be either Q or B so that bC next to bK is unable to move down and block.
8/8/2bc4/3n4/P3B3/8/6cp/C3K2k w Q
0-0-0# 1-0
['a_', 'b_', 'c_', 'd_', 'e_', 'f_', 'g_', 'h_']
['bQ', 'bC', '__', '__', '__', '__', '__', '__'] 8
['bK', 'bR', '__', '__', '__', '__', '__', '__'] 7
['bB', 'bP', '__', '__', '__', '__', '__', '__'] 6
['__', '__', '__', '__', 'wR', '__', '__', '__'] 5
['__', '__', '__', '__', '__', '__', '__', '__'] 4
['__', '__', '__', '__', '__', '__', '__', '__'] 3
['__', '__', '__', '__', '__', '__', '__', '__'] 2
['wK', '__', '__', '__', '__', '__', '__', '__'] 1
# Board 4: is won by wQK (=R) moving up 1 and left 2; requires bQB not be a R, bQQ not be a P,B or Q and bQC not be a Q or C.
qc6/kn6/bp6/4N3/8/8/8/K7 w -
Nc6# 1-0
['a_', 'b_', 'c_', 'd_', 'e_', 'f_', 'g_', 'h_']
['__', '__', '__', '__', '__', '__', '__', '__'] 8
['__', '__', '__', '__', '__', '__', '__', '__'] 7
['wK', '__', '__', '__', '__', '__', '__', '__'] 6
['__', 'wC', '__', '__', '__', '__', '__', '__'] 5
['__', '__', '__', '__', '__', '__', 'bK', 'bQ'] 4
['__', '__', '__', '__', '__', '__', 'bB', '__'] 3
['__', '__', 'wR', '__', 'wP', '__', '__', '__'] 2
['__', '__', '__', 'wQ', '__', 'wB', '__', '__'] 1
# Board 5: if bK were to move vertically up only wPQ would be able to take it so wPQ is probably not moved and is therefore likely to be either Q or C; similarly wRQ probably prevents bK from moving bottom-right so is either Q or B (which requires bPQ to not be a R).
8/8/K7/1C6/6kq/6b1/2N1P3/3Q1B2 w -
Qd4# 1-0
['a_', 'b_', 'c_', 'd_', 'e_', 'f_', 'g_', 'h_']
['bK', '__', '__', '__', '__', '__', '__', '__'] 8
['bB', '__', '__', '__', '__', '__', '__', '__'] 7
['__', '__', 'wP', '__', '__', '__', 'wK', '__'] 6
['__', '__', '__', '__', '__', '__', '__', '__'] 5
['__', '__', '__', '__', '__', '__', '__', '__'] 4
['__', '__', '__', '__', '__', '__', '__', '__'] 3
['__', '__', '__', '__', '__', '__', 'wQ', '__'] 2
['__', '__', '__', '__', '__', '__', '__', '__'] 1
# Board 6: if wP can move up one, preventing bK moving right (but bKB must not be a C or Q (which it doesn't appear to be)); wKR must then be a B to prevent bK from moving right-down.
k7/b7/2P3K1/8/8/8/6Q1/8 w -
c7# 1-0
['a_', 'b_', 'c_', 'd_', 'e_', 'f_', 'g_', 'h_']
['__', '__', '__', '__', '__', '__', 'bB', 'bK'] 8
['__', '__', '__', '__', '__', '__', '__', 'bQ'] 7
['__', '__', '__', '__', '__', 'wK', '__', '__'] 6
['__', '__', '__', '__', '__', '__', '__', '__'] 5
['__', '__', '__', '__', '__', '__', '__', '__'] 4
['__', '__', '__', '__', '__', '__', '__', '__'] 3
['__', 'wB', '__', '__', '__', '__', '__', 'wC'] 2
['__', '__', '__', '__', '__', '__', '__', '__'] 1
# Board 7: is probably won if wBC is a B or Q and wK moves to the left-up or right-down.
6bk/7q/5K2/8/8/8/1b5C/8 w -
Kg5# 1-0
['a_', 'b_', 'c_', 'd_', 'e_', 'f_', 'g_', 'h_']
['__', '__', '__', '__', '__', '__', 'wQ', '__'] 8
['__', '__', '__', 'bP', '__', 'bC', '__', '__'] 7
['__', '__', 'bQ', '__', 'bK', '__', '__', '__'] 6
['__', '__', '__', 'bP', '__', 'bC', 'wP', '__'] 5
['__', '__', 'wR', '__', 'wP', '__', 'wK', '__'] 4
['__', '__', '__', '__', '__', '__', '__', '__'] 3
['__', '__', '__', '__', '__', '__', '__', '__'] 2
['__', '__', 'wB', '__', 'wC', '__', 'wR', '__'] 1
# Board 8: the winning move appears to be wP near the centre takes bC to the top-right. This requires wPP to be either Q or B to prevent the bC next to it taking the wP; also wCC needs to be Q or C to prevent bK moving up or down.
6Q1/3p1c2/2q1k3/3p1cP1/2N1P1K1/8/8/2B1C1R1 w -
ef5# 1-0
['a_', 'b_', 'c_', 'd_', 'e_', 'f_', 'g_', 'h_']
['__', '__', '__', '__', '__', '__', '__', '__'] 8
['__', '__', '__', '__', '__', '__', '__', '__'] 7
['__', '__', '__', '__', '__', '__', '__', '__'] 6
['__', '__', '__', '__', '__', '__', '__', '__'] 5
['__', '__', '__', '__', '__', 'wC', '__', '__'] 4
['__', '__', '__', '__', '__', 'wK', '__', '__'] 3
['__', '__', '__', '__', '__', '__', '__', 'bK'] 2
['__', '__', '__', '__', '__', '__', 'bQ', '__'] 1
# Board 9: can be won by wBR (=C) moving right to the edge of he board. It doesn't matter if bQK is Q or C (the only options left) as neither will help.
8/8/8/8/5C2/5K2/7k/6q1 w -
Ch4# 1-0
--------------------------------------------------------------------------------
1 2 3
4 5 6
7 8 9
I think this is the solution we should be submitting but I'm not 100% sure.
Ke7 Cb8 0-0-0 Nc6 Qd4 c7 Kg5 ef5 Ch4
######################
# Update 01/02/2016. #
######################
Checking my solution against the rest of the Internet I appear to have fallen at the last hurdle:
https://www.reddit.com/r/puzzles/comments/3w6ja9/gchqs_christmas_puzzler_thread_spoilers_tagged/cxvby5w
I didn't follow through with exchanging C for R in the winning moves. If I had done this I would also have spotted that the correct winning move for board 5 was e4. That now gives:
Ke7 Rb8 0-0-0 Nc6 e4 c7 Kg5 ef5 Rh4
Hence the keyword is KRONECKER.
https://en.wikipedia.org/wiki/Leopold_Kronecker
So near and yet so far.
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment