• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 17:18
CET 23:18
KST 07:18
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #2312[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over5Dark completes military service, returns to SC217[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
SC4ALL: II Indiegogo Campaign Announcement No more SC2 streamers on team liquid? Team Liquid Map Contest #23 StarCraft open world shooter announced at BlizzCon Weekly Cups (Nov 9-15): Clem and herO take over
Tourneys
RSL goes to London! 2026 Offline Finals Nov 21-22 soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16) Sparkling Tuna Cup - Weekly Open Tournament Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 552 Secret Storm The PondCast: SC2 News & Results Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift
Brood War
General
Shield Battery Server New Patch List of top players active on ShieldBattery SC4ALL: II Indiegogo Campaign Announcement Light introduces ShieldBattery on his YouTube Practice Partners (Official)
Tourneys
[BSL23] Ro16 Group B - Saturday 21:00 CET 2v2v2v2 Tournament Stage 2: Players KCM Race Survival 2026 Season 4 SC1 Kevin Scrim hosted by SOOP (Nov 18-19)
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
The PlayStation 5 Stormgate/Frost Giant Megathread Nintendo Switch Thread Warcraft III: The Frozen Throne Free Space RTS Game, optimised f. Phone/Tablet etc
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread Artificial Intelligence Thread Russo-Ukrainian War Thread The Big Programming Thread Trading/Investing Thread
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
CEO
DeathFlowx
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
James Bond movies ranking - pa…
Topin
Customize Sidebar...

Website Feedback

Closed Threads



Active: 18872 users

[R] I need a name - Page 3

Blogs > berated-
Post a Reply
Prev 1 2 3 All
BroOd
Profile Blog Joined April 2003
Austin10833 Posts
April 28 2008 21:50 GMT
#41
Truedoku
ModeratorSIRL and JLIG.
azndsh
Profile Blog Joined August 2006
United States4447 Posts
Last Edited: 2008-04-28 22:23:12
April 28 2008 22:22 GMT
#42
On April 28 2008 23:57 berated- wrote:
Show nested quote +
On April 28 2008 14:18 azndsh wrote:
aren't sudoku SAT solvers extremely inefficient? unless you formulate the problem way differently from what I have in mind


That's really kind of irrelevant to the project. I'm taking a boolean satisfiability class and we have to do a final project related to boolean equations. Considering I'm not a total badass, I knew I wasn't going to come up with the next great thing such as WalkSAT or Davis Putnam or GSAT, any of the SAT solving techniques that were monumental upon release. So I was left with two options, I could either find some current research and write an 8 page paper on it, or I could code up an algorithm.

Reading conference papers didn't strike me as overly fun, so I went with a coding project. I could then do something like just pass a boolean equation to an algorithm and try to solve it, which would have got the job done but is a little bland. So I sought out something that would at least be enjoyable.

As for the original question, my first response would have to be no. Using DP, a true sudoku puzzle ( one with only one answer and requiring no search techniques ) would actually require only unit propagation while solving the algorithm. Of course, you would have to define what it is inefficient compared to. Its obviously better than a try all possibilities solution. Are there other algorithms out there that might do better? I have no idea. I wasnt studying Sudoku, I was studying boolean equations, so I apologize that I can't give you a better answer.

I guess you would have to make that judgment call:

My technique ( learned from the work of others who have already done this - I'm just an undergrad, I can't be doing monumental work in my field ):

There are 729 variables - one for every possible number in every possible cell. These are represented by a 3 digit string - the row, the column, and the number.

So 111 refers to a one being in the upper left most box, and will be a 1 if there is a 1 there, 0 otherwise. A - in front represents that the boolean is negated. so -111 refers to Not a 1 in the upper left hand box

Then you have to generate the equation, it will be in CNF form -

So the first thing to check is that there is a 1-9 in every cell.
so, 111 v 112 v 113 v 114 v 115 v 116 v 117 v 118 v 119
but then you need to make sure there aren't more than one
so
-111 v -112, -111 v -113 . . . etc

Repeat for rows, columns, and boxes.

