FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Why DLX?          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message redtan Joined: 06 Nov 2008 Posts: 5 : Items Posted: Sat Nov 22, 2008 4:45 am    Post subject: Why DLX? I'm doing Final Project for my Bachelor Degree. I'm creating application that can solve sudoku puzzle. From this forum I discovered that DLX is the most popular algorithm to do that (since there are so many use it in this forum. But my problem is that find proof that DLX is better than the others (such as GA, ACO, etc) since my supervisor want me to write the reason why I use DLX instead of others in my project report. Anyone can help? Back to top Adak Joined: 27 Feb 2008 Posts: 87 : Items Posted: Sat Nov 22, 2008 8:45 am    Post subject: I don't believe DLX is the most popular algorithm used to solve Sudoku puzzles. Probably because most people have not heard of DLX, and don't know what it's especially good for, etc. IMO the most popular way for a program to solve a Sudoku puzzle is to first, run the puzzle through some functions that mimic the way a human would start to solve the puzzle - forced singles in rows, columns, or boxes. Afterward, a variety of other "human" type logic functions are used to try and decrease further the number of possibles remaining. At some point, if the puzzle isn't solved yet, the logic functions stop, and the brute force "guessing" function, starts. Here, the remaining possibles (and the cells they came from), are sorted from least to most, and then searched by trial and error. The most efficient way to solve Soduku, imo, is by using bitboards. Check out Brit's blazing bit-based solver, as an excellent example, in this forum. It is not only the fastest solver I've tested, but it is fairly new, and still being optimized. Bitboards are "different" to work with, and even for experienced programmers, take a while to really get comfortable with, and use well. The advantage of course, is that in just one or two machine cycles, you can do work, with multiple squares, all at the same time. It's chess, but check out : www.talkchess.com/ particularly Robert Hyatt's posts on the matter, in the Programming forum at talkchess. His chess program "Crafty", is a famous bitboard based, and open source, program. I'm a hobby programmer, and have enough trouble with mail-box chess programs, but you have to admire the beauty of bitboards for tasks like Sudoku. DLX is a better algorithm than what I use in my solver (described above), but bitboards are better still. Last edited by Adak on Sat Nov 22, 2008 2:29 pm; edited 2 times in total Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Sat Nov 22, 2008 8:52 am    Post subject: Re: Why DLX? redtan wrote: I'm doing Final Project for my Bachelor Degree. I'm creating application that can solve sudoku puzzle. From this forum I discovered that DLX is the most popular algorithm to do that (since there are so many use it in this forum. But my problem is that find proof that DLX is better than the others (such as GA, ACO, etc) since my supervisor want me to write the reason why I use DLX instead of others in my project report. Anyone can help? As this is an academic project, you could try typing "dancing links knuth" into Google. Regards, Mike Metcalf Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Sat Nov 22, 2008 11:57 am    Post subject: Adak wrote: The most efficient way to solve Soduku, imo, is by using bitboards. Check out Brit's blazing bit-based solver, as an excellent example, in this forum. It is not only the fastest solver I've tested, but it is fairly new, and still being optimized. Brit's solver is indeed one of the fastest solvers, but, imo, the strategy is not totally new. Merri posted a solver (see topic) 3 years ago that used that same strategy, but was written in VisualBasic 6. Brit's approach of using optimized bitboards has taken the solver to a 'higher' level. Based upon both Merri's and briturner's solvers, i optimized my little jigsaw sudoku generator (that can generate regular sudokus as well), and is downloadable from this webpage. Here's a screenshot: _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top Adak Joined: 27 Feb 2008 Posts: 87 : Items Posted: Sun Nov 23, 2008 2:32 pm    Post subject: Did we ever get a chance to see what Merri's code was doing? It sounded great, but I didn't see any code posted for it. Is an executable for Windows available for Merri's program? Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Sun Nov 23, 2008 10:33 pm    Post subject: Adak wrote: Did we ever get a chance to see what Merri's code was doing? It sounded great, but I didn't see any code posted for it. Is an executable for Windows available for Merri's program? He posted a link (see post) to the VBForums where you can download the zipped project. A Windows executable is not available, but i have Visual Studio 6.0, so i have the ability to build an executable from his code. I can make a setup for it, upload it to my website, and provide a link, if you wish... Now don't expect stunning times from Merri's solver, after all it is written in Visual Basic and is much slower than C++, but it is a very fast solver, for Visual Basic solver standards... _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top zerothbase Joined: 02 Nov 2008 Posts: 17 : Items Posted: Sat Nov 29, 2008 6:06 pm    Post subject: Ok, I'll bite: What are "GA" and "ACO"? Genetic Algorithm or Greedy Algorithm? Ant Colony optimization? All of these don't really work for the case of Sudoku. All 3 of are meant for problems where "grey area" solutions are allowed. For example, the travelling saleman problem allows for sub-optimal solutions (a slightly longer path), as long as you get close to the optimal solution via the above heuristics. There is, of course, one "right" answer - the most optimal path, but to find it may require a very long time (depending on the problem size), even with these heuristics. Sudoku is an exact cover problem, in that either you have a solution or you don't. There is no grey area. This is similar to pentominoes and the n-queens problem. The question is how many ways are there to exactly cover a given problem space. That is, if you find a "sub-optimal solution" - you don't have a solution, you have a conflict (e.g. two 5's on a single row etc). DLX is designed to count (and iterate through) all of the solutions in a very fast manner. This goal of DLX (fast counting of exact solutions) seems to fit well with what most programmers want out of a solver - give me the number of solutions, and give it to me fast (assuming you aren't creating a human-logic based solver). Can you guarantee that GA or ACO would find all possible solutions to a given problem? Or might it just get stuck in some local optima and return the wrong number of solutions (e.g. return 0 when there is a solution, or 1 when there are multiple)? If you add code to get out of local optima, how much would that slow that whole algorithm down? The standard 9x9 (or 3x3 if you prefer) sudoku is what Knuth describes as a small problem. You can use specialty algorithms that have been tuned (bitboards) to be faster than DLX, but DLX definitely holds its own. On larger problems (16x16, 25x25...) DLX should close that gap and eventually overtake bitboards (though I have yet to see absolute proof of when that happens). If you have other algorithms that compete with DLX for performance and precision, I would love to see them. A genetic algorithm for sudoku solving could be very cool - though I expect it would be slow. If you can break 1000 puzzles/sec/GHz, you are doing well, and if you can hit 5000 puzzles/sec/GHz, you are competitive with bitboards and DLX. --Zerothbase Back to top Adak Joined: 27 Feb 2008 Posts: 87 : Items Posted: Sat Nov 29, 2008 6:50 pm    Post subject: Looking at the contest times he achieved, his solver is still fast. I'm very surprised at the speed his test showed on a file of grids. He obviously has some very efficient optimizations. I would very much like to ask you to make up the executable for his program! Thanks much for the offer, Lunatic. I thought he was pretty much boasting about his own program, but the test showed it was no boast, at all. I'll have to study his description of his program. Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Sat Nov 29, 2008 8:11 pm    Post subject: Adak wrote: I would very much like to ask you to make up the executable for his program! Thanks much for the offer, Lunatic. No thanks, here it is: Merri's Sudoku solver zerothbase wrote: DLX is designed to count (and iterate through) all of the solutions in a very fast manner..... ... You can use specialty algorithms that have been tuned (bitboards) to be faster than DLX, but DLX definitely holds its own. On larger problems (16x16, 25x25...) DLX should close that gap and eventually overtake bitboards (though I have yet to see absolute proof of when that happens). If you have other algorithms that compete with DLX for performance and precision, I would love to see them. I think that human logic in combination with DLX would perform better than they do seperately, but i don't have any proof. My thinking is based upon the following: For fast results, i normally use human logic in combination with brute force to solve a sudoku. I mean, first solve as many cells with some simple human logic, and then brute force the rest of the puzzle. Theoretical, for each cell, solved with human logic, the brute force will have a factor 9 less possibilities to check. Now, i've done some tests, and came to the conclusion that only solving naked and/or hidden singles really increases the total solving speed, other human like strategies will take longer than brute force. In another thread (see topic), i briefly discussed with briturner the possibility of using DLX in combination with human logic, but not the way as i described above. briturner came up with the idea to use human logic over and over again alternated with brute force. Little was i to know that in fact briturner allready made his solver based upon that principle, only he didn't use DLX for the brute force. In my opinion, using DLX is still worth trying, but this far, to my knowledge, no-one has made an attempt. Anyway, the stunning times of briturner's solver, made me think of merri's solver, who happened to be much faster than mine. Because merri's solver and my solver are both written in Visual Basic, and in my opinion, my code was very optimized, i began to wonder if merri used the same principle as briturner. So i tracked merri's code to find out that he did. As a result, i adapted my own code to handle alternating human logic with brute force through the whole solving process too, and managed to solve sudokus much faster now. I used that same principle in my Jigsaw Sudoku generator (see one of my posts above). _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top zerothbase Joined: 02 Nov 2008 Posts: 17 : Items Posted: Sat Nov 29, 2008 9:19 pm    Post subject: Quote: I think that human logic in combination with DLX would perform better than they do seperately The problem with your hypothesis is that DLX does use human logic. The first 81 columns are the naked singles, and the other 243 are the hidden singles. The minimum column optimization in Knuth's paper often finds a naked or hidden single and then chooses the appropriate row (which is the same as a bitboard placing a value in a square). Otherwise, DLX iterates over the smallest column which is the same as guessing in a bitboard solver by iterating over the square with the fewest possibilities, or iterating over a value in a house with the fewest places to put the value. The power of bitboards are their ability to handle whole sections of the puzzle in a single computer word (32- or 64-bit). When puzzle size gets too large for word size, suddenly you end up doubling the number of operations per pass (and it gets worse from there as puzzle size gets larger). DLX breaks the problem down into smaller problems and only deals with the unsolved portion. The way that briturner's code only checks changed houses helps a lot, but eventually, the act of iterating over a given house (even if you skip solved cells), in combination with doubling/tripling the number of operations, will become too much of a timesink for bitboards (compared with DLX simply ignoring all solved squares entirely). If you directly combine bitboards and DLX, you would be keeping state information in 2 places which would halve your speed. The same would occur if you only use DLX for guesses - the process of getting the DLX matrix into a proper state to perform a single guess would be cost prohibitive. However, I do believe that if one wanted to create the fastest solver possible for all circumstances, it would be a combination of bitboards at smaller puzzle sizes and switch to DLX at some arbitrary cut-off point of large puzzles. Though finding an ideal cut-off point would require a lot of testing with a variety of puzzles (or you could just switch over to DLX for any puzzle over a word size). Quote: solving naked and/or hidden singles really increases the total solving speed, other human like strategies will take longer than brute force btw briturner's code uses Locked Candidates and he found it drastically increases the speed of hard puzzles, while not impacting easy puzzles too much. He found subsets (twins/triplets etc) were the slowdown point (gsf previously mentioned this "knee" here). --zerothbase Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Sat Nov 29, 2008 10:51 pm    Post subject: zerothbase wrote: The problem with your hypothesis is that DLX does use human logic. The first 81 columns are the naked singles, and the other 243 are the hidden singles........ Well, i never saw it that way, thanks, i totally misjudged that. I thought that DLX basically only picked the cell with the least candidates. So, naked singles are solved first, followed by bivalue cells, and so on... I red Knuth's paper a few years ago trying to understand what was going on, in order to write a solver in Visual Basic based upon it. There was simply no way for me to use pointers like one could in C++, so i came up with an alternative for DLX. And yet, my solver performs much faster since i used the approach i described in my previous post. I think i will have to take another look on my brute force code. zerothbase wrote: btw briturner's code uses Locked Candidates and he found it drastically increases the speed of hard puzzles, while not impacting easy puzzles too much. He found subsets (twins/triplets etc) were the slowdown point (gsf previously mentioned this "knee" here). I tried locked candidates myself, but it was allready beyond the slow down point for my solver. Am i feeling the boundaries of Visual Basic coding ? Could be... _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top JasonLion Joined: 16 Nov 2008 Posts: 62 : Location: Silver Spring, MD Items Posted: Sun Nov 30, 2008 12:59 am    Post subject: Lunatic wrote: I tried locked candidates myself, but it was allready beyond the slow down point for my solver. Am i feeling the boundaries of Visual Basic coding ? Could be... Briturner has some very very clever, very efficient, code to check for locked candidates. I suspect that if you duplicated his entire approach in Visual Basic, checking for locked candidates would give you about the same percentage improvement that it gave him. Gsf covered much the same range of approaches to writing a solver in his collection of solvers quite some time ago. Briturner's code is very similar in the abstract to what gsf did, but briturner uses a somewhat different data structure. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming sudoku All times are GMT Page 1 of 1   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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 vote in polls in this forum   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron