[Wxlua-commit] wxLua/samples wxluasudoku.wx.lua,1.47,1.48

[John L. <jr...@us...>]

Update of /cvsroot/wxlua/wxLua/samples
In directory sc8-pr-cvs9.sourceforge.net:/tmp/cvs-serv30914/wxLua/samples

Modified Files:
	wxluasudoku.wx.lua 
Log Message:
first cut at generating unique puzzles


Index: wxluasudoku.wx.lua
===================================================================
RCS file: /cvsroot/wxlua/wxLua/samples/wxluasudoku.wx.lua,v
retrieving revision 1.47
retrieving revision 1.48
diff -C2 -d -r1.47 -r1.48
*** wxluasudoku.wx.lua	25 May 2006 03:55:23 -0000	1.47
--- wxluasudoku.wx.lua	30 May 2006 05:57:12 -0000	1.48
***************
*** 588,595 ****
  --   if exceptTable then don't remove it from exceptTable[cell#] = true
  function sudoku.RemovePossibleAll(row, col, value, sudokuTable, exceptTable)
      -- cell will be done below, note it's not any faster to code it all here
!     sudokuTable = sudoku.RemovePossibleRow(row, value, sudokuTable, exceptTable)
!     sudokuTable = sudoku.RemovePossibleCol(col, value, sudokuTable, exceptTable)
!     sudokuTable = sudoku.RemovePossibleBlock(sudoku.RowColToBlock(row, col), value, sudokuTable, exceptTable)
      return sudokuTable
  end
--- 588,616 ----
  --   if exceptTable then don't remove it from exceptTable[cell#] = true
  function sudoku.RemovePossibleAll(row, col, value, sudokuTable, exceptTable)
+     exceptTable = exceptTable or {}
+     local cell
+     local block_cell = sudoku.BlockToCell(sudoku.RowColToBlock(row, col))
+ 
+     for rcb = 1, 9 do
+         cell = sudoku.RowColToCell(rcb, col)
+         if not exceptTable[cell] then
+             sudokuTable = sudoku.RemoveCellPossible(cell, value, sudokuTable)
+         end
+ 
+         cell = sudoku.RowColToCell(row, rcb)
+         if not exceptTable[cell] then
+             sudokuTable = sudoku.RemoveCellPossible(cell, value, sudokuTable)
+         end
+ 
+         cell = rcb - 1 + block_cell + sudoku.LinearBlockCells[rcb]
+         if not exceptTable[cell] then
+             sudokuTable = sudoku.RemoveCellPossible(cell, value, sudokuTable)
+         end
+     end
+ 
      -- cell will be done below, note it's not any faster to code it all here
!     --sudokuTable = sudoku.RemovePossibleRow(row, value, sudokuTable, exceptTable)
!     --sudokuTable = sudoku.RemovePossibleCol(col, value, sudokuTable, exceptTable)
!     --sudokuTable = sudoku.RemovePossibleBlock(sudoku.RowColToBlock(row, col), value, sudokuTable, exceptTable)
      return sudokuTable
  end