And solve.

Edit: Okay, well yes I would say that having a SAT solver for a 9x9 sudoku puzzle is a little over the top. I knew that it was for a 9x9, but I guess I didn't realy realize how much over the top it was. Of course, it doesn't help that I'm using a lot of java classes - trying to really modularize my code to make it easier to understand and write.

Using strictly ints and try all possibilities it takes java about 64 ms to solve a sudoku puzzle. Using my sat solver it takes about 400ms to solve - however, the largest time with my solver is keeping track of which variables I flipped and which ones I didn't, because I have to store and reset the variables while backtracking.

It might be kind of interesting to mod my program and then try to see some results. I've seen some sat solvers that use strictly ints ( as i described the 111 stuff above, all that is ints while i use 4 different wrapper classes to keep the method writing short). I think that if I were go get my program working in that state, and then we compared the run times you would see a lot closer of a contest.

Where I think the SAT solver would really shine would be on the larger puzzles for a generalized sudoku puzzle of size nxn. I would guess that even at 16x16 the sat solver ( if done properly with int values instead of classes ) would already start to out due the try all possibilities approach.

Once again though, I had fun with the project and truly believe it will still get me an A, so I'm not too worried about the efficiency. Hope this explain things a little better, and thanks for the thought provoking question.



yeah... with 729 variables and thousands of restrictions, it seems like it would take a very long amount of time for non-trivial puzzles. I only ask because we were each asked to make a SAT solver and puzzle generator in one of my CS classes. We even had a competition to see who had the best solver in the end. One really simple and effective heuristic is to assume that all your variables are false at the beginning, which in this case is true 8/9 of the time.

I ended up doing a 4x4 version of sudoku puzzles, but that was relatively straightforward and ran very quickly.
berated-
Profile Blog Joined February 2007
United States1134 Posts
April 29 2008 00:11 GMT
#43
On April 29 2008 07:22 azndsh wrote:
Show nested quote +
On April 28 2008 23:57 berated- wrote:
On April 28 2008 14:18 azndsh wrote:
aren't sudoku SAT solvers extremely inefficient? unless you formulate the problem way differently from what I have in mind


That's really kind of irrelevant to the project. I'm taking a boolean satisfiability class and we have to do a final project related to boolean equations. Considering I'm not a total badass, I knew I wasn't going to come up with the next great thing such as WalkSAT or Davis Putnam or GSAT, any of the SAT solving techniques that were monumental upon release. So I was left with two options, I could either find some current research and write an 8 page paper on it, or I could code up an algorithm.

Reading conference papers didn't strike me as overly fun, so I went with a coding project. I could then do something like just pass a boolean equation to an algorithm and try to solve it, which would have got the job done but is a little bland. So I sought out something that would at least be enjoyable.

As for the original question, my first response would have to be no. Using DP, a true sudoku puzzle ( one with only one answer and requiring no search techniques ) would actually require only unit propagation while solving the algorithm. Of course, you would have to define what it is inefficient compared to. Its obviously better than a try all possibilities solution. Are there other algorithms out there that might do better? I have no idea. I wasnt studying Sudoku, I was studying boolean equations, so I apologize that I can't give you a better answer.

I guess you would have to make that judgment call:

My technique ( learned from the work of others who have already done this - I'm just an undergrad, I can't be doing monumental work in my field ):

There are 729 variables - one for every possible number in every possible cell. These are represented by a 3 digit string - the row, the column, and the number.

So 111 refers to a one being in the upper left most box, and will be a 1 if there is a 1 there, 0 otherwise. A - in front represents that the boolean is negated. so -111 refers to Not a 1 in the upper left hand box

Then you have to generate the equation, it will be in CNF form -

So the first thing to check is that there is a 1-9 in every cell.
so, 111 v 112 v 113 v 114 v 115 v 116 v 117 v 118 v 119
but then you need to make sure there aren't more than one
so
-111 v -112, -111 v -113 . . . etc

Repeat for rows, columns, and boxes.

And solve.

