It is currently December 6th, 2023, 8:06 am

## 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

<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.) 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'

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. 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
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] = {=true, =true, =true, =true, =true, =true, =true, =true, =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