***************
*** 1183,1206 ****
  -- Brute force recursive solver
  --   (call with only the SudokuTable, don't enter other parameters)
! function sudoku.SolveBruteForce(sudokuTable, simpleTable, guesses, cell)
!     cell = cell or 1
!     local s = simpleTable
! 
      -- first time through find possible to limit choices, subsequent calls ok
!     if not s then
!         s = sudoku.CreateTable()
!         s = sudoku.SetValues(sudokuTable.values, s)
!         -- table consists of guesses[cell] = #num
!         -- guesses.current is current guess #
!         guesses = { current = 0 }
!         for n = 1, 81 do guesses[n] = 0 end
!         -- we don't need these for this and they just slow TableCopy down
!         --  they're recreated at the end using UpdateTable
!         s.row_values   = nil
!         s.col_values   = nil
!         s.block_values = nil
!         s.invalid      = nil
!         s.flags        = nil
!     end
  
      if sudoku.SolveBruteForceHook then
--- 1204,1228 ----
  -- Brute force recursive solver
  --   (call with only the SudokuTable, don't enter other parameters)
! function sudoku.SolveBruteForce(sudokuTable, backwards)
      -- 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 #
!     local guesses = { current = 0 }
!     for n = 1, 81 do guesses[n] = 0 end
!     -- we don't need these for this and they just slow TableCopy down
!     --  they're recreated at the end using UpdateTable
!     s.row_values   = nil
!     s.col_values   = nil
!     s.block_values = nil
!     s.invalid      = nil
!     s.flags        = nil
! 
!     return sudoku.DoSolveBruteForce(sudokuTable, backwards, s, guesses, 1)
! end
! 
! function sudoku.DoSolveBruteForce(sudokuTable, backwards, simpleTable, guesses, cell)
!     local s = simpleTable
  
      if sudoku.SolveBruteForceHook then
***************
*** 1215,1219 ****
              local possible = sudoku.GetCellPossible(cell, s)
  
!             for k, v in pairs(possible) do
                  -- try a number and remove it as a possibility
                  s = sudoku.RemoveCellPossible(cell, k, s)
--- 1237,1245 ----
              local possible = sudoku.GetCellPossible(cell, s)
  
!             --for k, v in pairs(possible) do
!             for n = 1, 9 do
!                 local k = n
!                 if backwards == true then k = 10 - n end
!                 if possible[k] then
                  -- try a number and remove it as a possibility
                  s = sudoku.RemoveCellPossible(cell, k, s)
***************
*** 1225,1231 ****
                  -- don't use SetValue since we only care about possible
                  s1.values[cell] = k --sudoku.SetValue(row, col, k, s1)
!                 guesses[cell] = guesses[cell] + 1
                  guesses.current = guesses.current + 1
!                 s1, g = sudoku.SolveBruteForce(sudokuTable, s1, guesses, cell+1)
                  -- if s1 then success! we're all done
                  if s1 then
--- 1251,1257 ----
                  -- don't use SetValue since we only care about possible
                  s1.values[cell] = k --sudoku.SetValue(row, col, k, s1)
!                 guesses[cell]   = guesses[cell] + 1
                  guesses.current = guesses.current + 1
!                 s1, g = sudoku.DoSolveBruteForce(sudokuTable, backwards, s1, guesses, cell+1)
                  -- if s1 then success! we're all done
                  if s1 then
***************
*** 1234,1237 ****
--- 1260,1264 ----
                      return s2, g
                  end
+                 end
              end
  
***************
*** 1247,1250 ****
--- 1274,1300 ----
  end
  
+ function sudoku.IsUniquePuzzle(sudokuTable)
+     local s1, g1 = sudoku.SolveBruteForce(sudokuTable, false)
+     local s2, g2 = sudoku.SolveBruteForce(sudokuTable, true)
+ 
+     if (not s1) or (not s2) then return nil, g1 end
+ 
+     if not sudoku.IsSamePuzzle(s1, s2) then
+         return nil, g1
+     end
+ 
+     return s1, g1
+ end
+ 
+ function sudoku.IsSamePuzzle(s1, s2)
+     for cell = 1, 81 do
+         if sudoku.GetCellValue(cell, s1) ~= sudoku.GetCellValue(cell, s2) then
+             return false
+         end
+     end
+ 
+     return true
+ end
+ 
  -- ============================================================================
  -- Create a full puzzle with all the values
***************
*** 1322,1335 ****
      math.randomseed(os.time()+1)
      local i = 0
  
      while i < 81 - num_cells_to_keep do
          local cell = math.random(81)
!         if sudoku.HasCellValue(cell, sudokuTable) then
!             sudokuTable = sudoku.SetCellValue(cell, 0, sudokuTable)
!             i = i + 1
          end
      end
  
!     return sudokuTable
  end
  
--- 1372,1422 ----
      math.randomseed(os.time()+1)
      local i = 0
+     local count = 0
+     local last_cell
+     local soln = TableCopy(sudokuTable)
+     local bad_cells = {}
+     local bad_cells_count = 0
  
      while i < 81 - num_cells_to_keep do
          local cell = math.random(81)
!         count = count + 1
! 
!         if sudoku.GeneratePuzzleDifficultyHook then
!             if not sudoku.GeneratePuzzleDifficultyHook(count, i, cell) then
!                 return nil, count
!             end
!         end
! 
!         -- recursively call this function to restart finding unique soln
!         if bad_cells_count > i then
!             return sudoku.GeneratePuzzleDifficulty(num_cells_to_keep, sudokuTable)
!         end
! 
!         if (not bad_cells[cell]) and (last_cell ~= cell) and sudoku.HasCellValue(cell, sudokuTable) then
!             -- test if soln going forward is same as soln backwards and original
!             local s = TableCopy(sudokuTable)
!             s = sudoku.SetCellValue(cell, 0, s)
!             local soln1 = sudoku.SolveBruteForce(s, false)
! 
!             if not sudoku.IsSamePuzzle(soln, soln1) then
!                 -- don't try same cell twice in a row
!                 last_cell = cell
!                 bad_cells[cell] = true
!                 bad_cells_count = bad_cells_count + 1
!             else
!                 local soln2 = sudoku.SolveBruteForce(s, true)
!                 if not sudoku.IsSamePuzzle(soln, soln2) then
!                     last_cell = cell
!                     bad_cells[cell] = true
!                     bad_cells_count = bad_cells_count + 1
!                 else
!                     sudokuTable = sudoku.SetCellValue(cell, 0, sudokuTable)
!                     i = i + 1
!                 end
!             end
          end
      end
  
!     return sudokuTable, count
  end
  
***************
*** 2849,2852 ****
--- 2936,2940 ----
      local solve_progress = 0
      local start_time = os.time()
+     local solve_completed = true
  
      local progressDialog = wx.wxProgressDialog("wxLuaSudoku - Generating...",
***************
*** 2856,2860 ****
                             wx.wxPD_AUTO_HIDE+wx.wxPD_CAN_ABORT+wx.wxPD_ELAPSED_TIME)
  
-     local solve_completed = true
  
      -- define handler function here so it'll work w/o gui
--- 2944,2947 ----
***************
*** 2875,2884 ****
      progressDialog:Destroy()
  
!     if s then
!         sudokuGUI.sudokuSolnTable = TableCopy(s)
!         s = sudoku.GeneratePuzzleDifficulty(sudokuGUI.difficulty, s)
          sudokuGUI.sudokuTables_pos = 1
          sudokuGUI.sudokuTables = {}
!         table.insert(sudokuGUI.sudokuTables, s)
          sudokuGUI.UpdateTable() -- resets possible and refreshes too
      end
--- 2962,2999 ----
      progressDialog:Destroy()
  
!     if not s then return end
! 
!     local solve_progress = 0
!     local start_time = os.time()
!     local solve_completed = true
! 
!     local progressDialog = wx.wxProgressDialog("wxLuaSudoku - Ensuring Uniqueness...",
!                            string.format("%s\nIteration # %d, current cell %d            ", sudokuGUI.sayings[1], 0, 0),
!                            100,
!                            sudokuGUI.frame,
!                            wx.wxPD_AUTO_HIDE+wx.wxPD_CAN_ABORT+wx.wxPD_ELAPSED_TIME)
! 
!     local idx = 1
! 
!     -- define handler function here so it'll work w/o gui
!     function sudoku.GeneratePuzzleDifficultyHook(count, i, cell)
!         if solve_completed == false then return false end -- canceled
!         if math.floor((os.time()-start_time)/2) > 4 then
!             idx = idx + 1
!         end
!         if idx > sudokuGUI.sayings_n then idx = sudokuGUI.sayings_n end
!         local msg = string.format("%s\nIteration # %d, current cell %d            ", sudokuGUI.sayings[idx], count, cell)
!         solve_completed = progressDialog:Update(i, msg)
!         return solve_completed
!     end
! 
!     sudokuGUI.sudokuSolnTable = TableCopy(s)
!     local s1 = sudoku.GeneratePuzzleDifficulty(sudokuGUI.difficulty, TableCopy(s))
!     progressDialog:Destroy()
! 
!     if s1 then
          sudokuGUI.sudokuTables_pos = 1
          sudokuGUI.sudokuTables = {}
!         table.insert(sudokuGUI.sudokuTables, s1)
          sudokuGUI.UpdateTable() -- resets possible and refreshes too
      end
***************
*** 3151,3159 ****
      -- "cheat" a little by using SolveScan to get easy to find values
      local flags = TableCopy(s.flags)
!     for n = sudoku.ELIMINATE_FLAG_MIN, sudoku.ELIMINATE_FLAG_MAX do
!         s.flags[n] = true
!     end
  
!     local s, count, changed_cells = sudoku.SolveScan(s)
      local s, g = sudoku.SolveBruteForce(s)
  
--- 3266,3274 ----
      -- "cheat" a little by using SolveScan to get easy to find values
      local flags = TableCopy(s.flags)
!     --for n = sudoku.ELIMINATE_FLAG_MIN, sudoku.ELIMINATE_FLAG_MAX do
!     --    s.flags[n] = true
!     --end
  
!     --local s, count, changed_cells = sudoku.SolveScan(s)
      local s, g = sudoku.SolveBruteForce(s)