NScripterで数独を解く。

NScripter Lua


タイトル通り。
下記のサンプルでは、数独 －無料で数独パズルをプレイ、プリントそしてシェアの#6948を解いている。

luaで解説。

local game = field.new()で新しい盤面オブジェクトを作る。
game.write(x, y, num)で、盤面に既にわかっている数値を書き込む。
game:run()で解く。

NScripterで解説。

new_fieldで盤面を初期化。
cell_write x,y,numで盤面に数値を書き込む。
runで残りを計算する。

限界について

ルールの性質上、初期値があまりにも少ないと絞り込めなくなるが、その場合、このアルゴリズムは解けるところまで解いて終了する。

計算方法について

二つのアルゴリズムを使う。

その1

1.あるセルが決定すると、それは周囲のセルの可能性を減らす。
2.あるセルの可能性が一つになった場合、そのセルは残った可能性に決定される。1に戻る。

その2

1.あるグループ（列/行/3*3のクラスタ）それぞれについて見る。
2.そのグループの中で、ある値になる可能性を持つセルが一つしかなければ、その値に決定される。

感想

デバッグ時間の方が長かったよ！

00.txt

*define
deletemenu
game
*start
; 6948
new_field
cell_write 1,1,8
cell_write 1,3,1
cell_write 1,4,7
cell_write 1,5,9
cell_write 1,8,6
cell_write 2,6,5
cell_write 2,9,1
cell_write 3,2,3
cell_write 4,1,2
cell_write 4,2,6
cell_write 4,6,8
cell_write 4,7,4
cell_write 5,5,7
cell_write 6,3,3
cell_write 6,4,1
cell_write 6,6,9
cell_write 6,8,7
cell_write 6,9,2
cell_write 7,8,8
cell_write 8,1,7
cell_write 8,4,2
cell_write 9,2,9
cell_write 9,5,6
cell_write 9,6,3
cell_write 9,7,2
cell_write 9,9,7
click
run
click
end

system.lua

--system
NL_dofile("cell.lua")
NL_dofile("field.lua")

local game

NSExec("luasub new_field")
function NSCOM_new_field()
	game = field.new()
end

NSExec("luasub cell_write")
function NSCOM_cell_write()
	local x = NSPopInt()
	NSPopComma()
	local y = NSPopInt()
	NSPopComma()
	game:write(x, y, NSPopInt())
end

NSExec("luasub run")
function NSCOM_run()
	game:run()
end

field.lua

-- field
module("field", package.seeall)

local index = {}
local class = {__index=index}

index.write = function(self, x, y, num)
	return self.field[x][y]:decide_number(num)
end

index.decide = function(self, cell) -- セルの数値が決まったら、その他のセルを処理する。
	NSExec("caption \"decide\"")
	for x = 1, 9 do
		local cell2 = self.field[x][cell.y]
		if cell.x ~= cell2.x then cell2:delete_pos(cell.decide) end
	end
	for y = 1, 9 do
		local cell2 = self.field[cell.x][y]
		if cell.y ~= cell2.y then cell2:delete_pos(cell.decide) end
	end
	for x = cell.sx, cell.ex do
		for y = cell.sy, cell.ey do
			local cell2 = self.field[x][y]
			if cell.x ~= cell2.x then
				if cell.y ~= cell2.y then
					cell2:delete_pos(cell.decide)
				end
			end
		end
	end
end

index.run = function(self)
	local queue = self.queue
	while true do
		self:all_group_calc()
		local cell = table.remove(queue)
		if type(cell) == "nil" then break end
		cell:calc()
	end
end

