It is currently March 28th, 2024, 10:26 pm

Sudoku Solver skin

Skins that don't neatly fit into other categories
FlyingHyrax
Posts: 232
Joined: July 1st, 2011, 1:32 am
Location: US

Sudoku Solver skin

Post by FlyingHyrax »

<update>
Done. </update>


So far I've only implemented constraint propagation, so it can only solve easy puzzles.
This, for example, is the puzzle from the Sudoku page on Wikipedia.
(Also, the gif is 2x speed, so no, I'm not nearly that good with a mouse.)

Image

It's finals week, so maybe I'll get the search algorithm done soon, maybe I won't. I'll post the Lua code when it's more complete, but in the mean time, if you're interested in how it works, I'm essentially following Peter Norvig's Python solver.
(I had a purely brute force algorithm written in Java, but it was rather ugly and relatively slow.)
Last edited by FlyingHyrax on January 6th, 2014, 8:19 pm, edited 2 times in total.
Flying Hyrax on DeviantArt
FlyingHyrax
Posts: 232
Joined: July 1st, 2011, 1:32 am
Location: US

Re: W.i.P. - Lua solver 'finished'

Post by FlyingHyrax »

The Lua code is now pretty much final. I also added a measure option to make the script update the skin every time a value is placed - I think the effect is pretty neat, though it really takes a bite out of your CPU.

Image

I'm planning a few more features skin-side, so it might be a few more days before I release the skin as a whole.

Here's the Lua; critiques welcome as always:

Code: Select all

-- definitions for generating cell labels/keys
rows = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'}
cols = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
rowsqr = {
	{'A', 'B', 'C'},
	{'D', 'E', 'F'},
	{'G', 'H', 'I'}
}
colsqr = {
	{'1', '2', '3'},
	{'4', '5', '6'},
	{'7', '8', '9'}
}
cells = {}		-- a list of all 81 cell labels
unitlist = {}	-- a list of lists, where each is a unit of labels
units = {}		-- a list with each cell mapped to its lists of units
peers = {}		-- a list with each cell mapped to a list of peers

measures = {}	-- list for the measures that hold cell values in the skin

status = nil
BulletTime = false	-- controls whether or not the skin Updates every time a value is placed

function Update()
	return status
end

-- Given a string or number, sets the text of the 'statusMessage' meter to
-- that value and updates the skin
function SetStatus(text)
	status = text
	SKIN:Bang('!SetOption', 'statusMessage', 'Text', text)
	SKIN:Bang('!Update')
end

-- script setup; runs on skin load and refresh
-- generates the lists of keys, units, peers, and measure objects
function Initialize()
	SetStatus('initializing...')
	-- Generate list of all grid cells:
	cells = Cross(rows, cols)
	-- Generate list of unit lists:
	for _, c in pairs(cols) do	-- column units
		table.insert(unitlist, Cross(rows, c))
	end
	for _, r in pairs(rows) do	-- row units
		table.insert(unitlist, Cross(r, cols))
	end
	for _, rs in pairs(rowsqr) do -- box units
		for _, cs in pairs(colsqr) do
			table.insert(unitlist, Cross(rs, cs))
		end
	end
	
	-- now that we have our list of cells and list of units, for each cell:
	for cell, _ in pairs(cells) do
		
		-- generate a hashtable mapping of keys to unit lists
		units[cell] = {}	-- init
		-- for each unit list
		for _, unit in pairs(unitlist) do
			-- test if this cell is in this unit
			if unit[cell] then
				-- if yes, add that unit list to the units collection for this cell
				table.insert(units[cell], unit)
			end
		end
		
		-- generate a hashtable mapping of keys to peers:
		peers[cell] = {}	-- init
		-- for each unit list for this cell
		for _, unit in pairs(units[cell]) do
			-- for every cell in this unit list
			for peer, _ in pairs(unit) do
				-- excluding the cell itself
				if peer ~= cell then
					-- add the member of the unit list to a list of peers for this cell
					peers[cell][peer] = true
				end
			end
		end
		
		-- populate the measures table w/ references to skin measures:
		measures[cell] = SKIN:GetMeasure('m' .. cell)
	end
	
	BulletTime = SELF:GetOption('SlowMotion', '0') == '1' and true or false
	SetStatus('ready')
end

-- called from skin: gets clue cells from skin, validates the puzzle,
-- and solves the puzzle if it is valid
function Solve()
	SetStatus('solving...')
	
	local puzzle = InitPuzzle()
	local clues = GetSkinClues()
	local valid = true
	for cell, value in pairs(clues) do
		if not Place(puzzle, cell, value) then
			valid = false
			break
		end
	end
	
	if valid then
		local result = Search(puzzle)
		if result then
			SetStatus('solved')
			PopulateSkin(result)
		else
			SetStatus('unsolved')
			PopulateSkin(puzzle)
		end
	else
		SetStatus('invalid puzzle')
		PopulateSkin(puzzle)
	end
end

-- Returns a table mapping every cell to a set of digits 1..9
function InitPuzzle()
	local values = {}
	for cell, _ in pairs(cells) do
		values[cell] = {[1]=true, [2]=true, [3]=true, [4]=true, [5]=true, [6]=true, [7]=true, [8]=true, [9]=true}
	end
	return values
end

-- Returns a table mapping clue cells in the skin with their values
-- by checking cell measures which have a value other than 0
function GetSkinClues()
	local values = {}
	for cell, msr in pairs(measures) do
		local val = msr:GetValue()
		-- if the retrieved value is in our list of digits 1..9
		if cols[val] then
			values[cell] = val
		end
	end
	return values
end

-- assigns value 'v' to cell 'c' in puzzle table 'values'
function Place(values, c, v)
	for otherv, _ in pairs(values[c]) do
		if otherv == v then
			values[c][otherv] = true
		else 
			if not RemoveVal(values, c, otherv) then
				return false
			end
		end
	end
	if BulletTime then
		PutSkinVal(c, v)
	end
	return values
end

-- removes value 'v' from set of possibilities for cell 'c' in the puzzle table 'values'
function RemoveVal(values, c, v)
	
	if not values[c][v] then
		return true	-- v is not in list for c - already removed
	else
		values[c][v] = nil	-- remove v from c's list of possible values
	end
	
	local len = Count(values[c])
	if len == 0 then
		-- if the cell has 0 options left, there is a contradiction
		return false
	elseif len == 1 then
		-- if the cell has 1 option left, trigger first rule
		if not EliminateFromPeers(values, c, First(values[c])) then
			return false	-- contradiction further up the call stack
		end
		if BulletTime then
			PutSkinVal(c, First(values[c]))
		end
	else
		-- if the cell has >1 options left, tirgger second rule
		if not UnitCheck(values, c, v) then
			return false
		end
	end
	
	return true -- removal and any subsequent propagation was successful
end

-- FIRST RULE: 
-- if a cell has only one possible value, eliminate that value from the cell's peers
function EliminateFromPeers(values, c, v)
	-- print('eliminating ' .. v .. ' from peers of ' .. c)
	for peer, _ in pairs(peers[c]) do
		if not RemoveVal(values, peer, v) then
			return false
		end
	end
	return true
end

-- SECOND RULE: 
-- if a unit has only one place for a value, put that value in that place
function UnitCheck(values, c, v)
	-- for each unit that contains cell c:
	for _, unit in pairs(units[c]) do
		local places = {}
		-- for each cell in this unit:
		for unitc, _ in pairs(unit) do
			-- track the cells that have v as a possible value:
			if values[unitc][v] then
				places[unitc] = true
			end
		end
		-- if there is only one cell with v as an option in this unit:
		if Count(places) == 1 then
			-- put v in that cell
			if not Place(values, First(places), v) then
				return false
			end
		end
	end
	return true	-- any placement was successful
end

-- recursive search/guessing function to go where pure deduction cannot
function Search(values)
	-- check if we broke earlier
	if not values then 
		return false 
	end
	-- check if 'solved'
	local solved = true
	for c, vals in pairs(values) do
		if Count(vals) ~= 1 then
			solved = false
			break
		end
	end
	if solved then
		return values
	end
	-- if not solved, find cell w/ fewest values
	local minc = nil
	for c, vals in pairs(values) do
		local lenvals = Count(vals)
		if lenvals > 1 then
			if not minc or lenvals < Count(values[minc]) then
				minc = c
			end
		end
	end
	-- for every possible value of minc, assign that value to a new copy
	-- of the values table and see if it works
	for kv, _ in pairs(values[minc]) do
		local valuesCopy = CopyVals(values)
		local retval = Search(Place(valuesCopy, minc, kv))
		if retval then 
			return retval
		end
	end
	-- if we reach here, then no recurrence from above solved the puzzle
	return false
end

-- returns a copy of a puzzle/values table
function CopyVals(values)
	local copy = {}
	for cell, vals in pairs(values) do
		copy[cell] = {}
		for kv, b in pairs(vals) do
			copy[cell][kv] = b
		end
	end
	return copy
end

-- count items in a set (table of key=true pairs)
function Count(set)
	local n = 0
	for kv, b in pairs(set) do
		if b then
			n = n + 1
		end
	end
	return n
end

-- returns the first key in a set (table of key=true pairs)
-- or nil if empty (or some other error)
function First(set)
	local f = nil
	for k, b in pairs(set) do
		f = k
		break
	end
	return f
end

-- given a cell and a value, sets the 'Formula=<value>' in the measure m<cell>;
-- used to populate the skin with results during/after solving the puzzle
-- Putting an '!Update' bang causes the cool cell population effect,
-- though it takes time: we could update ONCE in PopulateSkin()
function PutSkinVal(cell, value)
	local msr = measures[cell]:GetName()
	SKIN:Bang('!SetOption', msr, 'Formula', value)
	SKIN:Bang('!UpdateMeasure', msr)
	if BulletTime then
		SKIN:Bang('!Update')
	end
end

-- Uses putSkinVal to set every cell in the skin using the 'values' table 
-- (which represents the puzzle).  Any cell with more than one possible value 
-- is set to 0 (blank).
function PopulateSkin(values)
	for cell, vals in pairs(values) do
		if Count(vals) == 1 then
			PutSkinVal(cell, First(vals))
		else
			PutSkinVal(cell, 0)
		end
	end
	if not BulletTime then
		SKIN:Bang('!Update')
	end
end

-- Creates a set of string keys: all values for keys in the table are 'true',
-- which makes it trivial to check if a table contains a value.
-- Used to create tables of cells and units
function Cross(t1, t2)
	local result = {}
	if type(t1) ~= 'table' then
		for _, v in pairs(t2) do
			result[t1..v] = true
		end
	elseif type(t2) ~= 'table' then
		for _, v in pairs(t1) do
			result[v..t2] = true
		end
	else
		for _, v1 in pairs(t1) do
			for _, v2 in pairs(t2) do
				result[v1..v2] = true
			end
		end
	end
	return result
end
Flying Hyrax on DeviantArt