Jump to content

Fast Sudoku solver (insane) in pure SQL[ite]

jchd

By jchd
in AutoIt Example Scripts

 Share

Recommended Posts

argumentum Universalist

argumentum

Posted
Posted (edited)
  On 1/6/2018 at 1:02 AM, farouk12 said:

that sad because its take less then 5 sec with backtracking algorithm built in autoit

Expand  

well, it takes forever ( 307 sec. ) to solve "Hardest" from the OP =/

PS: tweaked your code to speed up the process ( you had too many GUI updates )

  Reveal hidden contents

tho, it would be nice to integrate the @jchd sqlite way to your GUI :)  

PS2: below is the results of the sqlite output ( and the code )

  Reveal hidden contents
  Reveal hidden contents

 

Edited by argumentum
show the code, v2

Follow the link to my code contribution ( and other things too ).
FAQ - Please Read Before Posting.
autoit_scripter_blue_userbar.png

farouk12 Seeker

farouk12

Posted
Posted (edited)
  On 1/6/2018 at 6:12 AM, argumentum said:

well, it takes forever ( 307 sec. ) to solve "Hardest" from the OP =/

PS: tweaked your code to speed up the process ( you had too many GUI updates )

tho, it would be nice to integrate the @jchd sqlite way to your GUI :)  

Expand  

Well its not mine i got it from topic here (I dont know the link / Author).

 

And thanks for the edit, now its good as example.

I found out that back tracking is more effective in some situations, rather than the sql way.(Big deference)

Edited by farouk12
argumentum Universalist

argumentum

Posted
Posted

and since I can not let go of my obsessive nature, here is a broader comparison of the two systems, from an AutoIt execution time viewpoint :
Edzard Pasma's 

