Post Reply 
[PC] Sudoku Solver
Author Message
ZiNgA BuRgA
Smart Alternative

Posts: 17,023.4213
Threads: 1,174
Joined: 19th Jan 2007
Reputation: -1.71391
E-Pigs: 446.0333
Offline
Post: #11
RE: [PC] Sudoku Solver
_VEndeTta Wrote:Did you use techniques like XY-Wings, Swordfishing, etc? Or just
nice data structures?
Dunno what they are - I just used some techniques that I use to solve Sudoku puzzle myself.  If you want, I can send you the VB6 source (I'm a messy coder).
I did use a 3x3x3x3 array though - first time I've ever used a 4 (and also 5) dimensional array :D  Not that it really helped or anything - it was just for fun I guess.

_VEndeTta Wrote:IMO I broke my CS professor's Soduko Solver in like two seconds. This
took me three tries before it would have looped forever (and you even
warned me about that in the app).
O_o, oh, like not entering enough data?  Haha, I see.  Basically it tries to solve it logically, after failing it will try "basic" guessing (brute force but to a limited depth) then finally asks the user if it will do a full brute force.

Thanks for the comments _VEndeTta!  You seem to be a very experienced programmer - do you tend to program many little apps?
(This post was last modified: 11/04/2007 11:49 PM by ZiNgA BuRgA.)
11/04/2007 11:47 PM
Visit this user's website Find all posts by this user Quote this message in a reply
_VEndeTta
Endless Night

Posts: 522.1732
Threads: 48
Joined: 9th Apr 2007
Reputation: -3.19624
E-Pigs: 4.8849
Offline
Post: #12
RE: [PC] Sudoku Solver
ZiNgA BuRgA Wrote:Dunno what they are - I just used some techniques that I use to solve Sudoku puzzle myself.  If you want, I can send you the VB6 source (I'm a messy coder).
I did use a 3x3x3x3 array though - first time I've ever used a 4 (and also 5) dimensional array :D  Not that it really helped or anything - it was just for fun I guess.

That might be even more impressive. XY-Wings and Swordfishing and Chain forcing
and many others are all defined logic techniques to solve Sudoku puzzles, most logic
solver programmers just use modular programming (who doesn't?) and will program a
class or method for each technique. You probably used some without even knowing.

Zinger Burger Wrote:O_o, oh, like not entering enough data?  Haha, I see.  Basically it tries to solve it logically, after failing it will try "basic" guessing (brute force but to a limited depth) then finally asks the user if it will do a full brute force.
:D
Not quite, I have several pet invalid puzzles that are very hard to catch that I like to
feed to Sudoku solvers, yours actually caught the first ones I tried, but didn't
recognize the more complex ones that involved multiple subsquares, though it still
warned me before falling into exponential time. Which is very nice and which means
you probably could recognize them if you added a bit more code. :yipi:

ZingaBurga Wrote:Thanks for the comments _VEndeTta!  You seem to be a very experienced programmer - do you tend to program many little apps?
Alas no.  No time. Though it looks like my internship will fall through this summer so I'll
finally be able to catch up on some coding. :clown:

I've been dying to try my hand at Emu, been brushing up on my Pentium 4 assembly
in anticipation. ;) If Daedelus doesn't get its head out of its butt, i was thinking of
learning ARM assembly (I think that's right) and pulling together a team of people who
know more than me to give a go at an N64 emulator.

As for the source. Lulz. I don't have any VB IDE, so as long as I can open it in
notepad or something, that'd be awesome, I could see what techniques you used,
etc. I did some in-depth research on Sudoku puzzles when I programmed one for a
Programming Competition, I was trying to make the brute-force algorithm more
effecient, in truth I wanted to get it to linear time, and succeeded only partially. My
method was about 3 times faster then pure brute-force, which doesn't mean poo poo in
exponential time D:.

Still, was fun. I lol'd at a 4 dimensional array, when I did it I used a 1D array of "Box"
objects, which took care of the other dimensions. But I wasn't trying to program
logic, so it worked. There is a way to set up your arrays to catch every logical error,
but it does take a while.

By the way, if you want to break your sudoku solver, enter these initial values :

(address:value)

1,A:1
2,H:6
3,E:6
5,B:6
9,C:6

[Image: 3c68ce3.jpg]
And when you gaze long into an abyss,
the abyss gazes also into you.
12/04/2007 06:19 AM
Find all posts by this user Quote this message in a reply
ZiNgA BuRgA
Smart Alternative

Posts: 17,023.4213
Threads: 1,174
Joined: 19th Jan 2007
Reputation: -1.71391
E-Pigs: 446.0333
Offline
Post: #13
RE: [PC] Sudoku Solver
_VEndeTta Wrote:I've been dying to try my hand at Emu, been brushing up on my Pentium 4 assembly
in anticipation. ;) If Daedelus doesn't get its head out of its butt, i was thinking of
learning ARM assembly (I think that's right) and pulling together a team of people who
know more than me to give a go at an N64 emulator.
Wow, I really have no idea how to code emulators - never really looked into ASM actually.
Good luck!  I'm sure tonnes of people would love you if you could get good improvements on the N64 emulator!

_VEndeTta Wrote:As for the source. Lulz. I don't have any VB IDE, so as long as I can open it in
notepad or something, that'd be awesome, I could see what techniques you used,
etc.
Yeah, text editors work.  The code's stored in frmMain.frm - just open that and search for
Quote:Private Sub Solve()
Anyways, the code's rather messy and probably could be optimized quite a bit - it was only written for fun and I didn't bother looking into making it fast (but the "algorithm order" should be about the same)

_VEndeTta Wrote:I did some in-depth research on Sudoku puzzles when I programmed one for a
Programming Competition
Oh, so that's how you know so much about Sudoku Solvers XD

_VEndeTta Wrote:I was trying to make the brute-force algorithm more
effecient, in truth I wanted to get it to linear time, and succeeded only partially. My
method was about 3 times faster then pure brute-force, which doesn't mean poo poo in
exponential time D:.
HOLY poo poo!  LINEAR TIME?  Wow, how did you manage to do that???
I don't think that's called "brute force" anymore if you could do that :P
wow.

_VEndeTta Wrote:By the way, if you want to break your sudoku solver, enter these initial values :

(address:value)

1,A:1
2,H:6
3,E:6
5,B:6
9,C:6
I actually found a few puzzles which couldn't be solved using normal methods.

Thanks for the reply.


Attached File(s)
.rar  SSsrc.rar (Size: 253.04 KB / Downloads: 677)
12/04/2007 06:38 AM
Visit this user's website Find all posts by this user Quote this message in a reply
_VEndeTta
Endless Night

Posts: 522.1732
Threads: 48
Joined: 9th Apr 2007
Reputation: -3.19624
E-Pigs: 4.8849
Offline
Post: #14
RE: [PC] Sudoku Solver
ZiNgA BuRgA Wrote:Wow, I really have no idea how to code emulators - never really looked into ASM actually.
Good luck!  I'm sure tonnes of people would love you if you could get good improvements on the N64 emulator!

<.<

Actually I just really want to play GoldenEye on my PSP. :P

Quote:HOLY poo poo!  LINEAR TIME?  Wow, how did you manage to do that???
I don't think that's called "brute force" anymore if you could do that :P
wow.

Lol. That's what I was trying for, but my method still came out in exponential time.
Just three times faster than the average brute-force method. :lmao:

I'd be so famous if I got the brute force method down to that.

Quote:I actually found a few puzzles which couldn't be solved using normal methods.

Thanks for the reply.
Yeah, that puzzle actually can't be solved at all, if you enter it you'll see that you've
put a 1 in the only place a 6 can go, which means brute force will try every single
sudoku puzzle before coming  back false ,and there are like 60 billion trillion of them. :suprised:

That's more than all the particles of matter in the universe. :unlove:

[Image: 3c68ce3.jpg]
And when you gaze long into an abyss,
the abyss gazes also into you.
12/04/2007 07:20 AM
Find all posts by this user Quote this message in a reply
ZiNgA BuRgA
Smart Alternative

Posts: 17,023.4213
Threads: 1,174
Joined: 19th Jan 2007
Reputation: -1.71391
E-Pigs: 446.0333
Offline
Post: #15
RE: [PC] Sudoku Solver
^^ Haha, hmm, it seems I misunderstood those values you gave me - I see what you mean now by stuffing up :S  The algorithm would pick up that a 6 can't go in that square, but the brute force part was coded to believe that the puzzle has at least one solution.  Hmm, never thought about that!


Lol, well, it's usually small things which encourage devs to work on large projects sometimes! (referring to the N64 emulator).
Though Golden Eye would probably be a fair way off though - good luck however!
12/04/2007 03:07 PM
Visit this user's website Find all posts by this user Quote this message in a reply
_VEndeTta
Endless Night

Posts: 522.1732
Threads: 48
Joined: 9th Apr 2007
Reputation: -3.19624
E-Pigs: 4.8849
Offline
Post: #16
RE: [PC] Sudoku Solver
Quote:Though Golden Eye would probably be a fair way off though - good luck however!

T.T So far off. Its so depressing. Even if I started right now it would take me months just to start. XO

I don't get it:

N64: 93.75 MHz
PSP: 333 MHz

Gimme a break. Over 3 times faster. T.T

They must be using C. Or maybe some component is giving
them problems. :/ Because I just don't get why this thing's
operating so slowly.

Meh. Anyways, its a pretty far off dream, wee'll see. Looking
at your programs has got me interested in coding again, so
there is hope.

^.^

Small hope.

[Image: 3c68ce3.jpg]
And when you gaze long into an abyss,
the abyss gazes also into you.
12/04/2007 05:20 PM
Find all posts by this user Quote this message in a reply
ZiNgA BuRgA
Smart Alternative

Posts: 17,023.4213
Threads: 1,174
Joined: 19th Jan 2007
Reputation: -1.71391
E-Pigs: 446.0333
Offline
Post: #17
RE: [PC] Sudoku Solver
Actually one thing I don't get is SNES on PC:

SNES ~3MHz
PC needs to be at least ~233MHz to emulate SNES at decent speed, and that's on ZSNES which is mainly coded in x86 ASM.
I remember a more "accurate" emulator, BSNES required a ~1.5GHz machine to run decent.  Dunno exactly what the difference is however.

Although MIPS isn't powerful as x86, I guess the PSP's graphics system makes up for it.  But emulation is still CPU intensive (needs to emulate graphic chips etc).

Hmm, so what work do you do By the way?
12/04/2007 05:24 PM
Visit this user's website Find all posts by this user Quote this message in a reply
_VEndeTta
Endless Night

Posts: 522.1732
Threads: 48
Joined: 9th Apr 2007
Reputation: -3.19624
E-Pigs: 4.8849
Offline
Post: #18
RE: [PC] Sudoku Solver
Wow. I didn't even know that. O.O

That's weird. I have heard that SNES is one of the most
difficult, arduous emulators to build, but I never knew it
was that bad. Hmmm. Could be that it just has soo many
components all of which have to be run simultaneously,
I bet you could program an emulator a lot better on a two
or four core processor.

Too bad Intel's a slut. <.<

Work as in "Paid Job for Money" kind of work? Nothing serious, mainly
I'm a "full-time" student on scholarship, CS/SE double major.

D:

But I make some on the side tutoring Discrete Math, its pretty decent pay,
16.60 an hr, for sitting on my butt doing nothing for three hours.

[Image: 3c68ce3.jpg]
And when you gaze long into an abyss,
the abyss gazes also into you.
(This post was last modified: 12/04/2007 05:45 PM by _VEndeTta.)
12/04/2007 05:40 PM
Find all posts by this user Quote this message in a reply
ZiNgA BuRgA
Smart Alternative

Posts: 17,023.4213
Threads: 1,174
Joined: 19th Jan 2007
Reputation: -1.71391
E-Pigs: 446.0333
Offline
Post: #19
RE: [PC] Sudoku Solver
_VEndeTta Wrote:I bet you could program an emulator a lot better on a two
or four core processor.
Yeah - apparently the PS2 emulator, PCSX2, runs way better on dual core CPUs.

_VEndeTta Wrote:Too bad Intel's a slut. <.<
O_o

_VEndeTta Wrote:Work as in "Paid Job for Money" kind of work? Nothing serious, mainly
I'm a "full-time" student on scholarship, CS/SE double major.
Cool!

_VEndeTta Wrote:But I make some on the side tutoring Discrete Math, its pretty decent pay,
16.60 an hr, for sitting on my butt doing nothing for three hours.
Haha, that's pretty sweet.  As for "lazy" jobs, I'm looking into teaching piano - piano teachers tend to get AU$40-50 per hour (I'll start off cheaper of course) and you don't really have to do much :P
12/04/2007 07:01 PM
Visit this user's website Find all posts by this user Quote this message in a reply
_VEndeTta
Endless Night

Posts: 522.1732
Threads: 48
Joined: 9th Apr 2007
Reputation: -3.19624
E-Pigs: 4.8849
Offline
Post: #20
RE: [PC] Sudoku Solver
ZiNgA BuRgA Wrote:
_VEndeTta Wrote:Too bad Intel's a slut. <.<
O_o
After much fruitless websurfing, I've found out that they're keeping the
Centrino ASM a secret, and nobody's leaked it yet. Dual Core ASM would
be awesome for emulators.

D:

Sluts. Homo sluts. At least I haven't been able to find any Centrino ASM,
whereas I have found information on their slutty sexual habits. :O

ZiNgA BuRg Wrote:Haha, that's pretty sweet.  As for "lazy" jobs, I'm looking into teaching piano - piano teachers tend to get AU$40-50 per hour (I'll start off cheaper of course) and you don't really have to do much :P
O.o

That's insane. I don't know anybody who makes that much. Anybody. And I
know some rich pplz.

Fur Elise for the win

[Image: 3c68ce3.jpg]
And when you gaze long into an abyss,
the abyss gazes also into you.
(This post was last modified: 12/04/2007 10:46 PM by _VEndeTta.)
12/04/2007 10:45 PM
Find all posts by this user Quote this message in a reply
Post Reply 


Forum Jump:


User(s) browsing this thread: 1 Guest(s)

 Quick Theme: