Puzzles solved in under a second!

Programs which generate, solve, and analyze Sudoku puzzles

Puzzles solved in under a second!

Postby Guest » Fri Apr 22, 2005 10:10 pm

All, what's all this fuss about?

Took me 20 min to write a script that solves any puzzle.

Challenge me now ;)
Guest
 

Postby simes » Fri Apr 22, 2005 11:43 pm

All hail VB Guru <bow><scrape>

care to post a link to a downloadable version?

(and in VB too - what a masochist!)
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby Guest » Sat Apr 23, 2005 8:11 am

simes wrote:All hail VB Guru <bow><scrape>

care to post a link to a downloadable version?

(and in VB too - what a masochist!)


Later. Give it a try. Just a simple (very simple in this case) recursive algorithm doing all combinations. Pick an empty cell, put a digit, check the sudoku rules still hold, recurse into itself.
Guest
 

Postby Guest » Sat Apr 23, 2005 8:42 am

The iterative method is certainly a bit of a no-brainer, the interesting thing is using pattern recognition rather than T&E...
Guest
 

Postby Animator » Sat Apr 23, 2005 10:15 am

And it still takes you a second??
Animator
 
Posts: 469
Joined: 08 April 2005

Postby Guest » Sat Apr 23, 2005 10:42 am

Me? No! Mine is horrendously slow (around 40 seconds for a Very Hard). This is probably partly due to it being written in Excel VBA, but more relevantly my limited skills as a programmer :o(.

My ability and tools aside, several more capable folk using more suitable languages (Delphi, VB, Java, etc.) have produced programs that solve by pattern recognition alone, and in well under a second.

This is the only way a program can tell you whether or not a puzzle is solvable without T&E - which many utilities do, and more or less instantaneously (including Wayne's)
Guest
 

Postby Animator » Sat Apr 23, 2005 10:47 am

No, the one that started the topic :)
Animator
 
Posts: 469
Joined: 08 April 2005

Solving by logic alone

Postby tannedblondbloke » Sat Apr 23, 2005 1:50 pm

When I decided to write a solver, I deliberately wanted to it to solve problems using the rules I would try by hand rather than do an exhaustive search. (Although I haven't needed to yet, I wanted something that would think like me - only a lot faster! - to help if I got stuck on a particular problem. Also, I see a rule based solver as a more interesting challenge.) I might add in an exhaustive search option as a last resort at some point, once the other rules have been used.

I've managed to implement Milo rules 1 to 3, but nothing more esoteric yet such as X-wings. For problems which are soluble using these rules alone, solution time is typically well under a second. (Excel VBA).
tannedblondbloke
 
Posts: 16
Joined: 09 April 2005

Postby Guest » Sat Apr 23, 2005 8:14 pm

TBB - Thank you!!! I've been really annoyed by why my solver is so slow for ages, and had managed to shave a second off here and there, but had finally given up hope, thinking it was just that VBA was inefficient. Your post made me think again. I cut and pasted my macro into a new spreadsheet, unchanged, and it ran in less than a second. Microsoft, eh?
Guest
 

Postby tannedblondbloke » Sat Apr 23, 2005 8:51 pm

IJ wrote:Your post made me think again. I cut and pasted my macro into a new spreadsheet, unchanged, and it ran in less than a second. Microsoft, eh?


Indeed! Microsoft - the bane of my life in my day job!

To be fair I'm amazed at how efficient VBA is. I can run an algorithm on VBA , with all it's baggage of Windows and Excel, and it will still run many many times faster than my first museum piece computer (a Model 1 TRS80 from the late 70s!!)
tannedblondbloke
 
Posts: 16
Joined: 09 April 2005

Postby Guest » Mon Apr 25, 2005 8:30 pm

tannedblondbloke wrote:
To be fair I'm amazed at how efficient VBA is. I can run an algorithm on VBA , with all it's baggage of Windows and Excel, and it will still run many many times faster than my first museum piece computer (a Model 1 TRS80 from the late 70s!!)


Except that you are likely running now on a multi-scalar 2-3GHz machine with 512MB+ of RAM, and the old TRS-80's ran in the low MHz, with 4KB (thats K and not M) of RAM. So you've got 2.5-3 orders of magnitude more raw clock speed (never mind the parallel processing stuff), and 5 orders of magnitude more RAM.
Guest
 
Posts: 312
Joined: 25 November 2005

Postby Guest » Tue Apr 26, 2005 10:28 pm

Anonymous wrote:
tannedblondbloke wrote:
To be fair I'm amazed at how efficient VBA is. I can run an algorithm on VBA , with all it's baggage of Windows and Excel, and it will still run many many times faster than my first museum piece computer (a Model 1 TRS80 from the late 70s!!)


Except that you are likely running now on a multi-scalar 2-3GHz machine with 512MB+ of RAM, and the old TRS-80's ran in the low MHz, with 4KB (thats K and not M) of RAM. So you've got 2.5-3 orders of magnitude more raw clock speed (never mind the parallel processing stuff), and 5 orders of magnitude more RAM.


except that for this you dont need loads of RAM to solve sudoku ;)
Guest
 

Postby tannedblondbloke » Wed Apr 27, 2005 5:53 am

Anonymous wrote:Except that you are likely running now on a multi-scalar 2-3GHz machine with 512MB+ of RAM, and the old TRS-80's ran in the low MHz, with 4KB (thats K and not M) of RAM. So you've got 2.5-3 orders of magnitude more raw clock speed (never mind the parallel processing stuff), and 5 orders of magnitude more RAM.


Come on now. It was 16k. (Which I expanded to 48). 4k indeed! And about 1 to 2 MHz. Did I feel the bees knees.
tannedblondbloke
 
Posts: 16
Joined: 09 April 2005


Return to Software

cron