概要
本記事は、数独という脳トレ・パズルのようなものを問題として作成したり、実際に解を導き出すことは可能なのかということを記事にしてみたというものになります
作成だけで1記事になるか、作成・解の導きまで通して1記事になるかは不明ですが、まずは作成できるところまで記事にできればと思います
本題
そもそも数独とは？
こんな感じのルールがある、パズルです
- 各行（row）に1〜9が1回ずつ
- 各列（column）に1〜9が1回ずつ
- 各3x3のブロックに1〜9が1回ずつ
簡単な例で行くと3x3の1ブロックだけでも説明が可能です
| 1 | 4 | 7 |
| 2 | 5 | 8 |
| 3 | 6 | 9 |
上記が3x3の1ブロックです
これが↓なった時に、「空いているところに入る数字はなんでしょう？」というのが数独です(ちなみにこれは5です)
| 1 | 4 | 7 |
| 2 | 8 | |
| 3 | 6 | 9 |
さらに↓なった時にどうなるでしょうという感じですが、3x3の1ブロックしかない場合は決め切ることができないので2つパターンができると思います
| 1 | 4 | 7 |
| 2 | 8 | |
| 6 | 9 |
これかこれですね
| 1 | 4 | 7 |
| 2 | 3 | 8 |
| 5 | 6 | 9 |
| 1 | 4 | 7 |
| 2 | 5 | 8 |
| 3 | 6 | 9 |
3x3の1ブロックだと決め切ることが難しいですが、3x3が9ブロック繋がると世界が変わります
1つの3x3ブロックでも数字が被ることはなく、またルールに則って解いていくと絶対に縦横で数字が被ることはないという綺麗なことになります
問題は作れるのか
よくアプリや本などで数独の問題がありますが、それって自分の手でも作ることは可能なのでしょうか？
ふと思ったのでやってみたいと思います
今回、多次元配列を扱うのでpythonのnumpyを使ってみたいと思います
なのでnumpyのインストールが必要ですね
pip install numpy
そしてコード内での使い方はimport文やメソッドなどでいろいろできます
import numpy as np
n_1 = np.array([1, 2, 3])
n_2 = np.array([[1, 2, 3], [4, 5, 6]])
n_3 = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
実際のプリントした結果が以下になります
[1 2 3]
[[1 2 3]
[4 5 6]]
[[1 2 3]
[4 5 6]
[7 8 9]]
今回は数独で扱う9x9を作ります
ここで初期位置を0で埋めること＝何も数字が入っていないことと定義しておきます
単純に0埋めで作る場合は次の方法も取れるみたいです
import numpy as np
n_9 = np.zeros((9, 9), dtype=int)
そしてここから0であるところに数字をランダムで埋めていくように処理していきます
9x9なので2重for文でいけそうです
for i in range(9):
for j in range(9):
if n_3[i][j] == 0:
return (i, j)
return None
次に0である位置が見つかった場合、そこにランダムな数字を入れていく処理を考えます
rangeだと順番な数字になってしまいますが、randomモジュールのsampleを使うと重複せずに値を取ってくれるようです
そして選択された数字がそのマスに入れて良いかを判定するis_valid関数を呼び出しています
その後、全てのマスが埋まるまで以下の処理が繰り返されます
- is_validを通らなければ次の数字を検索する
- is_validを通れば対象の数字を入れる→次のマスの数字を見つけるために再起的にこの関数を呼び出す
def solve_sudoku(board):
empty_index = find_empty(board)
if not empty_index:
return True
row, col = empty_index
for num in random.sample(range(1, 10), 9):
if is_valid(board, row, col, num):
board[row][col] = num
if solve_sudoku(board):
return True
board[row][col] = 0
また処理内で使用しているis_valid関数については以下になります
boardはndarryなので行・列を取得するのは簡単ですね
列の取得時だけ、感覚的には縦なのですがリストで返却されるので注意点かと思います
周囲の3x3マスの判定がどうなっているかのチェックですが、少し工夫が必要でした(9x9なので3で割る掛けるを使うことでできました)
def is_valid(board, row, col, num):
if num in board[row]:
return False
if num in board[:, col]:
return False
start_row, start_col = (row // 3) * 3, (col // 3) * 3
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == num:
return False
return True
ということで全ての処理を合わせると以下のような感じになります
import numpy as np
import random
def is_valid(board, row, col, num):
if num in board[row]:
return False
if num in board[:, col]:
return False
start_row, start_col = (row // 3) * 3, (col // 3) * 3
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == num:
return False
return True
def solve_sudoku(board):
empty_index = find_empty(board)
if not empty_index:
return True
row, col = empty_index
for num in random.sample(range(1, 10), 9):
if is_valid(board, row, col, num):
board[row][col] = num
if solve_sudoku(board):
return True
board[row][col] = 0
return False
def find_empty(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return (i, j)
return None
def generate_full_sudoku():
n_9 = np.zeros((9, 9), dtype=int)
solve_sudoku(n_9)
return n_9
full_sudoku = generate_full_sudoku()
print(full_sudoku)
おわりに
今回はここでおわりにしたいと思います
問題が作る時はここからランダムでどこかの数字を0にすると勝手に問題ができていくと思われます
(答えが複数になる場合もあるので、解が1つになるように工夫する必要もありそうですが)
問題を作るためにまずは全てのマスをランダムに埋める処理を作る
is_valid関数を作るといったことをしたので図らずとも数独を解くプログラムを作れていたとこの記事のまとめを書いていて気づきました
もし数独の問題作ってやりたい方がいましたら、使ってみてください