数独を自動再生するので、すぐに数独プレーヤーになれる

2022-02-21 21:34:17

プログラムオートフィルWeb数独ゲーム

数独ゲームのサイトがあります。 https://www.sudoku.name/index-cn.php

もちろん、この種の数独ゲームのサイトはたくさんあるので、とりあえずデモのためにこのサイトを例にとって説明します。

遊んだことのある人は、数独の基本的なルールをよく知っていますね。

1〜9の数字は各列に1回しか出現しない。
1～9の数字は、各列に1回のみ表示されます。
太い実線で区切られた3×3のボックスには、1～9の数字が一度だけ表示されます。

この数独ゲームのプレイを支援するプログラムを入手するにはどうしたらよいでしょうか？

アイデア

Webオートメーションテストツール（seleniumなど）でページを開くことができます
ページを解析してテーブルデータを取得する
着信ハンドラでのテーブルの自動解析
計算された数独の結果を自動的に書き込むプログラムを使用する

ステップバイステップで問題を解いてみましょう。

Selenium経由でターゲットURLにアクセスする

seleniumのインストールについては、https://blog.csdn.net/as604049322/article/details/114157526 を参照してください。

まず、以下のサイトでselenium経由でツアーを開きます。

from selenium import webdriver
browser = webdriver.Chrome()

selenium が正しくインストールされていれば、上記のコードを実行すると、Google Chrome のエクスプローラが

この時点で、数独ゲームのURLにアクセスするには、コントロールされたツアーに直接URLを入力するか、以下のコードでツアーをコントロールする必要があります。

url = "https://www.sudoku.name/index.php?ln=cn&puzzle_num=&play=1&difficulty=4&timer=&time_limit=0"
browser.get(url)

<イグ

社内PS：やはり今後はGoogle Chromeの広告削除プラグインを導入する必要がありますね

数独データ抽出

ノード解析

テーブルノードのidは

のvalue属性にノード値が存在する。

Seleniumを使ってツアーを制御するのはこの利点で、プログラムによって必要なデータをいつでも抽出できるようになります。

まず対象のテーブルタグを取得します。

from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC

wait = WebDriverWait(browser, 10)

table = wait.until(EC.element_to_be_clickable(
    (By.CSS_SELECTOR, 'table#sudoku_main_board')))

以下は、ノードの分析に基づいて必要な数独データを抽出する方法です。

board = []
for tr in table.find_elements_by_xpath(". //tr"):
    row = []
    for input_e in tr.find_elements_by_xpath(". //input[@class='i3']"):
        cell = input_e.get_attribute("value")
        row.append(cell if cell else ". ")
    board.append(row)
board

[['7', '.' , '.' , '.' , '.' , '4', '.' , '.' , '.'] ,
 ['.' , '4', '.' , '.' , '.' , '5', '9', '.' , '.'] ,
 ['8', '.' , '.' , '.' , '.' , '.' , '.' , '2', '.'] ,
 ['.' , '.' , '6', '.' , '9', '.' , '.' , '.' , '4'],
 ['.' , '1', '.' , '.' , '.' , '.' , '.' , '3', '.'] ,
 ['2', '.' , '.' , '.' , '8', '.' , '5', '.' , '.'] ,
 ['.' , '5', '.' , '.' , '.' , '.' , '.' , '.' , '1'],
 ['.' , '.' , '3', '7', '.' , '.' , '.' , '8', '.'] ,
 ['.' , '.' , '.' , '2', '.' , '.' , '.' , '.' , '6']]

def solveSudoku(board):
    def flip(i: int, j: int, digit: int):
        line[i] ^= (1 << digit)
        column[j] ^= (1 << digit)
        block[i // 3][j // 3] ^= (1 << digit)

    def dfs(pos: int):
        nonlocal valid
        if pos == len(spaces):
            valid = True
            return

        i, j = spaces[pos]
        mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
        while mask:
            digitMask = mask & (-mask)
            digit = bin(digitMask).count("0") - 1
            flip(i, j, digit)
            board[i][j] = str(digit + 1)
            dfs(pos + 1)
            flip(i, j, digit)
            mask &= (mask - 1)
            if valid:
                return

    line = [0] * 9
    column = [0] * 9
    block = [[0] * 3 for _ in range(3)]
    valid = False
    spaces = list()

    for i in range(9):
        for j in range(9):
            if board[i][j] == ". ":
                spaces.append((i, j))
            else:
                digit = int(board[i][j]) - 1
                flip(i, j, digit)

    dfs(0)

<ブロッククオート

場所を示すには、.を使用します。

数独計算機

上の数独の結果を計算するプログラムはどのようにすればいいのでしょうか？これには論理的なアルゴリズム思考が必要です。

この種の問題を解く最も基本的な考え方は、再帰的＋バックトラックのアルゴリズムを使って、可能な塗りつぶしを一つずつ調べていき、矛盾がない状況を見つけるまで妥当性を検証していくことです。再帰の間、現在の空白セルがどの数字でも埋められない場合、バックトラックが実行されます。

その上で、最適化のためにビット演算を使うことができる。従来の方法では、各数字が発生したかどうかを示すために長さ99の配列を使用していましたが、ビット演算を使用すると、1つの整数だけで各数字が発生したかどうかを示すことができます。例えば、2進数の表（011000100）は、3,7,8が発生したことを示す。

具体的には、最終的なプログラムはかなり複雑なので、コードのロジックが理解できなければ、コピー＆ペーストでOKです。

solveSudoku(board)
board

[['7', '2', '9', '3', '6', '4', '1', '5', '8'],
 ['3', '4', '1', '8', '2', '5', '9', '6', '7'],
 ['8', '6', '5', '9', '7', '1', '4', '2', '3'],
 ['5', '3', '6', '1', '9', '2', '8', '7', '4'],
 ['9', '1', '8', '5', '4', '7', '6', '3', '2'],
 ['2', '7', '4', '6', '8', '3', '5', '1', '9'],
 ['6', '5', '2', '4', '3', '8', '7', '9', '1'],
 ['4', '9', '3', '7', '1', '6', '2', '8', '5'],
 ['1', '8', '7', '2', '5', '9', '3', '4', '6']]

そして実行する。

[['. , '.' , '.' , '6', '.' , '.' , '.' , '3', '.'] ,
 ['5', '.' , '.' , '.' , '.' , '.' , '6', '.' , '.'] ,
 ['.' , '9', '.' , '.' , '.' , '5', '.' , '.' , '.'] ,
 ['.' , '.' , '4', '.' , '1', '.' , '.' , '.' , '6'],
 ['.' , '.' , '.' , '4', '.' , '3', '.' , '.' , '.'] ,
 ['8', '.' , '.' , '.' , '9', '.' , '5', '.' , '.'] ,
 ['.' , '.' , '.' , '7', '.' , '.' , '.' , '4', '.'] ,
 ['.' , '.' , '5', '.' , '.' , '.' , '.' , '.' , '8'],
 ['.' , '3', '.' , '.' , '.' , '8', '.' , '.' , '.']]

def solveSudoku(board: list) -> None:
    def flip(i: int, j: int, digit: int):
        line[i] ^= (1 << digit)
        column[j] ^= (1 << digit)
        block[i // 3][j // 3] ^= (1 << digit)

    def dfs(pos: int):
        nonlocal valid
        if pos == len(spaces):
            valid = True
            return

        i, j = spaces[pos]
        mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
        while mask:
            digitMask = mask & (-mask)
            digit = bin(digitMask).count("0") - 1
            flip(i, j, digit)
            board[i][j] = str(digit + 1)
            dfs(pos + 1)
            flip(i, j, digit)
            mask &= (mask - 1)
            if valid:
                return

    line = [0] * 9
    column = [0] * 9
    block = [[0] * 3 for _ in range(3)]
    valid = False
    spaces = list()

    for i in range(9):
        for j in range(9):
            if board[i][j] ! = ". ":
                digit = int(board[i][j]) - 1
                flip(i, j, digit)

    while True:
        modified = False
        for i in range(9):
            for j in range(9):
                if board[i][j] == ". ":
                    mask = ~(line[i] | column[j] |
                             block[i // 3][j // 3]) & 0x1ff
                    if not (mask & (mask - 1)):
                        digit = bin(mask).count("0") - 1
                        flip(i, j, digit)
                        board[i][j] = str(digit + 1)
                        modified = True
        if not modified:
            break

    for i in range(9):
        for j in range(9):
            if board[i][j] == ". ":
                spaces.append((i, j))

    dfs(0)

ご覧の通り、プログラムは数独の結果を計算しています。

ただし、データについては

solveSudoku(board)
board

上記のアルゴリズムは実際には17秒かかっており、最適化が必要である。

for i, tr in enumerate(table.find_elements_by_xpath(". //tr")):
    for j, input_e in enumerate(tr.find_elements_by_xpath(". //input[@class='i3']")):
        if input_e.get_attribute("readonly") == "true":
            continue
        input_e.click()
        input_e.clear()
        input_e.send_keys(board[i][j])

もう一度実行してください。

from selenium.webdriver.support import expected_conditions as EC
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.common.by import By
from selenium import webdriver

browser = webdriver.Chrome()
url = "https://www.sudoku.name/index.php?ln=cn&puzzle_num=&play=1&difficulty=4&timer=&time_limit=0"
browser.get(url)

wait = WebDriverWait(browser, 10)

table = wait.until(EC.element_to_be_clickable(
    (By.CSS_SELECTOR, 'table#sudoku_main_board')))
    
board = []
for tr in table.find_elements_by_xpath(". //tr"):
    row = []
    for input_e in tr.find_elements_by_xpath(". //input[@class='i3']"):
        cell = input_e.get_attribute("value")
        row.append(cell if cell else ". ")
    board.append(row)
    
def solveSudoku(board: list) -> None:
    def flip(i: int, j: int, digit: int):
        line[i] ^= (1 << digit)
        column[j] ^= (1 << digit)
        block[i // 3][j // 3] ^= (1 << digit)

    def dfs(pos: int):
        nonlocal valid
        if pos == len(spaces):
            valid = True
            return

        i, j = spaces[pos]
        mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
        while mask:
            digitMask = mask & (-mask)
            digit = bin(digitMask).count("0") - 1
            flip(i, j, digit)
            board[i][j] = str(digit + 1)
            dfs(pos + 1)
            flip(i, j, digit)
            mask &= (mask - 1)
            if valid:
                return

    line = [0] * 9
    column = [0] * 9
    block = [[0] * 3 for _ in range(3)]
    valid = False
    spaces = list()

    for i in range(9):
        for j in range(9):
            if board[i][j] ! = ". ":
                digit = int(board[i][j]) - 1
                flip(i, j, digit)

    while True:
        modified = False
        for i in range(9):
            for j in range(9):
                if board[i][j] == ". ":
                    mask = ~(line[i] | column[j] |
                             block[i // 3][j // 3]) & 0x1ff
                    if not (mask & (mask - 1)):
                        digit = bin(mask).count("0") - 1
                        flip(i, j, digit)
                        board[i][j] = str(digit + 1)
                        modified = True
        if not modified:
            break

    for i in range(9):
        for j in range(9):
            if board[i][j] == ". ":
                spaces.append((i, j))

    dfs(0)

solveSudoku(board)

for i, tr in enumerate(table.find_elements_by_xpath(". //tr")):
    for j, input_e in enumerate(tr.find_elements_by_xpath(". //input[@class='i3']")):
        if input_e.get_attribute("readonly") == "true":
            continue
        input_e.click()
        input_e.clear()
        input_e.send_keys(board[i][j])

<イグ

所要時間はわずか3.2秒と、大幅な性能向上を実現しました。

<ブロッククオート

最適化です。空白のセルに、埋めるべき固有の数値、つまり対応するb値とb-1があれば、0が得られる（つまり、bのバイナリビットが1つだけ1である）。その時点で、再帰処理まで待たずに、空白のセルに埋めるべき数を決定することができる。

あとは結果を適切な場所に配置するだけです。手で叩き込むのは大変ですからね。

結果をページに書き戻す

Seleniumの場合、手動でのボタンクリックをシミュレートし、キーボードアクションを送信することができます。

ここでは、table タグを再トラバースし、click と send_keys メソッドを使用しています。

from selenium.webdriver.support import expected_conditions as EC
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.common.by import By
from selenium import webdriver

browser = webdriver.Chrome()
url = "https://cn.sudokupuzzle.org/online2.php?nd=4"
browser.get(url)

wait = WebDriverWait(browser, 10)
table = wait.until(EC.element_to_be_clickable(
    (By.CSS_SELECTOR, 'table.sd')))
board = []
for tr in table.find_elements_by_xpath('. //tr'):
    row = []
    for input_e in tr.find_elements_by_xpath('. //td/input'):
        cell = input_e.get_attribute("value")
        row.append(cell if cell else ". ")
    board.append(row)

def solveSudoku(board: list) -> None:
    def flip(i: int, j: int, digit: int):
        line[i] ^= (1 << digit)
        column[j] ^= (1 << digit)
        block[i // 3][j // 3] ^= (1 << digit)

    def dfs(pos: int):
        nonlocal valid
        if pos == len(spaces):
            valid = True
            return

        i, j = spaces[pos]
        mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
        while mask:
            digitMask = mask & (-mask)
            digit = bin(digitMask).count("0") - 1
            flip(i, j, digit)
            board[i][j] = str(digit + 1)
            dfs(pos + 1)
            flip(i, j, digit)
            mask &= (mask - 1)
            if valid:
                return

    line = [0] * 9
    column = [0] * 9
    block = [[0] * 3 for _ in range(3)]
    valid = False
    spaces = list()

    for i in range(9):
        for j in range(9):
            if board[i][j] ! = ". ":
                digit = int(board[i][j]) - 1
                flip(i, j, digit)

    while True:
        modified = False
        for i in range(9):
            for j in range(9):
                if board[i][j] == ". ":
                    mask = ~(line[i] | column[j] |
                             block[i // 3][j // 3]) & 0x1ff
                    if not (mask & (mask - 1)):
                        digit = bin(mask).count("0") - 1
                        flip(i, j, digit)
                        board[i][j] = str(digit + 1)
                        modified = True
        if not modified:
            break

    for i in range(9):
        for j in range(9):
            if board[i][j] == ". ":
                spaces.append((i, j))

    dfs(0)


solveSudoku(board)

for i, tr in enumerate(table.find_elements_by_xpath(". //tr")):
    for j, input_e in enumerate(tr.find_elements_by_xpath(". //td/input")):
        if input_e.get_attribute("readonly") == "true":
            continue
        input_e.click()
        input_e.clear()
        input_e.send_keys(board[i][j])

実行時の効果です。

骨太の数独プレーヤーが証明すること

他の人は9分かかるところを、このプログラムでは11秒で記入できる。

フルコード

from selenium.webdriver.support import expected_conditions as EC
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.common.by import By
from selenium import webdriver

browser = webdriver.Chrome()
url = "https://www.sudoku.name/index.php?ln=cn&puzzle_num=&play=1&difficulty=4&timer=&time_limit=0"
browser.get(url)

wait = WebDriverWait(browser, 10)

table = wait.until(EC.element_to_be_clickable(
    (By.CSS_SELECTOR, 'table#sudoku_main_board')))
    
board = []
for tr in table.find_elements_by_xpath(". //tr"):
    row = []
    for input_e in tr.find_elements_by_xpath(". //input[@class='i3']"):
        cell = input_e.get_attribute("value")
        row.append(cell if cell else ". ")
    board.append(row)
    
def solveSudoku(board: list) -> None:
    def flip(i: int, j: int, digit: int):
        line[i] ^= (1 << digit)
        column[j] ^= (1 << digit)
        block[i // 3][j // 3] ^= (1 << digit)

    def dfs(pos: int):
        nonlocal valid
        if pos == len(spaces):
            valid = True
            return

        i, j = spaces[pos]
        mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
        while mask:
            digitMask = mask & (-mask)
            digit = bin(digitMask).count("0") - 1
            flip(i, j, digit)
            board[i][j] = str(digit + 1)
            dfs(pos + 1)
            flip(i, j, digit)
            mask &= (mask - 1)
            if valid:
                return

    line = [0] * 9
    column = [0] * 9
    block = [[0] * 3 for _ in range(3)]
    valid = False
    spaces = list()

    for i in range(9):
        for j in range(9):
            if board[i][j] ! = ". ":
                digit = int(board[i][j]) - 1
                flip(i, j, digit)

    while True:
        modified = False
        for i in range(9):
            for j in range(9):
                if board[i][j] == ". ":
                    mask = ~(line[i] | column[j] |
                             block[i // 3][j // 3]) & 0x1ff
                    if not (mask & (mask - 1)):
                        digit = bin(mask).count("0") - 1
                        flip(i, j, digit)
                        board[i][j] = str(digit + 1)
                        modified = True
        if not modified:
            break

    for i in range(9):
        for j in range(9):
            if board[i][j] == ". ":
                spaces.append((i, j))

    dfs(0)

solveSudoku(board)

for i, tr in enumerate(table.find_elements_by_xpath(". //tr")):
    for j, input_e in enumerate(tr.find_elements_by_xpath(". //input[@class='i3']")):
        if input_e.get_attribute("readonly") == "true":
            continue
        input_e.click()
        input_e.clear()
        input_e.send_keys(board[i][j])

数独サイト2

https://cn.sudokupuzzle.org/ にも数独のサイトがあります。

実際の数独ゲームはフレームワークの中にあるので、中を見るだけでいいのです。https://cn.sudokupuzzle.org/online2.php?nd=4

上記のサイトが一通りできたので、このサイトのnode要素は比較的シンプルになり、同じ考えで、以下のようなコードを書きます。

from selenium.webdriver.support import expected_conditions as EC
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.common.by import By
from selenium import webdriver

browser = webdriver.Chrome()
url = "https://cn.sudokupuzzle.org/online2.php?nd=4"
browser.get(url)

wait = WebDriverWait(browser, 10)
table = wait.until(EC.element_to_be_clickable(
    (By.CSS_SELECTOR, 'table.sd')))
board = []
for tr in table.find_elements_by_xpath('. //tr'):
    row = []
    for input_e in tr.find_elements_by_xpath('. //td/input'):
        cell = input_e.get_attribute("value")
        row.append(cell if cell else ". ")
    board.append(row)

def solveSudoku(board: list) -> None:
    def flip(i: int, j: int, digit: int):
        line[i] ^= (1 << digit)
        column[j] ^= (1 << digit)
        block[i // 3][j // 3] ^= (1 << digit)

    def dfs(pos: int):
        nonlocal valid
        if pos == len(spaces):
            valid = True
            return

        i, j = spaces[pos]
        mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
        while mask:
            digitMask = mask & (-mask)
            digit = bin(digitMask).count("0") - 1
            flip(i, j, digit)
            board[i][j] = str(digit + 1)
            dfs(pos + 1)
            flip(i, j, digit)
            mask &= (mask - 1)
            if valid:
                return

    line = [0] * 9
    column = [0] * 9
    block = [[0] * 3 for _ in range(3)]
    valid = False
    spaces = list()

    for i in range(9):
        for j in range(9):
            if board[i][j] ! = ". ":
                digit = int(board[i][j]) - 1
                flip(i, j, digit)

    while True:
        modified = False
        for i in range(9):
            for j in range(9):
                if board[i][j] == ". ":
                    mask = ~(line[i] | column[j] |
                             block[i // 3][j // 3]) & 0x1ff
                    if not (mask & (mask - 1)):
                        digit = bin(mask).count("0") - 1
                        flip(i, j, digit)
                        board[i][j] = str(digit + 1)
                        modified = True
        if not modified:
            break

    for i in range(9):
        for j in range(9):
            if board[i][j] == ". ":
                spaces.append((i, j))

    dfs(0)


solveSudoku(board)

for i, tr in enumerate(table.find_elements_by_xpath(". //tr")):
    for j, input_e in enumerate(tr.find_elements_by_xpath(". //td/input")):
        if input_e.get_attribute("readonly") == "true":
            continue
        input_e.click()
        input_e.clear()
        input_e.send_keys(board[i][j])

も遊んでみてください。