Sudoku Code [was: python code I'm trying to copy over to LC]

Want to move your code and projects to LiveCode but don't know where to start?

Moderators: FourthWorld, heatherlaine, Klaus, robinmiller

Opaquer
Posts: 247
Joined: Wed Aug 14, 2013 8:24 am

Sudoku Code [was: python code I'm trying to copy over to LC]

Post by Opaquer » Tue Feb 04, 2020 6:19 pm

Hey guys

So, I'm still working on my Sudoku app and still having some issues, though it's making slow but steady progress!

I'm now trying to get to one of the last stages - solving sudokus. I've found SO MANY places online that talk about it in different languages, but none for LC :(

I tried to code it myself and it's just not working for some silly reason, so I found one that's coded in Python that looks like it works and everything, but I can't quite figure out how to convert it over to LC (I keep getting a recursion error when I try :( )

The code in Python is as follows:

Code: Select all

#A function to check if the grid is full
def checkGrid(grid):
  for row in range(0,9):
      for col in range(0,9):
        if grid[row][col]==0:
          return False

  #We have a complete grid!  
  return True 

#A backtracking/recursive function to check all possible combinations of numbers until a solution is found
def solveGrid(grid):
  #Find next empty cell
  for i in range(0,81):
    row=i//9
    col=i%9
    if grid[row][col]==0:
      for value in range (1,10):
        #Check that this value has not already be used on this row
        if not(value in grid[row]):
          #Check that this value has not already be used on this column
          if not value in (grid[0][col],grid[1][col],grid[2][col],grid[3][col],grid[4][col],grid[5][col],grid[6][col],grid[7][col],grid[8][col]):
            #Identify which of the 9 squares we are working on
            square=[]
            if row<3:
              if col<3:
                square=[grid[i][0:3] for i in range(0,3)]
              elif col<6:
                square=[grid[i][3:6] for i in range(0,3)]
              else:  
                square=[grid[i][6:9] for i in range(0,3)]
            elif row<6:
              if col<3:
                square=[grid[i][0:3] for i in range(3,6)]
              elif col<6:
                square=[grid[i][3:6] for i in range(3,6)]
              else:  
                square=[grid[i][6:9] for i in range(3,6)]
            else:
              if col<3:
                square=[grid[i][0:3] for i in range(6,9)]
              elif col<6:
                square=[grid[i][3:6] for i in range(6,9)]
              else:  
                square=[grid[i][6:9] for i in range(6,9)]
            #Check that this value has not already be used on this 3x3 square
            if not value in (square[0] + square[1] + square[2]):
              grid[row][col]=value
              myPen.clear()
              drawGrid(grid) 
              myPen.getscreen().update()            
              if checkGrid(grid):
                print("Grid Complete and Checked")
                return True
              else:
                if solveGrid(grid):
                  return True
      break
  print("Backtrack")
  grid[row][col]=0  

I have some of it working, but for some reason there's an issue with the repeat. I keep getting a recursive error when I run it :P

For reference, this is the code I have at the moment (ignore how bad it is, it's 3AM for me at the moment and I can't even think clearly right now :P ), In my code, the CellTracker variable is used to keep track of the cells of the sudoku, while the TestCellTracker is used to keep track of the possible solution.

Code: Select all

global CellTracker
global TestCellTracker
global Solved

on mouseUp
   put 0 into Solved
   put CellTracker into TestCellTracker
   SolveGrid
   answer "DONE"
end mouseUp

on SolveGrid
   repeat with i=1 to 81
      put (trunc(i/9)+1) into Row
      put i mod 9 into Col
      if Col=0 then
         put 9 into Col
      end if
      put "R"&Row&"C"&Col into Cell
      
      if TestCellTracker[Cell]["Normal"]=0 then
         put WorkOutValues(Row,Col) into Values
         repeat with m=1 to 9
            if Values[m]=0 then
               put m into TestCellTracker[Cell]["Normal"]
               exit repeat
            end if
         end repeat
         if CheckGrid=True then
            put 1 into Solved
            exit repeat
         else
            SolveGrid
         end if
      end if
      if Solved=0 then
         put 0 into TestCellTracker[Cell]["Normal"]
      end if
   end repeat
end SolveGrid

function CheckGrid
   repeat with i=1 to 9
      repeat with j=1 to 9
         if TestCellTracker["R"&i&"C"&j]["Normal"] = 0 then
            return false
         else
            return true
         end if
      end repeat
   end repeat
end CheckGrid

function WorkOutValues i, j
   repeat with m=i to 9
      put 0 into ValueCheck[m]
   end repeat
   repeat with m=1 to 9
      if TestCellTracker["R"&i&"C"&m]["Normal"]<>0 then
         put TestCellTracker["R"&i&"C"&m]["Normal"] into ValueCheck[TestCellTracker["R"&i&"C"&m]["Normal"]]
      end if
      if TestCellTracker["R"&m&"C"&j]["Normal"]<>0 then
         put TestCellTracker["R"&m&"C"&j]["Normal"] into ValueCheck[TestCellTracker["R"&m&"C"&j]["Normal"]]
      end if
   end repeat   
   if i<=3 then
      put 3 into MaxRow
      if j<=3 then
         put 3 into MaxCol
      else if j<=6 then
         put 6 into MaxCol
      else
         put 9 into MaxCol
      end if
   else if i<=6 then
      put 6 into MaxRow
      if j<=3 then
         put 3 into MaxCol
      else if j<=6 then
         put 6 into MaxCol
      else
         put 9 into MaxCol
      end if
   else
      put 9 into MaxRow
      if j<=3 then
         put 3 into MaxCol
      else if j<=6 then
         put 6 into MaxCol
      else
         put 9 into MaxCol
      end if
   end if
   repeat with m=MaxRow-2 to MaxRow
      repeat with n=MaxCol-2 to MaxCol
         if TestCellTracker["R"&m&"C"&n]["Normal"]<>0 then
            put TestCellTracker["R"&m&"C"&n]["Normal"] into ValueCheck[TestCellTracker["R"&m&"C"&n]["Normal"]]
         end if
      end repeat
   end repeat
   --   if sum(ValueCheck)=45 then
   --      return 0
   --   else
   return ValueCheck
   --end if
end WorkOutValues
I know I've done things slightly differently, but surely that's not the reason for the failure, is it? Any help would be appreciated :)

Many thanks!
Last edited by Opaquer on Tue Feb 18, 2020 12:35 pm, edited 1 time in total.

capellan
Posts: 654
Joined: Wed Aug 15, 2007 11:09 pm

Re: Python code I'm trying to copy over to LC

Post by capellan » Wed Feb 05, 2020 1:32 am

Just for reference: Jim Hurley wrote a Sudoku application using LiveCode
http://jamesphurley.com/Sudoku.htm
Screen Shot 2020-02-04 at 8.49.17 PM.png

Opaquer
Posts: 247
Joined: Wed Aug 14, 2013 8:24 am

Re: Python code I'm trying to copy over to LC

Post by Opaquer » Wed Feb 05, 2020 4:20 am

Hey Capellan

Thanks for showing me that - I didn't know it existed! I've not had a chance to look at it on my computer yet, but on the website I couldn't see anything relating to it being able to completely solve a sudoku? Can it?

RogGuay
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 114
Joined: Fri Apr 28, 2006 12:10 am
Location: Seattle

Re: Python code I'm trying to copy over to LC

Post by RogGuay » Wed Feb 05, 2020 4:17 pm

I just upgraded an old Sudoku stack that I made back in the day. It's called SudokuMatic and it's available in Sample Stacks.

Roger

Opaquer
Posts: 247
Joined: Wed Aug 14, 2013 8:24 am

Re: Python code I'm trying to copy over to LC

Post by Opaquer » Thu Feb 06, 2020 9:05 am

Hi RogGuay

I had a look at your app, and while it's great for generating Sudoku's (which I still need to implement, so will definitely come back to it), I couldn't see anywhere in it that lets you solve a given Sudoku? Am I missing something in it?

RogGuay
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 114
Joined: Fri Apr 28, 2006 12:10 am
Location: Seattle

Re: Python code I'm trying to copy over to LC

Post by RogGuay » Fri Feb 07, 2020 4:39 pm

Sorry, but SudokuMatic cannot solve a given Sudoku puzzle. Interesting challenge, though. Does the Python code example do that? Good luck and keep me posted, if you will.

Roger

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

Re: Python code I'm trying to copy over to LC

Post by [-hh] » Fri Feb 07, 2020 7:18 pm

capellan wrote:Just for reference: Jim Hurley wrote a Sudoku application using LiveCode
http://jamesphurley.com/Sudoku.htm
Opaquer wrote:... but on the website I couldn't see anything relating to it being able to completely solve a sudoku? Can it?
It is a fine exercise/learning step to implement one of the many solution tools from other languages in LiveCode.

But when doing that you shouldn't belittle solutions that others have since years:
The page of Alejandro's link above writes explicitly about that, impossible to overlook.
And the stacks in the downloadable apps are not protected, you can read the scripts!
shiftLock happens

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

Re: Python code I'm trying to copy over to LC

Post by [-hh] » Fri Feb 07, 2020 9:25 pm

Here is for your comparisons a complete "brute-force-solver" for 9x9 sudokus (=the method you tried to code from python) in 65 lines, the essential solver in 25 lines.

It is implemented into LC based on https://samirhodzic.github.io/sudoku-solver-js/ (which is more than 100 times faster than Livecode).

The input is a 9x9-puzzle in the form (81 chars):

Code: Select all

local p0="062100950908035006040029170250000084400502600890463205020357000070006502685004731"
where "0" stands for an empty cell.

The solution is in the same form (a 81 chars string), e.g. for the above (in 11 ms):

Code: Select all

762148953918735426543629178256971384431582697897463215124357869379816542685294731
Watch the timing (which I got from my tests on a 2.5 GHz machine).

Code: Select all

local puzzle
local p0="062100950908035006040029170250000084400502600890463205020357000070006502685004731"
local p1="806047003901083547300900600680090300012376084009800706290760031003502060108400270"
local p2="007300405000020900253064870090740360000030080836209047100802603600000018082610004"
local p3="032054900090001004080700031005600027800070000270140005000210300018907652603000000"
local p4="010000300000300051308146009900000000280050704000602900600400000000003107107805090"
local p5="005200000400300700600000010800020100040800500000095000083040070090006080500902000"

on mouseUp
  put the millisecs into m1; set cursor to watch
  put p1 into tP; put "beginner" into tLevel -- 28 ms
  put p2 into tP; put "easy" into tLevel -- 13 ms
  put p3 into tP; put "normal" into tLevel -- 39 ms
  -- put p4 into tP; put "hard" into tLevel -- 2153 ms
  -- put p5 into tP ; put "evil" into tLevel -- 70227 ms
  put empty into puzzle
  repeat with j=1 to 81
    put char j of tP into puzzle[j-1]
  end repeat
  if get_candidate(0) then
    put empty into s0
    repeat with j=0 to 80
      put puzzle[j] after s0
    end repeat
    put s0 into fld "OUT"
  else return "No solution found"
  put tLevel & ": " &the millisecs-m1 & " ms" into fld "timing"
end mouseUp

-- Check if the number is a legal candidate for the given cell (by Sudoku rules).
function check_candidate n, row, col
  repeat with i=0 to 8
    put 9*(3*(row div 3) + (i div 3)) + 3*(col div 3) + i mod 3 into tI
    if n is among the items of ( puzzle[row * 9 + i], \
          puzzle[col + i * 9], puzzle[tI] )
    then return false
  end repeat
  return true
end check_candidate

-- Recursively test all possible numbers for a given cell until the puzzle is solved.
function get_candidate index
  if index >= 81 then return true
  else if puzzle[index] <> 0 then
    return get_candidate(index + 1)
  end if
  repeat with i=1 to 9 
    if check_candidate(i, index div 9, index mod 9) then
      put i into puzzle[index]
      if get_candidate(index + 1) then return true
    end if
  end repeat
  put 0 into puzzle[index]
  return false
end get_candidate
shiftLock happens

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9580
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Python code I'm trying to copy over to LC

Post by dunbarx » Fri Feb 07, 2020 11:38 pm

Hermann.

I knew something like this would come from you.

Craig

Opaquer
Posts: 247
Joined: Wed Aug 14, 2013 8:24 am

Re: Python code I'm trying to copy over to LC

Post by Opaquer » Sat Feb 08, 2020 3:49 am

Hey guys, thanks for all the replies and solutions to the problem. Sorry for not seeing everything - I'm currently on holidays and only get a chance to get on my laptop for an hour or so every other day or two, and sometimes getting caught up in the holiday makes me miss things on websites and such until I get a chance to check it out myself :-P

As for your solution Hermann, that looks so elegant and simple! I may have to try it out when I get a chance next - it definitely looks very promising and should speed up things quite a bit! Thank you so much!

Thierry
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 875
Joined: Wed Nov 22, 2006 3:42 pm

Re: Python code I'm trying to copy over to LC

Post by Thierry » Mon Feb 10, 2020 6:37 pm

Hi,

Had some fun helping Opaquer with his Python's code.

Then Hermann post his nice and elegant piece of code...

After that, I've spent a couple of hours trying to optimize a bit but
not changing the algorithm (formula) of the solver.

Here are the results so far; details will come later...


sudoku r1.png
sudoku r2.png
!
SUNNY-TDZ.COM doesn't belong to me since 2021.
To contact me, use the Private messages. Merci.
!

Thierry
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 875
Joined: Wed Nov 22, 2006 3:42 pm

Re: Python code I'm trying to copy over to LC

Post by Thierry » Tue Feb 11, 2020 3:44 am

and the code B- in the results from previous post.
This is a variant of Hermann's code posted before in this thread.


sudokuB.png

Thierry
!
SUNNY-TDZ.COM doesn't belong to me since 2021.
To contact me, use the Private messages. Merci.
!

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

Re: Python code I'm trying to copy over to LC

Post by [-hh] » Tue Feb 11, 2020 3:29 pm

Thierry, this is a really fine optimization you have worked out for that.

On the other hand, the dancing links algorithm X (DLX) by D. Knuth is known to be very fast for solving even difficult puzzles. Find enclosed a stack that does a JS implementation of that algorithm in JavaScript (via a browser widget), credits: https://hewgill.com/sudoku/ .

This needs here, incl. the transport of data to and from the browser widget, for each and every of the current puzzle examples less than 20 ms, from beginner to evil!!

Could be interesting to translate that (or a python or a C++ implementation of this algorithm) to LiveCode.
[I'm not interested, I prefer to solve sudokus manually ;-)].
Attachments
sudoku.livecode.zip
Solver: JS implementation of DLX.
(4.96 KiB) Downloaded 358 times
shiftLock happens

Thierry
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 875
Joined: Wed Nov 22, 2006 3:42 pm

Re: Python code I'm trying to copy over to LC

Post by Thierry » Tue Feb 11, 2020 3:42 pm

[-hh] wrote: Thierry, this is a really fine optimization you have worked out for that.
Thank you Hermann,
On the other hand, the dancing links algorithm X (DLX) by D. Knuth is well known to be very fast for solving even difficult puzzels. Find enclosed a stack that does a JS implementation of that algorithm in JavaScript (via a browser widget), credits: https://hewgill.com/sudoku/ .

This needs here, incl. the transport of data to and from the browser widget, for each and every of the current puzzle examples less than 20 ms, from beginner to evil!!
Thanks, and yes I'm aware of this one too :)
But my job here was to help Opaquer to translate his python's code; not much really.
Could be interesting to translate that (or a python or a C++ implementation of this algorithm) to LiveCode.
[I'm not interested, I prefer to solve sudokus manually ;-)].
Sure, it could be.
And I'm with you on this one as from time to time,
I'm playing with sudokus on my iPad near an open fire.... :)

Oh, there is another technic which seems to be even more interesting,
but I bet we need you for a better understanding :wink:

It's called: the Chaos within Sudoku
You can find all the information here: https://arxiv.org/pdf/1208.0370v1.pdf

Edit: I've checked your stack, and it's really excellent !


Cheers,

Thierry
!
SUNNY-TDZ.COM doesn't belong to me since 2021.
To contact me, use the Private messages. Merci.
!

Opaquer
Posts: 247
Joined: Wed Aug 14, 2013 8:24 am

Re: Python code I'm trying to copy over to LC

Post by Opaquer » Wed Feb 12, 2020 3:04 am

Hey guys

Thanks for both your inputs - and thanks Hermann for the way to do DLX in LC - I was actually researching it and was trying to figure out how to get DLX working in LC when your post came up! I want to try and convert it to LC, which will be my next step, but for some reason when I tried your stack it doesn't work for me - it's probably something simple, but I've never used a browser widget before and never seen this before :P

All I've done is downloaded the stack and opened it in LC, though I'm on Windows if that makes a difference?

Also as a side note, I also like solving Sudokus manually - and this app will help! Eventually I'll be able to generate sudokus procedurally, and having a way to solve them quickly will make it easier when it comes to making sure it's valid and everything :). Along with some features of course :)

EDIT: Don't worry guys, I figured it out! That is an impressively fast Sudoku Solver! I'm definitely going to have to try convert this to LC and see how it compares, but I think this is the next step to making the perfect app!
Attachments
Browser error.png
Browser error.png (10.95 KiB) Viewed 11946 times

Post Reply

Return to “Converting to LiveCode”