QueensをPythonで解く

Queens

皆さんはQueensというゲームをご存知でしょうか。

Queensはビジュアル・ロジックゲーム。いわゆるパズルです。グリッド上の各行・各列・各色の領域にそれぞれクイーン（👑）を１つずつ置き、いかなる向きでもクイーン同士が触れ合わないよう（斜めも含め）埋めていきます。新しいパネルはLinkedIn上で毎日公開され、通知設定で配信を受け取るよう登録できますが、一度挑戦すると毎日毎日お知らせが来ます。最初のうちは楽しいですが、最近はなんだかやらされ気味になってきました。

(Queensのゲーム画面。 https://mojodojo.io/blog/you-can-now-play-games-on-linkedin/ より転載)

気力があるうちはいいのですが、私の場合すでに160日を経過して飽きてきました。ただ、継続は力なりと言う言葉もあります。何かしらの力になってくれなければ続けてきた意味がありません。
じゃあしょうがねえやということで、この際プログラムのネタにでもなってもらおうかと思い筆をとりました。

構想

じゃあ、プログラムでこれを解こうとして、実際どうやって解くのかと言うと、速いCPUを利用した全探索がいいんじゃないの？的なことは誰だって考えます。私もそう考えました。

課題は LinkedIn のゲームページに掲載されるのをマウスでポチポチ解くタイプなので、まずそのページの中から盤（日によって5x5~10x10くらいまで変わるが必ず正方形）をスクリーンショットで切り出します。この時、どこかに吐き出していたら時間がかかりますよね？
一応タイムアタック要素もあるゲームなので、まずはクリップボードにこの画像を収めます。
そのうえでPythonスクリプトを実行し、クリップボードの中を解析してやればより手早く回答にたどり着けます。

あとは回答をどう表示するかです。出てきた回答をLinkedInのページにポチポチと入力するわけですから、できればオリジナルに沿った画像がどこかに出てきて欲しい、ということで PILを使って出力するのが良かろうということになりました。

準備

必要なライブラリは opencv, numpy, KMeans, PILです。

$ pip3 install opencv-python numpy sklearn PIL

みたいな感じでインストールしていけば良いのでしょうか。とりあえず「ないよ」とエラーが出たらそれをインストールする方向でお願いします。

KMeans 何に使うんじゃい問題

これは、画面をキャプチャした時にクリップボードに載ったボード画像が必ずしもきちんとした色だとは限らないケースを想定しています。エッジ部分が中間色にボケていたり、というやつですね。
そんないろんな色をとりあえず灰緑色、群青色、小豆色……なんかに分けていくために必要なんです。こんなののために機械学習を使うのかと言われるとアレですが、役に立つなら何使ってもいいですよね。

本体

次に、プログラム本体です。エディタでもメモ帳でも開いて次のファイルをコピペして、保存して下さい。

queens.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import cv2
import numpy as np
from sklearn.cluster import KMeans
from PIL import ImageGrab, Image

def cluster_lines(lines, threshold=10):
    """
    ライン座標のリストを、近い値同士でクラスタリングして平均値を返す。
    threshold: クラスタリングする際の閾値（画素数）
    """
    if not lines:
        return []
    lines.sort()
    clusters = []
    current_cluster = [lines[0]]
    for line in lines[1:]:
        if abs(line - current_cluster[-1]) < threshold:
            current_cluster.append(line)
        else:
            clusters.append(int(np.mean(current_cluster)))
            current_cluster = [line]
    clusters.append(int(np.mean(current_cluster)))
    return clusters

def main():
    # ステップ1: クリップボードから画像を取得する
    im = ImageGrab.grabclipboard()
    # Windows では、画像ファイルパスのリストが返る場合があるので対処する
    if isinstance(im, list):
        if len(im) > 0:
            try:
                im = Image.open(im[0])
            except Exception as e:
                print("画像ファイルを開けませんでした:", e)
                return

    if not isinstance(im, Image.Image):
        print('クリップボードに画像がありません。')
        return

    # PIL画像を OpenCV 形式に変換（RGB→BGR）
    img = cv2.cvtColor(np.array(im), cv2.COLOR_RGB2BGR)
    original_img = img.copy()

    # 大きな正方形領域を検出するためにグレースケール化＆二値化
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    _, thresh = cv2.threshold(gray, 127, 255, cv2.THRESH_BINARY_INV)

    contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
    if not contours:
        print('画像内に輪郭が見つかりませんでした。')
        return

    # 一番面積の大きい輪郭を大きな正方形と仮定
    largest_contour = max(contours, key=cv2.contourArea)
    x, y, w, h = cv2.boundingRect(largest_contour)
    square_img = img[y:y+h, x:x+w]

    # 検出対象の画像領域を更新
    img = square_img
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    _, thresh = cv2.threshold(gray, 127, 255, cv2.THRESH_BINARY_INV)

    # ステップ2: グリッド線を検出してセル数 n を確定する
    horizontal_kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (25, 1))
    vertical_kernel   = cv2.getStructuringElement(cv2.MORPH_RECT, (1, 25))

    detect_horizontal = cv2.morphologyEx(thresh, cv2.MORPH_OPEN, horizontal_kernel, iterations=2)
    detect_vertical   = cv2.morphologyEx(thresh, cv2.MORPH_OPEN, vertical_kernel, iterations=2)

    # 水平線検出
    contours_h, _ = cv2.findContours(detect_horizontal, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
    horizontal_candidates = [cv2.boundingRect(c)[1] for c in contours_h]
    horizontal_lines = cluster_lines(horizontal_candidates, threshold=10)
    
    # 垂直線検出
    contours_v, _ = cv2.findContours(detect_vertical, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
    vertical_candidates = [cv2.boundingRect(c)[0] for c in contours_v]
    vertical_lines = cluster_lines(vertical_candidates, threshold=10)

    # 横方向のライン数が1個多いので、グリッドのセル数 n は (ライン数 - 1)
    n = len(horizontal_lines) - 1
    print("検出されたグリッドサイズ n:", n)
    if n <= 0:
        print("グリッドサイズを検出できませんでした。")
        return

    cell_height = (horizontal_lines[-1] - horizontal_lines[0]) // n
    cell_width  = (vertical_lines[-1] - vertical_lines[0]) // n

    # ステップ3: 各セル内の色を抽出し、平均色を取得
    avg_colors = []
    for i in range(n):
        for j in range(n):
            y1 = horizontal_lines[0] + i * cell_height
            y2 = y1 + cell_height
            x1 = vertical_lines[0] + j * cell_width
            x2 = x1 + cell_width
            cell = img[y1:y2, x1:x2]
            # 黒いグリッド線の部分を除くマスクを作成
            mask = cv2.inRange(cell, np.array([0, 0, 0]), np.array([10, 10, 10]))
            mask_inv = cv2.bitwise_not(mask)
            cell_colors = cell[mask_inv == 255]
            if cell_colors.size == 0:
                avg_color = np.array([0, 0, 0])
            else:
                avg_color = np.mean(cell_colors.reshape(-1, 3), axis=0)
            avg_colors.append(avg_color)

    avg_colors_array = np.array(avg_colors)  # shape: (n^2, 3)

    # ステップ4: K-means によりセル内の色を n クラスに分類
    kmeans = KMeans(n_clusters=n, random_state=42)
    kmeans.fit(avg_colors_array)
    labels = kmeans.labels_
    cell_indices = labels.reshape(n, n)
    print("クラスタリングによって検出された色の数:", n)

    # ステップ5: 各色ごとに条件を満たす位置をバックトラッキングで決定
    domains = {}
    for color_index in range(n):
        positions = []
        for i in range(n):
            for j in range(n):
                if cell_indices[i, j] == color_index:
                    positions.append((i, j))
        domains[color_index] = positions

    solution = {}

    def is_safe(pos, assignments):
        for other_pos in assignments.values():
            # 同じ行または列にある場合は配置不可
            if pos[0] == other_pos[0] or pos[1] == other_pos[1]:
                return False
            # 隣接（斜め含む）している場合も配置不可
            if abs(pos[0] - other_pos[0]) <= 1 and abs(pos[1] - other_pos[1]) <= 1:
                return False
        return True

    def backtrack(color_index):
        if color_index == n:
            return True
        for pos in domains[color_index]:
            if is_safe(pos, solution):
                solution[color_index] = pos
                if backtrack(color_index + 1):
                    return True
                del solution[color_index]
        return False

    if backtrack(0):
        print("解が見つかりました:", solution)
    else:
        print("解が見つかりませんでした。")
        return

    # 検出された解に対して❌を描画
    for color_index, pos in solution.items():
        i, j = pos
        y1 = horizontal_lines[0] + i * cell_height
        y2 = y1 + cell_height
        x1 = vertical_lines[0] + j * cell_width
        x2 = x1 + cell_width
        center_x = (x1 + x2) // 2 + x
        center_y = (y1 + y2) // 2 + y
        offset = min(cell_width, cell_height) // 4
        cv2.line(original_img, (center_x - offset, center_y - offset),
                 (center_x + offset, center_y + offset), (0, 0, 255), 2)
        cv2.line(original_img, (center_x - offset, center_y + offset),
                 (center_x + offset, center_y - offset), (0, 0, 255), 2)

    cv2.imshow('Result', original_img)
    cv2.waitKey(0)
    cv2.destroyAllWindows()

if __name__ == '__main__':
    main()

実行

クリップボードに盤があるという条件下で、queens.py を実行すれば回答の盤が画面に現われます。

$ chmod +x queens.py
$ ./queens.py

または

$ python3 queens.py

で回答が出ます。
私の場合、画面キャプチャであたふたしなければだいたい25秒~35秒くらいで回答が完了します。

で、「あなたはCEOの99%より賢い！」と言われるわけですが、CPUにやらせてるんですから感動もありません。自分は何をしてるんだろうという虚無感に襲われます。力にならないのに継続しても仕方ないと分かれば大人です。

(2025/05/26)