2020年11月18日水曜日

数独問題の作成方法4x4 から100x100まで

 勤務表ソフトではありますが、数独を汎用的にプログラムできれば、GUIを拡張できる能力の強力な証明になるので、搭載pythonで汎用的に書き直してみました。100x100までは、動作を確認しました。GUIでは、100x100結果は、表示しきれないので、ExcelにExportさせた結果が以下です。簡易的ですが、一応各行列の和が各々5050になっていることを確認しました。

∵ n(n+1)/2=5050




Pythonソースは、以下が全ソースです。このソースは、数独サイズに依存しません。4x4でも、100x100でも同じソースでOKです。では、どうやってサイズを可変するかというと、GUI上で、スタッフ数、Day数、シフト数をGUIで定義しなおせばよいです。例えば、4x4の場合は、4人、4Days,4シフトを定義します。

<オリジナル問題の作り方>
1)ブランク状態(解が存在するなら適度な数字が入っていてもよい)で解を求めます。
2)解を予定に送ります。
3)適当な箇所をブランクにします。
4)解を求め2解目が存在しないことを確認します。
5)3)4)を気力が続く限り続け、2解目が存在するときに諦めて、その前の状態を問題として終了します。



数独の条件としては、1解しか存在しないことが条件となります。例えば、100x100で1ブランクでも作れば、1解しか存在しないので、超巨大ではあるけれども超簡単な数独問題となります。1解しか存在しない証明は難しいですが、スケジュールナースを活用すれば、簡単にチェック出来ます。

import sc3
import math

if math.sqrt(len(AllDays)) !=math.sqrt(len(shiftdef)):
    raise ValueError("AllDays and shiftdef are inconsistent")
blocks=int(math.sqrt(len(AllDays)))

for day in AllDays: #column
	for shift in shiftdef.keys():
		V=[]
		for person in A_Member_in_All:
			V.append(sc3.GetShiftVar(person,day,shift))
		sc3.AddHard(sc3.SeqLE(1,1,V),'')
for person in A_Member_in_All: #row
	for  shift in shiftdef.keys():
		V=[]
		for  day in AllDays:
			V.append(sc3.GetShiftVar(person,day,shift))
		sc3.AddHard(sc3.SeqLE(1,1,V),'')
for person in range(0,len(A_Member_in_All),blocks): #block
	for shift in shiftdef.keys():
		for  day in range(0,len(AllDays),blocks):
			V=[]
			for  i  in range(blocks):
				for  j in range(blocks):
					V.append(sc3.GetShiftVar(person+i,day+j,shift))
			sc3.AddHard(sc3.SeqLE(1,1,V),'')


0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。