Update of /cvsroot/wxlua/wxLua/samples
In directory sc8-pr-cvs9.sourceforge.net:/tmp/cvs-serv7387/samples
Modified Files:
wxluasudoku.wx.lua
Log Message:
speed up brute force solver by scanning first
Index: wxluasudoku.wx.lua
===================================================================
RCS file: /cvsroot/wxlua/wxLua/samples/wxluasudoku.wx.lua,v
retrieving revision 1.61
retrieving revision 1.62
diff -C2 -d -r1.61 -r1.62
*** wxluasudoku.wx.lua 4 Jan 2007 23:28:05 -0000 1.61
--- wxluasudoku.wx.lua 8 Jan 2007 23:39:52 -0000 1.62
***************
*** 36,39 ****
--- 36,43 ----
-- ============================================================================
-- Simple functions to count the total number of elements in a table
+ -- Notes about speed : using for loop and pairs() in TableCount is 2X faster
+ -- than using while loop and next(table). However using next() is slightly
+ -- faster than using for k,v in pairs(t) do return true end in TableIsEmpty.
+
function TableCount(atable)
local count = 0
***************
*** 41,58 ****
return count
end
- function TableICount(atable)
- local count = 0
- for k, v in ipairs(atable) do count = count + 1 end
- return count
- end
function TableIsEmpty(atable)
! for k, v in pairs(atable) do return false end
! return true
end
-- Set a value in the table or subtable, first making sure that the subtables
-- are created first.
! -- a = TableSetValue(a, 3, "How", "Are", 4, "You") ==> a.How.Are[4].You = 3
! function TableSetValue(atable, value, ...)
if type(atable) ~= "table" then atable = {} end
local t = atable -- t moves up levels through t
--- 45,56 ----
return count
end
function TableIsEmpty(atable)
! return next(atable) == nil
end
-- Set a value in the table or subtable, first making sure that the subtables
-- are created first.
! -- a = TableSetValue(3, a, "How", "Are", 4, "You") ==> a.How.Are[4].You = 3
! function TableSetValue(value, atable, ...)
if type(atable) ~= "table" then atable = {} end
local t = atable -- t moves up levels through t
***************
*** 386,401 ****
-- ============================================================================
-- Check the validity of rows, cols, cells, blocks, values
- function sudoku.IsValidRowN(row)
- return (row >= 1) and (row <= 9)
- end
- function sudoku.IsValidColN(col)
- return (col >= 1) and (col <= 9)
- end
- function sudoku.IsValidCellN(cell)
- return (cell >= 1) and (cell <= 81)
- end
- function sudoku.IsValidBlockN(block)
- return (block >= 1) and (block <= 9)
- end
function sudoku.IsValidValueN(value)
return (value >= 1) and (value <= 9)
--- 384,387 ----
***************
*** 509,524 ****
-- ============================================================================
- -- Get all the row values for the row as a table[value] = { cell1, cell2... }
- -- if no value then table[value] = nil
- function sudoku.GetRowValues(row, sudokuTable)
- return sudokuTable.row_values[row]
- end
- function sudoku.GetColValues(col, sudokuTable)
- return sudokuTable.col_values[col]
- end
- function sudoku.GetBlockValues(block, sudokuTable)
- return sudokuTable.block_values[block]
- end
-
-- Set the row_values, col_values, block_values in the sudokuTable
-- eg. row values table is row_values[row#][value][cell#] = cell#
--- 495,498 ----
***************
*** 537,543 ****
if not sudokuTable.block_values[block] then sudokuTable.block_values[block] = {} end
! if sudoku.HasCellValue(cell, sudokuTable) then
! local value = sudoku.GetCellValue(cell, sudokuTable)
if not sudokuTable.row_values[row][value] then
sudokuTable.row_values[row][value] = {[cell] = cell}
--- 511,517 ----
if not sudokuTable.block_values[block] then sudokuTable.block_values[block] = {} end
! local value = sudoku.GetCellValue(cell, sudokuTable)
+ if sudoku.IsValidValueN(value) then
if not sudokuTable.row_values[row][value] then
sudokuTable.row_values[row][value] = {[cell] = cell}
***************
*** 743,749 ****
-- gather up all the set values in row, col, and block
! local rowValues = sudoku.GetRowValues(row, sudokuTable)
! local colValues = sudoku.GetColValues(col, sudokuTable)
! local blockValues = sudoku.GetBlockValues(sudoku.RowColToBlock(row, col), sudokuTable)
-- remove the set values from the possible values
for v = 1, 9 do
--- 717,723 ----
-- gather up all the set values in row, col, and block
! local rowValues = sudokuTable.row_values[row]
! local colValues = sudokuTable.col_values[col]
! local blockValues = sudokuTable.block_values[sudoku.RowColToBlock(row, col)]
-- remove the set values from the possible values
for v = 1, 9 do
***************
*** 761,781 ****
for cell = 1, 81 do
local row, col = sudoku.CellToRowCol(cell)
! if sudoku.HasCellValue(cell, sudokuTable) then
! sudokuTable = sudoku.SetCellPossible(cell, {}, sudokuTable)
! else
! local possible = {}
! local block = sudoku.CellToBlock(cell)
for v = 1, 9 do
! if (sudoku.GetRowValues(row, sudokuTable)[v] == nil) and
! (sudoku.GetColValues(col, sudokuTable)[v] == nil) and
! (sudoku.GetBlockValues(block, sudokuTable)[v] == nil) then
possible[v] = v
end
end
- sudokuTable = sudoku.SetCellPossible(cell, possible, sudokuTable)
end
end
--- 735,754 ----
for cell = 1, 81 do
local row, col = sudoku.CellToRowCol(cell)
+ local possible = {}
! if not sudoku.HasCellValue(cell, sudokuTable) then
! local block = sudoku.CellToBlock(cell)
for v = 1, 9 do
! if (sudokuTable.row_values[row][v] == nil) and
! (sudokuTable.col_values[col][v] == nil) and
! (sudokuTable.block_values[block][v] == nil) then
possible[v] = v
end
end
end
+
+ sudokuTable = sudoku.SetCellPossible(cell, possible, sudokuTable)
end
***************
*** 1268,1272 ****
-- first time through find possible to limit choices, subsequent calls ok
local s = sudoku.CreateTable()
! s = sudoku.SetValues(sudokuTable.values, s)
-- table consists of guesses[cell] = #num
-- guesses.current is current guess #
--- 1241,1259 ----
-- first time through find possible to limit choices, subsequent calls ok
local s = sudoku.CreateTable()
!
! -- finding all the possibilities is slow, but at least do solve scan
! --s.flags[sudoku.ELIMINATE_NAKED_PAIRS] = true
! --s.flags[sudoku.ELIMINATE_HIDDEN_PAIRS] = true
! --s.flags[sudoku.ELIMINATE_NAKED_TRIPLETS] = true
! --s.flags[sudoku.ELIMINATE_HIDDEN_TRIPLETS] = true
! --s.flags[sudoku.ELIMINATE_NAKED_QUADS] = true
! --s.flags[sudoku.ELIMINATE_HIDDEN_QUADS] = true
!
! --s = sudoku.SetValues(sudokuTable.values, s)
! s.values = TableCopy(sudokuTable.values)
! s = sudoku.CalcRowColBlockValues(s)
! s = sudoku.CalcAllPossible(s)
! s = sudoku.SolveScan(s)
!
-- table consists of guesses[cell] = #num
-- guesses.current is current guess #
|