From TOP 95: # 1 took 0.022 sec. to solve
From TOP 95: # 2 took 0.061 sec. to solve
From TOP 95: # 3 took 0.054 sec. to solve
From TOP 95: # 4 took 2.86 sec. to solve
From TOP 95: # 5 took 1.936 sec. to solve
From TOP 95: # 6 took 8.716 sec. to solve
From TOP 95: # 7 took 2.705 sec. to solve
From TOP 95: # 8 took 0.72 sec. to solve
From TOP 95: # 9 took 2.106 sec. to solve
From TOP 95: # 10 took 4.136 sec. to solve
From TOP 95: # 11 took 0.547 sec. to solve
From TOP 95: # 12 took 0.123 sec. to solve
From TOP 95: # 13 took 0.166 sec. to solve
From TOP 95: # 14 took 1.009 sec. to solve
From TOP 95: # 15 took 0.161 sec. to solve
From TOP 95: # 16 took 0.536 sec. to solve
From TOP 95: # 17 took 0.038 sec. to solve
From TOP 95: # 18 took 1.947 sec. to solve
From TOP 95: # 19 took 0.031 sec. to solve
From TOP 95: # 20 took 0.017 sec. to solve
From TOP 95: # 21 took 4.631 sec. to solve
From TOP 95: # 22 took 0.048 sec. to solve
From TOP 95: # 23 took 0.09 sec. to solve
From TOP 95: # 24 took 0.099 sec. to solve
From TOP 95: # 25 took 0.142 sec. to solve
From TOP 95: # 26 took 0.287 sec. to solve
From TOP 95: # 27 took 0.217 sec. to solve
From TOP 95: # 28 took 5.642 sec. to solve
From TOP 95: # 29 took 0.03 sec. to solve
From TOP 95: # 30 took 0.202 sec. to solve
From TOP 95: # 31 took 0.044 sec. to solve
From TOP 95: # 32 took 0.021 sec. to solve
From TOP 95: # 33 took 0.013 sec. to solve
From TOP 95: # 34 took 3.036 sec. to solve
From TOP 95: # 35 took 0.266 sec. to solve
From TOP 95: # 36 took 0.061 sec. to solve
From TOP 95: # 37 took 0.113 sec. to solve
From TOP 95: # 38 took 0.01 sec. to solve
From TOP 95: # 39 took 0.352 sec. to solve
From TOP 95: # 40 took 0.027 sec. to solve
From TOP 95: # 41 took 4.337 sec. to solve
From TOP 95: # 42 took 0.42 sec. to solve
From TOP 95: # 43 took 0.222 sec. to solve
From TOP 95: # 44 took 0.099 sec. to solve
From TOP 95: # 45 took 0.073 sec. to solve
From TOP 95: # 46 took 3.182 sec. to solve
From TOP 95: # 47 took 0.217 sec. to solve
From TOP 95: # 48 took 0.059 sec. to solve
From TOP 95: # 49 took 0.221 sec. to solve
From TOP 95: # 50 took 0.422 sec. to solve
From TOP 95: # 51 took 0.014 sec. to solve
From TOP 95: # 52 took 0.104 sec. to solve
From TOP 95: # 53 took 0.095 sec. to solve
From TOP 95: # 54 took 0.013 sec. to solve
From TOP 95: # 55 took 0.061 sec. to solve
From TOP 95: # 56 took 0.021 sec. to solve
From TOP 95: # 57 took 0.315 sec. to solve
From TOP 95: # 58 took 0.063 sec. to solve
From TOP 95: # 59 took 0.051 sec. to solve
From TOP 95: # 60 took 0.013 sec. to solve
From TOP 95: # 61 took 0.187 sec. to solve
From TOP 95: # 62 took 0.07 sec. to solve
From TOP 95: # 63 took 0.056 sec. to solve
From TOP 95: # 64 took 0.252 sec. to solve
From TOP 95: # 65 took 0.006 sec. to solve
From TOP 95: # 66 took 0.222 sec. to solve
From TOP 95: # 67 took 0.193 sec. to solve
From TOP 95: # 68 took 0.164 sec. to solve
From TOP 95: # 69 took 0.056 sec. to solve
From TOP 95: # 70 took 0.069 sec. to solve
From TOP 95: # 71 took 2.819 sec. to solve
From TOP 95: # 72 took 0.024 sec. to solve
From TOP 95: # 73 took 0.044 sec. to solve
From TOP 95: # 74 took 0.174 sec. to solve
From TOP 95: # 75 took 0.043 sec. to solve
From TOP 95: # 76 took 0.242 sec. to solve
From TOP 95: # 77 took 0.079 sec. to solve
From TOP 95: # 78 took 0.036 sec. to solve
From TOP 95: # 79 took 0.25 sec. to solve
From TOP 95: # 80 took 0.027 sec. to solve
From TOP 95: # 81 took 0.086 sec. to solve
From TOP 95: # 82 took 0.04 sec. to solve
From TOP 95: # 83 took 0.201 sec. to solve
From TOP 95: # 84 took 0.054 sec. to solve
From TOP 95: # 85 took 0.015 sec. to solve
From TOP 95: # 86 took 0.021 sec. to solve
From TOP 95: # 87 took 0.11 sec. to solve
From TOP 95: # 88 took 0.009 sec. to solve
From TOP 95: # 89 took 0.135 sec. to solve
From TOP 95: # 90 took 0.077 sec. to solve
From TOP 95: # 91 took 0.02 sec. to solve
From TOP 95: # 92 took 0.011 sec. to solve
From TOP 95: # 93 took 0.035 sec. to solve
From TOP 95: # 94 took 0.015 sec. to solve
From TOP 95: # 95 took 0.189 sec. to solve
  Reveal hidden contents

and that is a hell of a lot faster than the backtracking algorithm

  Reveal hidden contents

then again, one runs in AutoIt and the other in sqlite. So is not Apples to Apples.

Follow the link to my code contribution ( and other things too ).
FAQ - Please Read Before Posting.
autoit_scripter_blue_userbar.png

argumentum Universalist

argumentum

Posted
Posted (edited)
  On 1/5/2018 at 9:23 PM, Chimp said:

the puzzle included in the listing has only one solution

Expand  

".....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3.." ; 155 results in 10 sec.
"37...8........32..1......6..9.12.5....4...1....1.37.2..2......9..69........2...18" ; 17 results in 3 sec.

:) 

Edited by argumentum
added 1 more

Follow the link to my code contribution ( and other things too ).
FAQ - Please Read Before Posting.
autoit_scripter_blue_userbar.png

Gianni Universalist

Gianni

Posted
Posted
  On 1/6/2018 at 8:31 PM, argumentum said:

".....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3.." ; 155 results in 10 sec.
"37...8........32..1......6..9.12.5....4...1....1.37.2..2......9..69........2...18" ; 17 results in 3 sec.

:) 

Expand  

(?) what code are you using to get that output and those (wrong?) results?

 

image.jpeg.9f1a974c98e9f77d824b358729b089b0.jpeg Chimp

small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

argumentum Universalist

argumentum

Posted
Posted (edited)
  On 1/6/2018 at 9:11 PM, Chimp said:

what code are you using to get that output and those (wrong?) results?

Expand  

the code you used from sqlite site. The string of sudoku is a mod. of exiting strings.
Why so you find the strings to be wrong?
 

  Reveal hidden contents

 