index.all_group_calc = function(self)
	local group
	for x = 1, 9 do
		group = {}
		for y = 1, 9 do group[y] = self.field[x][y] end
		self:group_calc(group)
	end
	for y = 1, 9 do
		group = {}
		for x = 1, 9 do group[y] = self.field[x][y] end
		self:group_calc(group)
	end
	for sx = 0, 2 do
		for sy = 0, 2 do
			group = {}
			for ex = 1, 3 do
				for ey = 1, 3 do
					group[1+#group] = self.field[sx*3+ex][sy*3+ey]
				end
			end
			self:group_calc(group)
		end
	end
end

index.group_calc = function(self, group) -- グループ計算
	-- ある一つのグループを調べる。その中で、あるセルのみが持つ可能性を調べる。
	local pos_list = {}
	for pos = 1, 9 do
		pos_list[pos] = {}
		for dummy, cell in ipairs(group) do
			if cell.decide then
				-- 既に決定したセルなら何もしない。
			else
				if cell.pos[pos] then -- その可能性があるなら。
					pos_list[pos][1+#pos_list[pos]] = cell
				end
			end
		end
	end
	for pos = 1, 9 do
		if 1 == #pos_list[pos] then
			pos_list[pos][1]:decide_number(pos)
		end
	end
end

function new()
	local self = setmetatable({}, class)
	self.field = {}
	for x = 1, 9 do
		self.field[x] = {}
		for y = 1, 9 do
			self.field[x][y] = cell.new(self, x, y)
		end
	end
	self.queue = {}
	NSUpdate()
	return self
end

cell.lua

-- cell
module("cell", package.seeall)

local index = {}
local class = {__index=index}

index.delete_pos = function(self, pos) -- 可能性を削除する。
	if self.pos[pos] then else return 0 end -- 既に削除されていれば何もしない。

	NSExec("caption \"pos("..tostring(self.x)..","..tostring(self.y)..")="..tostring(pos).."\"")

	self.pos[pos] = nil
	self.count = self.count - 1
	self:print() -- セルを表示
	if self.count == 1 then -- もし、残った可能性が一つになったら、フィールドのチェックキューに追加。
		local field = self.field
		local queue = field.queue
		queue[1+#queue] = self
	end
	return self.count
end

index.decide_number = function(self, num) -- セルの数値を決定する
	if self.pos[num] then else return false end -- 入れられる数値しか入れない。
	if self.decide then return false end -- 既に決定していたら何もしない。

	NSExec("caption \"decide("..tostring(self.x)..","..tostring(self.y)..")="..tostring(num).."\"")

	self.decide = num -- 数値を決定する。
	self.pos = {}
	self.pos[num] = true
	self.count = 1
	self:print() -- セルを表示

	self.field:decide(self) -- 他のセルを処理する。

	return true
end

index.calc = function(self) -- セルの数値を決定できるかどうか。決定できたら、決定する。
	if self.count ~= 1 then return false end
	if self.decide then return false end -- 既に決定されている。

	NSExec("caption \"calc("..tostring(self.x)..","..tostring(self.y)..")\"")

	local num = 0
	for i = 1, 9 do
		num = i
		if self.pos[i] then break end
	end
	return self:decide_number(num)
end

local alpha_count = 16
local alpha_base = 255 - 9 * alpha_count
local cell_size = 50

local han2zen = {}
han2zen[1] = "１"
han2zen[2] = "２"
han2zen[3] = "３"
han2zen[4] = "４"
han2zen[5] = "５"
han2zen[6] = "６"
han2zen[7] = "７"
han2zen[8] = "８"
han2zen[9] = "９"
index.print = function(self) -- セルを表示する。
	NSExec("caption \"print\"")
	if self.decide then -- 既に決定している。
		NSSpMove(self.sp2, self.px, self.py, 255)
		local str = ":s/"..tostring(cell_size)..","..tostring(cell_size)..",0;#000000"..han2zen[self.decide]
		NSSpLoad(self.sp1, str)
		NSSpMove(self.sp1, self.px, self.py, 255)
		NSSpVisible(self.sp1, true)
	else -- 未決
		local str = ""
		for i = 1, 9 do if self.pos[i] then str = str .. han2zen[i] else str = str .. "　" end end
		str = "strsp "..tostring(self.sp1)..",\""..str.."\","..tostring(self.px)..","..tostring(self.py)..",3,3,"..tostring(math.floor(cell_size/3))..","..tostring(math.floor(cell_size/3))..",0,0,0,0,#000000"
		NSExec(str)
		NSSpMove(self.sp2, self.px, self.py, alpha_base + self.count * alpha_count)
	end
	NSUpdate()
	NSSleep(1)
end

local sp_num = 0

function new(field, x, y)
	local self = setmetatable({}, class)
	self.x = x -- セルのx
	self.y = y -- セルのy
	self.field = field -- セルの所属するフィールド
	self.count = 9 -- セルの可能性の数
	local pos = {}
	for i = 1, 9 do pos[i] = true end
	self.pos = pos -- セルの可能性

	-- グループ処理
	self.sx = 4; self.ex = 6
	if x < 4 then self.sx = 1; self.ex = 3 end
	if x > 6 then self.sx = 7; self.ex = 9 end
	self.sy = 4; self.ey = 6
	if y < 4 then self.sy = 1; self.ey = 3 end
	if y > 6 then self.sy = 7; self.ey = 9 end
	

	-- 表示用パラメータ
	self.px = cell_size * ( x - 1 ) -- セルの表示x座標
	self.py = cell_size * ( y - 1 ) -- セルの表示y座標
	self.sp1 = sp_num -- セルのスプライト№
	sp_num = sp_num + 1
	self.sp2 = sp_num -- 土台のスプライト№
	sp_num = sp_num + 1
	
	-- セルを準備する。
	NSSpLoad(self.sp2, ":c;>"..tostring(cell_size)..","..tostring(cell_size)..",#FFFFFF")
	NSSpMove(self.sp2, self.px, self.py, 255)
	NSSpVisible(self.sp2, true)
	self:print()
	
	-- 返す。
	return self
end