LoginSignup
2

posted at

updated at

数独の問題を Python で作成してみました - 見直要編

概要

正月休みに、5歳の孫がやっていた「数独」にハマってしまい、 9x9 の数独の問題作成をPythonで、、、、、っということで、試しにブランクなし(答えとなる)の表を作ってみました。

  • 作成にあたって :

    • Dataframe を利用してよりシンプル(同じロジック)に、、、
    • 表の完成までにどれだけ時間がかかっても、今回は良しとする
  • 作成方法 :

    • まずは、1列目を作成
    • 2列目以降は、列を追加するたびに、数値の行重複がないかをチェックする
      • 行重複を確認するために、配列転換(行列の入替)を行った後、列での非重複数を確認
    • 2,5,8列目に 2x3 の ブロック内での重複チェックを実施
      • ブロック重複を確認するために、ブロック内の数値リストの数と、その数値リストから重複排除した数を比較確認
    • 3,6,9列目に 3x3 の ブロック内での重複チェックを実施
      • ブロック重複を確認するために、ブロック内の数値リストの数と、その数値リストから重複排除した数を比較確認

実行環境

macOS Ventura 13.0
python 3.8.12

マシンスペック

  • プロセッサ : 2.3 GHz 8コア Intel Core i9
  • メモリ : 32GB 2667MHz DDR4

実行プログラム

test03.py
import pandas as pd
import random
import time


# i列目の作成
def func_dice(i, num):
    # 1〜9をランダムに並び替えたリストを作成
    dice = list(range(1, num+1))
    random.shuffle(dice)

    # 列名タグをつけてDataframe化
    dice_df = pd.DataFrame({i : dice})
    return dice_df


# 各行の各列で数値が重複していないかのチェック
def check_unique(i, num, sudoku_df_t):
    # 各列毎の非重複数のカウントとそのサマリ
    cnt_df = sudoku_df_t.nunique()
    # print(cnt_df, "\n")
    cnt_sum = cnt_df.sum()

    # そのサマリ数をチェックする
    # print("i, num, cnt_sum : ", i, num, cnt_sum)
    if cnt_sum != (i+1)*num:
        return False
    else:
        return True


# 2x3 のブロックで数値が重複していないかのチェック
def check_2x3(i, sudoku_df_t):
    for j in range(3):
        # 2x3マスの値を二次元リスト形式で取得
        c = j*3
        rows_list = sudoku_df_t.iloc[[i-1],[c,c+1,c+2]].values.tolist() + \
                            sudoku_df_t.iloc[[i],[c,c+1,c+2]].values.tolist()
        # 二次元リストの平坦化
        row_list = sum(rows_list, [])

        # 取得した数値リストの数と、その数値リストから重複排除した数を比較する
        if len(row_list) != len(set(row_list)) :
            return False
    return True


# 3x3 のブロックで数値が重複していないかのチェック
def check_3x3(i, sudoku_df_t):
    for j in range(3):
        # 3x3マスの値を二次元リスト形式で取得
        c = j*3
        rows_list = sudoku_df_t.iloc[[i-2],[c,c+1,c+2]].values.tolist() + \
                            sudoku_df_t.iloc[[i-1],[c,c+1,c+2]].values.tolist() + \
                            sudoku_df_t.iloc[[i],[c,c+1,c+2]].values.tolist()
        # 二次元リストの平坦化
        row_list = sum(rows_list, [])

        # 取得した数値リストの数と、その数値リストから重複排除した数を比較する
        if len(row_list) != len(set(row_list)) :
            return False
    return True


# 数独配列の作成
def create_sudoku(num):
    start = time.time()

    # 9x9 数独問題をつくる
    for i in range(num):

        print("\n**************** ", i+1, " 列目 *********************\n")

        # 1列目の作成
        if i == 0:
            # 列の数列の作成
            sudoku_df = func_dice(i, num)
            continue

        # 2列目以降の作成処理
        res = False
        while res == False:
            # 列を追加していく
            dice_df = func_dice(i, num)
            sudoku_df = pd.concat([sudoku_df, dice_df], axis=1)

            # 各行の各列で数値が重複していないかのチェック(配列の配置転換(行列の入替))
            res = check_unique(i, num, sudoku_df.T)
            
            # 重複していたなかったとき
            if res == True :
                # 2x3ブロックでの重複チェック(配列の配置転換(行列の入替))
                if i%3 == 1:
                    res = check_2x3(i, sudoku_df.T)

                # 3x3ブロックでの重複チェック(配列の配置転換(行列の入替))
                elif i%3 == 2:
                    res = check_3x3(i, sudoku_df.T)

                # それ以外はブロックの重複チェックはやらない
                else :
                    print("3x3 のトップ列のため、ブロックチェックなし\n")
            
            # 重複していたとき
            if res == False :
                # 直前に作成した列を削除
                sudoku_df.drop(columns=[i], inplace=True)

        making_time = time.time() - start
        print(sudoku_df)
        print("作成時間:{0}".format(making_time) + " [sec]\n")


