librelist archives

« back to archive

solve sudoku

solve sudoku

From:
Allen Maxwell
Date:
2012-07-30 @ 05:14
I got it done.  wish I could say I did it all on my own but the last 
algorithm that does a recursive brut force resolution was copied from some
stuff I found on the net.  but it does work pretty well and I think it 
will solve any valid sudoku puzzle.

code is on github.  user name aamax

see ya monday?

Max

Re: [getarailsjob] solve sudoku

From:
Stanley Stuart
Date:
2012-07-30 @ 05:25
Solving sudoku puzzles is an interesting problem because it's NP-complete,
meaning that nobody has found an "efficient" or fast way to solve them.

I won't be there tomorrow night, I'll be at work.  Have fun guys.

Re: [getarailsjob] solve sudoku

From:
Allen Maxwell
Date:
2012-07-30 @ 05:38
the computer does it very quickly but it's a brute force approach so not 
efficient or very elegant.  uses a backtrace recursive algorithm.

fun to get done.

Max


On Jul 29, 2012, at 11:25 PM, Stanley Stuart wrote:

> Solving sudoku puzzles is an interesting problem because it's 
NP-complete, meaning that nobody has found an "efficient" or fast way to 
solve them.
> 
> I won't be there tomorrow night, I'll be at work.  Have fun guys.

Re: [getarailsjob] solve sudoku

From:
Date:
2012-07-30 @ 06:04
I'm just curious are you guys learning ruby by solving sudoku or just 
learning programming in general with any language by solving sudoku? There
is a more efficient method compared to brute force and you will need to 
use integer linear programming. You probably need to use an external 
library like lp_solve hence I asked the question. It is essentially 
bruteforce but the searching space is greatly reduced,especially for some 
easy problems.the harder ones I think integer linear programming might 
perform the same. But good stuff, I'd always wanted to do this before but 
it has become some sort of a pipe dream for me.lol.
------Original Message------
From: Allen Maxwell
Sender: getarailsjob@librelist.com
To: getarailsjob@librelist.com
ReplyTo: getarailsjob@librelist.com
Subject: Re: [getarailsjob] solve sudoku
Sent: Jul 29, 2012 11:38 PM

the computer does it very quickly but it's a brute force approach so not 
efficient or very elegant.  uses a backtrace recursive algorithm.

fun to get done.

Max


On Jul 29, 2012, at 11:25 PM, Stanley Stuart wrote:

> Solving sudoku puzzles is an interesting problem because it's 
NP-complete, meaning that nobody has found an "efficient" or fast way to 
solve them.
> 
> I won't be there tomorrow night, I'll be at work.  Have fun guys.


Re: [getarailsjob] solve sudoku

From:
Allen Maxwell
Date:
2012-07-30 @ 13:53
Actually, sudoku was just a thing my son thought up while he and I were 
doing a TDD kata and it sounded like fun so I was just sharing the process
and idea with the group since we've been doing some little katas here and 
there.  I was teaching him some ruby and general TDD.  Lately my focus has
been ruby and rails specific but I see it as improving my craft in 
general.

I deviated from the total brute force method in that I solved as much of 
it as possible by analyzing all cells that can be distilled down to one 
possibility without substitution first.  then applied brute force to the 
remaining cells.  Not sure if it makes much of a difference on very 
complex puzzles but my TDD process walked me down that path and it made 
sense.

It a fun weekend thing. ;)

Max


On Jul 30, 2012, at 12:04 AM, dbancajas@gmail.com wrote:

> I'm just curious are you guys learning ruby by solving sudoku or just 
learning programming in general with any language by solving sudoku? There
is a more efficient method compared to brute force and you will need to 
use integer linear programming. You probably need to use an external 
library like lp_solve hence I asked the question. It is essentially 
bruteforce but the searching space is greatly reduced,especially for some 
easy problems.the harder ones I think integer linear programming might 
perform the same. But good stuff, I'd always wanted to do this before but 
it has become some sort of a pipe dream for me.lol.
> ------Original Message------
> From: Allen Maxwell
> Sender: getarailsjob@librelist.com
> To: getarailsjob@librelist.com
> ReplyTo: getarailsjob@librelist.com
> Subject: Re: [getarailsjob] solve sudoku
> Sent: Jul 29, 2012 11:38 PM
> 
> the computer does it very quickly but it's a brute force approach so not
efficient or very elegant.  uses a backtrace recursive algorithm.
> 
> fun to get done.
> 
> Max
> 
> 
> On Jul 29, 2012, at 11:25 PM, Stanley Stuart wrote:
> 
>> Solving sudoku puzzles is an interesting problem because it's 
NP-complete, meaning that nobody has found an "efficient" or fast way to 
solve them.
>> 
>> I won't be there tomorrow night, I'll be at work.  Have fun guys.
> 
> 
>