Edit: Okay, well yes I would say that having a SAT solver for a 9x9 sudoku puzzle is a little over the top. I knew that it was for a 9x9, but I guess I didn't realy realize how much over the top it was. Of course, it doesn't help that I'm using a lot of java classes - trying to really modularize my code to make it easier to understand and write.

Using strictly ints and try all possibilities it takes java about 64 ms to solve a sudoku puzzle. Using my sat solver it takes about 400ms to solve - however, the largest time with my solver is keeping track of which variables I flipped and which ones I didn't, because I have to store and reset the variables while backtracking.

It might be kind of interesting to mod my program and then try to see some results. I've seen some sat solvers that use strictly ints ( as i described the 111 stuff above, all that is ints while i use 4 different wrapper classes to keep the method writing short). I think that if I were go get my program working in that state, and then we compared the run times you would see a lot closer of a contest.

Where I think the SAT solver would really shine would be on the larger puzzles for a generalized sudoku puzzle of size nxn. I would guess that even at 16x16 the sat solver ( if done properly with int values instead of classes ) would already start to out due the try all possibilities approach.

Once again though, I had fun with the project and truly believe it will still get me an A, so I'm not too worried about the efficiency. Hope this explain things a little better, and thanks for the thought provoking question.



yeah... with 729 variables and thousands of restrictions, it seems like it would take a very long amount of time for non-trivial puzzles. I only ask because we were each asked to make a SAT solver and puzzle generator in one of my CS classes. We even had a competition to see who had the best solver in the end. One really simple and effective heuristic is to assume that all your variables are false at the beginning, which in this case is true 8/9 of the time.

I ended up doing a 4x4 version of sudoku puzzles, but that was relatively straightforward and ran very quickly.


While it does take a long time relatively, under half a second to solve a sudoku puzzle is still pretty fast imo. As far as the competition part, that sounds awesome. They have a national sat competition every year that my prof has been to. Of course the people who enter those are the people that created most of the algorithms that we studied this year.

I talked to my professor about holding one at our school when he got to teach his boolean SAT course again, but considering our honors seminar class has 2 people in it, I doubt it would be much fun. Plus I'm graduating so I wouldn't even get to stay around to enjoy it.
minus_human
Profile Blog Joined November 2006
4784 Posts
April 29 2008 00:13 GMT
#44
sudoku=> songoku

[image loading]
Prev 1 2 3 All
Please log in or register to reply.
Live Events Refresh
Next event in 12h 42m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
ProTech159
EmSc Tv 34
StarCraft: Brood War
Shuttle 388
910 18
Dota 2
XaKoH 688
BananaSlamJamma402
syndereN358
Counter-Strike
edward96
Heroes of the Storm
Liquid`Hasu618
Trikslyr59
Other Games
tarik_tv4375
Grubby2792
FrodaN1547
shahzam349
ArmadaUGS104
ZombieGrub100
PPMD25
ToD25
Models1
Organizations
Other Games
BasetradeTV135
StarCraft 2
EmSc Tv 34
[ Show 15 non-featured ]
StarCraft 2
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• Azhi_Dahaki59
• Michael_bg 5
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• masondota21520
• WagamamaTV918
League of Legends
• Stunt195
Other Games
• imaqtpie1237
• Shiphtur500
Upcoming Events
RSL Revival
12h 42m
AI Arena Tournament
18h 42m
BSL
21h 42m
eOnzErG vs StRyKeR
Cross vs JDConan
RSL Revival
1d 13h
IPSL
1d 18h
Ret vs ggnore13
nOmaD vs Aether
BSL
1d 21h
Bonyth vs Doodle
Kyrie vs Jimin
Replay Cast
2 days
WardiTV Weekly
2 days
Kung Fu Cup
3 days
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
4 days
[ Show More ]
The PondCast
5 days
KCM Race Survival
5 days
Liquipedia Results

Completed

Proleague 2026-11-17
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3

Upcoming

Sector 591
YSL S4
SC4ALL II: Brood War
CSL 2026 Winter (S23)
NBSL 2026 Xiamen LAN
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.