# メイン
if __name__ == '__main__':
    # 9x9 の数独問題を作成する
    num = 9
    create_sudoku(num)

プログラムの実行

2列目以降では、各々の列作成完了時に経過時間を表示しています。
以下の実行例では、完了(完成)までに 10分程かかっていますが、5分以下の場合も15分以上かかる場合もありました。

結果の一番左の列はDataframeのインデックスで、一番最初の行はDataframeのタグとなります。

$ python test03.py

****************  1  列目 *********************


****************  2  列目 *********************

   0  1
0  6  2
1  5  7
2  4  8
3  1  5
4  9  3
5  7  4
6  2  1
7  3  9
8  8  6
作成時間:0.17218589782714844 [sec]


****************  3  列目 *********************

   0  1  2
0  6  2  9
1  5  7  1
2  4  8  3
3  1  5  2
4  9  3  8
5  7  4  6
6  2  1  4
7  3  9  7
8  8  6  5
作成時間:6.673443794250488 [sec]


****************  4  列目 *********************

3x3 のトップ列のため、ブロックチェックなし

   0  1  2  3
0  6  2  9  7
1  5  7  1  2
2  4  8  3  6
3  1  5  2  8
4  9  3  8  4
5  7  4  6  5
6  2  1  4  3
7  3  9  7  1
8  8  6  5  9
作成時間:6.731637954711914 [sec]


****************  5  列目 *********************

   0  1  2  3  4
0  6  2  9  7  8
1  5  7  1  2  4
2  4  8  3  6  9
3  1  5  2  8  6
4  9  3  8  4  1
5  7  4  6  5  3
6  2  1  4  3  7
7  3  9  7  1  5
8  8  6  5  9  2
作成時間:9.96546196937561 [sec]


****************  6  列目 *********************

   0  1  2  3  4  5
0  6  2  9  7  8  5
1  5  7  1  2  4  3
2  4  8  3  6  9  1
3  1  5  2  8  6  7
4  9  3  8  4  1  2
5  7  4  6  5  3  9
6  2  1  4  3  7  6
7  3  9  7  1  5  8
8  8  6  5  9  2  4
作成時間:18.998865842819214 [sec]


****************  7  列目 *********************

3x3 のトップ列のため、ブロックチェックなし

   0  1  2  3  4  5  6
0  6  2  9  7  8  5  1
1  5  7  1  2  4  3  9
2  4  8  3  6  9  1  7
3  1  5  2  8  6  7  4
4  9  3  8  4  1  2  6
5  7  4  6  5  3  9  8
6  2  1  4  3  7  6  5
7  3  9  7  1  5  8  2
8  8  6  5  9  2  4  3
作成時間:25.805356979370117 [sec]


****************  8  列目 *********************

   0  1  2  3  4  5  6  7
0  6  2  9  7  8  5  1  3
1  5  7  1  2  4  3  9  6
2  4  8  3  6  9  1  7  5
3  1  5  2  8  6  7  4  9
4  9  3  8  4  1  2  6  7
5  7  4  6  5  3  9  8  2
6  2  1  4  3  7  6  5  8
7  3  9  7  1  5  8  2  4
8  8  6  5  9  2  4  3  1
作成時間:213.39887595176697 [sec]


****************  9  列目 *********************

   0  1  2  3  4  5  6  7  8
0  6  2  9  7  8  5  1  3  4
1  5  7  1  2  4  3  9  6  8
2  4  8  3  6  9  1  7  5  2
3  1  5  2  8  6  7  4  9  3
4  9  3  8  4  1  2  6  7  5
5  7  4  6  5  3  9  8  2  1
6  2  1  4  3  7  6  5  8  9
7  3  9  7  1  5  8  2  4  6
8  8  6  5  9  2  4  3  1  7
作成時間:627.2772240638733 [sec]

まとめ

やはり、作成完了まで数分かかるというのは、いかがなものかと、、、8列目と9列目作成時のロジックを別途追加する(シンプルにならないですが)か、他の方法を考えるか、、、、、ですね。今回、孫から色々学ばせてもらいました。

参考記事

以下の記事を参考にさせていただきました。感謝申し上げます。
pandas DataFrameの行・列を抽出|loc, iloc, at, iatわかりやすく解説!
Pythonでリスト(配列)に重複した要素があるか判定

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
2