Edited by argumentum
added the code

Follow the link to my code contribution ( and other things too ).
FAQ - Please Read Before Posting.
autoit_scripter_blue_userbar.png

Gianni Universalist

Gianni

Posted
Posted (edited)

... from my run I get this, 3 solutions for first puzzle and also 3 solutions for the second. What me (or you) are doing wrong? 

.....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..
162857493534129678789643521475312986913586742628794135356478219241935867897261354
251847693436925178789613524825371946914586732673294851362758419548139267197462385
251847693436925178789613524825371946914586732673294851392768415548139267167452389


37...8........32..1......6..9.12.5....4...1....1.37.2..2......9..69........2...18
372568491689413275145792863798124536234659187561837924427381659816975342953246718
372568491689413275145792863897124536234659187561837924428371659716985342953246718
372568491968413275145792863793124586284659137651837924427381659816975342539246718

 

Edited by Chimp

 

image.jpeg.9f1a974c98e9f77d824b358729b089b0.jpeg Chimp

small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

argumentum Universalist

argumentum

Posted
Posted (edited)
  On 1/6/2018 at 9:25 PM, Chimp said:

what me (or you) are doing wrong?

Expand  

no clue, I've added the code I'm using to my post above.
  

37...8........32..1......6..9.12.5....4...1....1.37.2..2......9..69........2...18
372568491689413275145792863798124536234659187561837924427381659816975342953246718
372568491689413275145792863897124536234659187561837924428371659716985342953246718
372568491968413275145792863793124586284659137651837924427381659816975342539246718
372618495568493271149752863793124586254869137681537924427381659816975342935246718
372618495568493271149752863793124586284569137651837924427381659816975342935246718
372618495648593271159742863793126584264859137581437926427381659816975342935264718
372618495658493271149752863793124586284569137561837924427381659816975342935246718
372618495685493271149752863798124536234569187561837924427381659816975342953246718
372618495685493271149752863897124536234569187561837924428371659716985342953246718
372618495689453271145792863798124536234569187561837924427381659816975342953246718
372618495689453271145792863897124536234569187561837924428371659716985342953246718
372618495968453271145792863793124586254869137681537924427381659816975342539246718
372618495968453271145792863793124586284569137651837924427381659816975342539246718
372658491689413275145792863798124536234569187561837924427381659816975342953246718
372658491689413275145792863897124536234569187561837924428371659716985342953246718
372658491968413275145792863793124586254869137681537924427381659816975342539246718
372658491968413275145792863793124586284569137651837924427381659816975342539246718

PS: added my array above
PS2: using _SQLite_LibVersion = 3.20.0

PS3: the ".....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3.." result is below:

  Reveal hidden contents

PS4: I just read your post below. 
this happens to the best of us ;) 

Edited by argumentum

Follow the link to my code contribution ( and other things too ).
FAQ - Please Read Before Posting.
autoit_scripter_blue_userbar.png

Gianni Universalist

Gianni

Posted
Posted

Sorry, but you're right!
doing some previous tests I modified and saved the query by inserting the clause "LIMIT 3;" at the end of the query, then I forgot about this change I had made and continued to use the modified query getting results limited to 3.
my fault! sorry.

P.S.....I'm getting old :(

 

image.jpeg.9f1a974c98e9f77d824b358729b089b0.jpeg Chimp

small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

Gianni Universalist

Gianni

Posted
Posted

it's probably because the first part of the query still looks for all the results spending all the needed time, and then the second part just picks up only the wanted results

 

image.jpeg.9f1a974c98e9f77d824b358729b089b0.jpeg Chimp

small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

jchd Universalist

jchd

Posted
  • Author
Posted

Yeah, the subquery flattener of the query planner/optimizer isn't always smart enough to perform such (advanced?) optimization, mainly because there are potential dark corners where a seemingly clever optimization falls flat on its nose in another seemingly similar use case.

Such remarks regularly pop up on the mailing list, but often enough, the proposed optimization made by people would work on their precise test case but have devastating effects on another large range of slightly different queries.

SQLite main use base (in terms of number of devices) is for low-end devices having limited computing power and/or memory. So contrary to Oracle or MySQL and other RDBMS where massaging a query ad nauseam to choose the absolute best plan is both possible and beneficial, SQLite can't devote as much code and complexity.

In case one of your queries takes longer than expected, try looking at what EXPLAIN QUERY PLAN <query> yields. The output often calls for a rewrite of the query and/or creation of a useful index. See http://www.sqlite.org/eqp.html

  Reveal hidden contents

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share
Go to topic listing

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...