It is currently Fri May 24, 2013 11:34 pm

All times are UTC




Post new topic Reply to topic  [ 22 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Programming Challenge
PostPosted: Fri Jul 06, 2012 5:41 pm 
Offline
UB Admin
User avatar

Joined: Tue Feb 17, 2004 10:15 pm
Location: Conjunction Junction
A recent article about Sudoku inspired me to write a puzzle solver. I know there are existing programs but I wanted to see how easily I could manage one from scratch. It turned out to be a bit more nuanced than I originally expected and it ended up being a lot of fun.

http://www.metro.co.uk/weird/903532-mathematician-arto-inkala-creates-worlds-hardest-sudoku-everest

The challenge.
1) Use only your code. No reusing code from other Sudoku solvers.
2) Use any language you like.
3) It should be able to solve ANY Sudoku puzzle but the benchmark will be the one in the link above.
4) Measure your execution time in milliseconds

http://www.sudoku.name/rules/en

My current execution time is 6264 milliseconds. I'll post my source around the end of the month.


Top
 Profile  
 
PostPosted: Mon Jul 09, 2012 3:31 am 
Offline
User avatar

Joined: Wed Dec 14, 2005 6:15 pm
Location: Lisbon, Portugal
This was my AI class project. We coded it in lisp. It honestly wasn't too hard. I'll post time later.


Top
 Profile  
 
PostPosted: Thu Jul 12, 2012 5:37 am 
Offline
UB Admin
User avatar

Joined: Thu Feb 05, 2004 1:42 am
Location: San Antonio
How do you take input?


Top
 Profile  
 
PostPosted: Thu Jul 12, 2012 11:10 am 
Offline
UB Admin
User avatar

Joined: Tue Feb 17, 2004 10:15 pm
Location: Conjunction Junction
You can do it however you like. I use a grid of buttons that accept a keypress when they have focus. If you wanted to load the puzzle from a file that's fine too.


Top
 Profile  
 
PostPosted: Fri Jul 13, 2012 6:24 am 
Offline
UB Admin
User avatar

Joined: Thu Feb 05, 2004 1:42 am
Location: San Antonio
File io it is.


Top
 Profile  
 
PostPosted: Fri Jul 13, 2012 7:45 am 
Offline
UB Admin
User avatar

Joined: Thu Feb 05, 2004 1:42 am
Location: San Antonio
Did you look up any ideas on how to tackle this? I haven't started yet, but I have a feeling this is going to be complicated. Just want to know if that would be cheating.

PS. I feel like doing recursion.


Top
 Profile  
 
PostPosted: Fri Jul 13, 2012 12:51 pm 
Offline
UB Admin
User avatar

Joined: Tue Feb 17, 2004 10:15 pm
Location: Conjunction Junction
I did not look up any ideas. I'd recommend trying to figure out your own method.


Top
 Profile  
 
PostPosted: Tue Jul 17, 2012 10:01 pm 
Offline
User avatar

Joined: Thu Feb 05, 2004 12:18 am
Location: glitch lies he's from Lisboa, Portugal Posts: more than glitch
has MiniWookie out-programmed you yet? The day is coming...


Top
 Profile  
 
PostPosted: Wed Jul 18, 2012 4:30 pm 
Offline
UB Admin
User avatar

Joined: Tue Feb 17, 2004 10:15 pm
Location: Conjunction Junction
He's getting there. Already knows how to use the DVR better than I do.


Top
 Profile  
 
PostPosted: Thu Jul 19, 2012 4:19 am 
Offline
UB Admin
User avatar

Joined: Thu Feb 05, 2004 1:42 am
Location: San Antonio
I'm working on it now... I've had a lot going on these last few days so progress has been slow. But I will say getting the basics down was quite easy.


Top
 Profile  
 
PostPosted: Sat Jul 21, 2012 1:57 pm 
Offline
UB Admin
User avatar

Joined: Tue Feb 17, 2004 10:15 pm
Location: Conjunction Junction
http://www.youtube.com/watch?v=mJtoVXXcArQ&feature=plcp
4159 ms


Top
 Profile  
 
PostPosted: Sun Jul 22, 2012 10:33 am 
Offline
User avatar

Joined: Sat Feb 07, 2004 6:47 am
I spent 30 minutes coding up a solution.

It runs instantly but doesn't find all the answers..

http://pastebin.com/BBauCpy5

I stored all 1,2,3,4,5,6,7,8,9 against each grid point as a possible answer for that grid point. If any of these numbers comes up as the answer for a "neighbour" gridpoint, then I remove it as a possible answer from this gridpoint.

I also look at all numbers that are a possible answer of a neighbouring gridpoint, and the gridpoint has a possible answer that isn't possible in it's neighbours, then I set that possible answer as the answer.

I must need to add some additional logic to get the solution.

edit: it would be easier if I used branch and bound by "guessing" possible gridpoint numbers (ones that have high probability of being right) and then using recursion + dynamic programming.

However I wanted to solve it the way a human would solve it.


Top
 Profile  
 
PostPosted: Sun Jul 22, 2012 3:58 pm 
Offline
UB Admin
User avatar

Joined: Thu Feb 05, 2004 1:42 am
Location: San Antonio
I think there are some puzzles that require guessing and then retracing if you are wrong. I might be wrong though.

In other news, I don't like dealing with arrays/lists in python.


Top
 Profile  
 
PostPosted: Mon Jul 23, 2012 6:56 pm 
Offline
User avatar

Joined: Thu Feb 05, 2004 12:18 am
Location: glitch lies he's from Lisboa, Portugal Posts: more than glitch
You guys might want to learn to play Sudoku first. I don't know everything you've done but you can't just look at neighboring spaces. you have to think about it not repeating across a left to right line or an up to down line.


Top
 Profile  
 
PostPosted: Mon Jul 23, 2012 8:26 pm 
Offline
UB Admin
User avatar

Joined: Thu Feb 05, 2004 1:42 am
Location: San Antonio
MiniEye, you clearly do not understand the delicate intricacies of New Zealand style Sudoku.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 22 posts ]  Go to page 1, 2  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group