[WIP] Solver for https://ardoedo.it/kempelen/

solver.py

#!/usr/bin/env python3

import itertools
import time


UNIVERSE = 0xffffffffffffffff
H_LINE = 0x0101010101010101
A_LINE = 0x0101010101010101 << 7


def pprint(board: int) -> None:
    mask = 0xff00000000000000
    for i in range(7, -1, -1):
        print(' '.join(f'{(board & mask) >> (i * 8):08b}'))
        mask >>= 8

def precompute_queen_moves() -> list[int]:
    moves_for_square = []
    for pos in range(64):
        pos = (128 >> (pos % 8)) << ((pos // 8) * 8)
        moves = valid_queen_moves(pos, board=0)
        moves_for_square.append(moves)

    return moves_for_square


def precompute_bishop_moves() -> list[int]:
    moves_for_square = []
    for pos in range(64):
        pos = (128 >> (pos % 8)) << ((pos // 8) * 8)
        moves = valid_bishop_moves(pos, board=0)
        moves_for_square.append(moves)
    return moves_for_square


def valid_queen_moves(pos, board) -> int:
    moves = pos

    sq = pos
    for _ in range(7):
        # shift right
        sq = (sq >> 1) & ~A_LINE
        if sq == 0 or sq & board: break
        moves |= sq

    sq = pos
    for _ in range(7):
        # shift left
        sq = ((sq << 1) & ~H_LINE)
        if sq == 0 or sq & board: break
        moves |= sq

    sq = pos
    for _ in range(7):
        # shift up
        sq = (sq << 8)
        if  sq == 0 or sq & board: break
        moves |= sq

    sq = pos
    for _ in range(7):
        # shift down
        sq = (sq >> 8)
        if  sq == 0 or sq & board: break
        moves |= sq

    sq = pos
    for _ in range(7):
        # shift right up
        sq = (((sq>>1) << 8) & ~A_LINE)
        if  sq == 0 or sq & board: break
        moves |= sq

    sq = pos
    for _ in range(7):
        # shift left up
        sq = (((sq<<1) << 8) & ~H_LINE)
        if  sq == 0 or sq & board: break
        moves |= sq

    sq = pos
    for _ in range(7):
        # shift right down
        sq = (((sq>>1) >> 8) & ~A_LINE)
        if  sq == 0 or sq & board: break
        moves |= sq

    sq = pos
    for _ in range(7):
        # shift left down
        sq = (((sq<<1) >> 8) & ~H_LINE)
        if  sq == 0 or sq & board: break
        moves |= sq

    return moves


def valid_bishop_moves(pos, board) -> int:
    moves = pos
    sq = pos
    for _ in range(7):
        # shift right up
        sq = (((sq>>1) << 8) & ~A_LINE)
        if  sq == 0 or sq & board: break
        moves |= sq

    sq = pos
    for _ in range(7):
        # shift left up
        sq = (((sq<<1) << 8) & ~H_LINE)
        if  sq == 0 or sq & board: break
        moves |= sq

    sq = pos
    for _ in range(7):
        # shift right down
        sq = (((sq>>1) >> 8) & ~A_LINE)
        if  sq == 0 or sq & board: break
        moves |= sq

    sq = pos
    for _ in range(7):
        # shift left down
        sq = (((sq<<1) >> 8) & ~H_LINE)
        if  sq == 0 or sq & board: break
        moves |= sq

    return moves

if __name__ == '__main__':
    start = time.monotonic()
    queen_moves = precompute_queen_moves()
    bishop_moves = precompute_bishop_moves()
    num_found_solutions = 0

    for queens in itertools.combinations(range(64), r=4):
        for bishop in range(64):
            attacked = queen_moves[queens[0]] | queen_moves[queens[1]] |  queen_moves[queens[2]] | queen_moves[queens[3]] | bishop_moves[bishop]

            if (attacked & UNIVERSE) == UNIVERSE:
                # This is a potential solution. Verify if it is actually valid
                board = (128 >> (queens[0] % 8)) << ((queens[0] // 8) * 8)
                board |= (128 >> (queens[1] % 8)) << ((queens[1] // 8) * 8)
                board |= (128 >> (queens[2] % 8)) << ((queens[2] // 8) * 8)
                board |= (128 >> (queens[3] % 8)) << ((queens[3] // 8) * 8)
                board |= (128 >> (bishop % 8)) << ((bishop // 8) * 8)

                attacked = valid_queen_moves((128 >> (queens[0] % 8)) << ((queens[0] // 8) * 8), board)
                attacked |= valid_queen_moves((128 >> (queens[1] % 8)) << ((queens[1] // 8) * 8), board)
                attacked |= valid_queen_moves((128 >> (queens[2] % 8)) << ((queens[2] // 8) * 8), board)
                attacked |= valid_queen_moves((128 >> (queens[3] % 8)) << ((queens[3] // 8) * 8), board)
                attacked |= valid_bishop_moves((128 >> (bishop % 8)) << ((bishop // 8) * 8), board)

                if (attacked & UNIVERSE) == UNIVERSE:
                    num_found_solutions += 1
                    print(f'Found {num_found_solutions} solution(s) after {time.monotonic() - start:.2f}s')
    print(num_found_solutions)