FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    The fastest method of creating unique puzzles Goto page Previous  1, 2          Sudoku Programmers Forum Index -> Setting sudoku View previous topic :: View next topic   Author Message antony Joined: 22 Jul 2005 Posts: 13 : Items Posted: Fri Jul 22, 2005 11:33 pm    Post subject: I added a generator to my zipped demo. It uses your loop. With the pair removal step, it generates 2300 grids/min (symmetrical, 25 fixed cells at most, unique solution) ready for grid rating. Speed strongly depends on what output you ask: I only achieve 2 grids/min for size-21 grids. This is less than the speed reported by rubylips at the beginning of the thread, so I guess there are possible improvements over the "random" loop. Back to top tilps Joined: 19 Jun 2005 Posts: 44 : Items Posted: Sat Jul 23, 2005 2:56 am    Post subject: I was under the impression that rubylips Only generated size 21 grids since rubylips was randomly laying out 21 numbers then solving. If you are after a specific size, then that way will probably be faster (upto some extent, I have evidence that skipping ahead is not very effective on 4x4). However, I am after sampling a random subset of the full sudoku space. Never know where the difficult ones will be found (my most difficult puzzle to date is a size 26). The pair removal step I should actually add, I just havent yet, since my pair removal step was still using slow code. But this way I get to see if the pair removal step shifts the difficulty spectrum. Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Sat Jul 23, 2005 6:51 am    Post subject: here is another idea to generate sudokus with c-clues: fill c1 cells with 1s (c1=2 or 3) and c-c1 cells with non-1s randomly , such that there is a unique (out of the 46656) set of nonattacking sudoku-leapers which meets the 1s and avoids the non-1s. Continue with the 2s : pick some 2s from the non-1s such that there is a unique set from the 46656 which meets the 2s and avoids the non-2s including the nine 1s. etc. until the board is filled Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Sat Jul 23, 2005 10:04 am    Post subject: jaap wrote: Hi, This is my first post here. I have also made a Sudoku solver/generator. I'd be interested to hear what you guys think of it, and how it compares to others. http://www.geocities.com/jaapsch/sudoku.htm The solver uses a clever brute force method, essentially the Dancing Links algorithm by Don Knuth (without the links but with the full matrix instead). rallveird wrote: I would like to see some numbers from people on which type of solving is fastest. I don't have any numbers on mine, but the solver does use two solving modes - a fast one for checking solvability, and one with extra logical rules that generates a log and judges difficulty more accurately. rallveird wrote: My solving code basically try to find the spot with least possible numbers and iterate from there (over the possible numbers). The fun part of the dancing links algorithm is that all the constraints that need to be satisfied are treated equally. A cell with only one possible digit, or a row/column/box with only one placement for a particular digit, are both treated in the same way. If none of these constraints have only one possibility, then (in fast mode) it makes a guess for one of the constraints that has only 2 possibilities. This can be a cell with two possible values, or a row/column/box with two possible placements for a particular digit. I implemented two extra deduction rules for slow but more human solving. The first is a 'single sector candidates' rule: 1. If all possibilities for satisfying one constraint also satisfy a second constraint, then any other possibilities for the second constraint may be discarded. The second rule is this: 2. If a pair of constraints can be satisfied in only two interdependent ways, then any other constraint that is satisfied by both those solutions can have its other possibilities discarded. This reads like a kind of x-wings rule, but due to the equal treatment of the constraints, many cases of the 'disjoint subsets' rule also get caught by this one. Let me know what you think. how do you distinguish the constraints, when they are treated equally ? can you translate the other rules into your unified system too ? what language ? is the source-code available ? can lookahead-technique be easily included in your program ? Back to top jaap Joined: 13 Jun 2005 Posts: 24 : Location: NL Items Posted: Sat Jul 23, 2005 10:50 pm    Post subject: dukuso wrote: how do you distinguish the constraints, when they are treated equally? You don't really have to distinguish the types of constraint. In Dancing Links, each constraint is a column of a large matrix. From the column number you can work out which constraint it is, but during the algorithm you don't need to. I only do so when generating a log. See my post in this thread for an example of the output of my second logic rule, which is for x-wings, matched pairs, and related deductions. http://www.setbb.com/phpbb/viewtopic.php?t=95&mforum=sudoku dukuso wrote: can you translate the other rules into your unified system too ? It should be possible, but it gets rather hard. dukuso wrote: what language ? is the source-code available ? Java. Code is not available unfortunately, since it will be used in a commercial setting. dukuso wrote: can lookahead-technique be easily included in your program ? What do you mean exactly? If it doesn't have a forced move, it tries to apply the logic deduction rules. If those don't simplify things, it has to start making guesses and backtracking if it then hits a snag. In a way, the logic rules are a kind of lookahead, since it would have to start guessing earlier if it didn't have them. The more complete the set of logic rules is, the more it avoids trouble arising from having to guess. Jaap http://www.geocities.com/jaapsch/puzzles/ http://www.geocities.com/jaapsch/sudoku.htm _________________ Jaap -- Jaap's Puzzle Page: http://www.geocities.com/jaapsch/puzzles Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Sun Jul 24, 2005 8:24 am    Post subject: Jaap, your 2 logic-rules, I don't quite understand them. We probably agree that there are 4 kinds of basic forced placements - in the binary exact-cover matrix it's just the rows which are the only ones to intersect some column. (sum of the column is 1) Now we have the natural rule, that when there is a column of sum=2 and exactly one of the two placements (rows) intersecting the column leads to a dead end (or solution) when only allowing forced moves, then the other row must be taken as forced-level-2-move. I assume, this rule includes both of your rules ?! Guenter. Back to top jaap Joined: 13 Jun 2005 Posts: 24 : Location: NL Items Posted: Mon Jul 25, 2005 6:02 am    Post subject: dukuso wrote: Jaap, your 2 logic-rules, I don't quite understand them. I'll get to those in a moment. dukuso wrote: We probably agree that there are 4 kinds of basic forced placements. To me, there is only one kind of forced placement in my opinion - if a column in the matrix has only 1 entry, the row with that entry is a forced move. It doesn't matter what kind of constraint that column represents, that is the beauty of it. dukuso wrote: Now we have the natural rule, that when there is a column of sum=2 and exactly one of the two placements (rows) intersecting the column leads to a dead end (or solution) when only allowing forced moves, then the other row must be taken as forced-level-2-move. I assume, this rule includes both of your rules ?! No it doesn't really. The rules I use are elimination rules. They eliminate candidates, in the hope of producing a forced move in the next step. My first rule is this: Suppose there are two columns in the matrix, A and B, and that for every row where A has a non-zero entry B also has a non-zero entry. Any move that satisfies constraint A then also satisfies constraint B. Therefore we can eliminate any other entries in column B (i.e. any matrix row that has an entry in B but not in A). This rule does things like this: If the only places to put digit 7 in row 1 all lie in box 1, then the cells in box 1 rows 2&3 cannot hold a 7. My second rule is this: Suppose there are 2 columns A and B, each with exactly two entries, say A1, A2, and B3,B4. Suppose also that A1 conflicts with B3 (there is some column that has entries in rows 1 and 3) and similarly that A2 conflicts with B4. Then we must have one of the moves 1 or 3, and also have one of the moves 2 or 4. Any column with entries in 1 and 3 can have its other entries eliminated. Similarly, any column with entries in 2 and 4 can have its other entries eliminated. This rule does things like this: If one cell in row 1 has candidates {1 2}, another has candidates {1 2 3}, and no other cell in row 1 has 1 or 2 as a candidate, then the second cell has candidate 3 removed. or like this: If two cells in row 1 have only candidates {1 2}, then any other cell in row 1 can have 1 and 2 removed as candidates. or like this (rectangular x-wings): If the only placements of digit 7 in row 1 are in columns 4 and 5, and the only placements of digit 7 in row 8 are also in columns 4 and 5, then any other cells in columns 4 and 5 can have 7 removed as a candidate. or even like this (other kind of x-wings): If the only placements of digit 7 in box 1 are at (1,1) and (2,1), and the only placements of digit 7 in box 2 are (1,4) and (2,6), then any other cells in rows 1 and 2 can have 7 removed as a candidate. (Actually this would most likely be caught by application of the first rule - restricting the 7 in row 3 to box 3, but occasionally things like the above do come up.) Jaap _________________ Jaap -- Jaap's Puzzle Page: http://www.geocities.com/jaapsch/puzzles Back to top antony Joined: 22 Jul 2005 Posts: 13 : Items Posted: Mon Jul 25, 2005 7:06 am    Post subject: dukuso wrote: how do you distinguish the constraints, when they are treated equally ? can you translate the other rules into your unified system too ? Here is my own interpretation of some logic rules in the context of dancing links. Anyway, the good thing with dancing links is that most rules get naturally "generalized". For example, X-Wings with intersecting rows & columns also holds for intersecting rows & blocks, but you don't have to hard-code it, the algorithm does it automatically. Below, "constraints" and "candidates" stand for the columns and rows of the dancing links matrix (that avoids confusion with the rows and columns of the sudoku grid.) Transposal of Single sector, Locked pair, X-Wing, Swordfish, Jellyfish, some disjoint subsets: Choose any constraint. Select (one after another) each candidate for it, look at which constraints can be solved by recursively solving sum-1 constraints only (stop when there are none left). If a constraint has been solved in all cases, you can discard any candidate for it, except the candidates you solved it with. Notes: - a constraint always solved within the first recursion is an X-Wing; within the first 2 recursions a Swordfish, etc. - a constraint always solved before any recursion is a locked pair (if initially chosen constraint is sum-2) or a single sector. This means that the constraint has at least the same candidates as the chosen one. Remote locked pair: Choose any constraint. Select in turn each of its candidates, look at which candidates are discarded when you recursively solve sum-1 constraints. If a candidate has been discarded in all cases, you can discard it. Forcing chains: Choose any constraint. Select in turn each of its candidates, look at which others candidates are discarded or selected when you recursively solve sum-1 constraints. If a candidate has been discarded in all cases, you can discard it (one candidate down). If a candidate has been selected in all cases, it is part of the solution (that's one cell solved!) Nishio: Apply any candidate. Recursively solve sum-1 constraints only. If you end up with a sum-0 constraint, you can discard the candidate. I still miss a satisfactory method for transposing Disjoint Subsets and Unique Subsets... I don't know if it's accurate. Hoping it makes sense Regards [Added: if anyone is interested in a Java Dancing Links (with links) solver, I rewrote my C++ class: http://jpboucher.free.fr/antony/DLXSolver.java.zip ] Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Mon Jul 25, 2005 9:33 am    Post subject: >dukuso wrote: > >>Now we have the natural rule, that when there is >>a column of sum=2 and exactly one of the >>two placements (rows) intersecting the column >>leads to a dead end (or solution) when only allowing >>forced moves, then the other row must be taken >>as forced-level-2-move. >>I assume, this rule includes both of your rules ?! Jaap wrote: >No it doesn't really. The rules I use are elimination rules. >They eliminate candidates, in the hope of producing a forced >move in the next step. > >My first rule is this: >Suppose there are two columns in the matrix, A and B, and that >for every row where A has a non-zero entry B also has a non-zero entry. >Any move that satisfies constraint A then also satisfies constraint B. >Therefore we can eliminate any other entries in column B >(i.e. any matrix row that has an entry in B but not in A). A row intersecting B but not A forces all rows to be removed which intersect B. This includes all rows intersecting A and A would become empty which isn't allowed. So we have a forced chain to exclude that row and my rule governs this case. >My second rule is this: >Suppose there are 2 columns A and B, each with exactly two entries, >say A1, A2, and B3,B4. Suppose also that A1 conflicts with B3 >(there is some column that has entries in rows 1 and 3) and you mean : rows A1 and B3 >similarly that A2 conflicts with B4. >Then we must have one of the moves 1 or 3, and also have >one of the moves 2 or 4. >Any column with entries in 1 and 3 can have its other >entries eliminated. Similarly, any column with entries >in 2 and 4 can have its other entries eliminated. suppose we pick a row r, which intersects rows A1 and B3 both. Rows A1 and B3 will be removed, the only members remaining in columns A and B are A2 and B4 so we must pick them both as forced moves but since A2 conflicts with B4 we will have a column od sum>1 - contradiction. So this is also a subcase of my rule above. And, of course then I want to generalize to forced moves of level 3 etc. And I think it can be best done with a general exact-cover- solver. Is any of you planning to do the same ? Antony ? Jaap ? Do you think it will be easy ? See my C-code here: http://www.setbb.com/phpbb/viewtopic.php?t=119&mforum=sudoku Back to top jaap Joined: 13 Jun 2005 Posts: 24 : Location: NL Items Posted: Mon Jul 25, 2005 9:56 am    Post subject: dukuso wrote: So this is also a subcase of my rule above. And, of course then I want to generalize to forced moves of level 3 etc. And I think it can be best done with a general exact-cover- solver. Is any of you planning to do the same ? Anthony ? Jaap ? Do you think it will be easy ? Now I see what you're getting at. I like this a lot. I may implement that eventually, but I won't for the time being. I don't think it is that hard to implement, but certainly not trivial. It depends on whether you can reuse the code for solving normally for doing this limited lookahead. _________________ Jaap -- Jaap's Puzzle Page: http://www.geocities.com/jaapsch/puzzles Back to top tilps Joined: 19 Jun 2005 Posts: 44 : Items Posted: Mon Jul 25, 2005 12:11 pm    Post subject: antony wrote: Here is my own interpretation of some logic rules in the context of dancing links. Anyway, the good thing with dancing links is that most rules get naturally "generalized". For example, X-Wings with intersecting rows & columns also holds for intersecting rows & blocks, but you don't have to hard-code it, the algorithm does it automatically. Below, "constraints" and "candidates" stand for the columns and rows of the dancing links matrix (that avoids confusion with the rows and columns of the sudoku grid.) Transposal of Single sector, Locked pair, X-Wing, Swordfish, Jellyfish, some disjoint subsets: Choose any constraint. Select (one after another) each candidate for it, look at which constraints can be solved by recursively solving sum-1 constraints only (stop when there are none left). If a constraint has been solved in all cases, you can discard any candidate for it, except the candidates you solved it with. Notes: - a constraint always solved within the first recursion is an X-Wing; within the first 2 recursions a Swordfish, etc. - a constraint always solved before any recursion is a locked pair (if initially chosen constraint is sum-2) or a single sector. This means that the constraint has at least the same candidates as the chosen one. This and the remote locked pair and forcing chains, your descriptions are all the same, this is what I expected. my ratings in relation to your system here is well defined. 0 puzzles require are solvable entirely by forced moves. 1.a.b puzzles require a recursions on sum 1 from a sum b starting point. 2 puzzles require a single recursion of > sum 1 after a sum n starting point. n puzzles require n-1 recursions of > sum 1 after a sum k starting point. Currently I am deciding how to detail the rating of 2 puzzles 2.a.b.c.d, require a recursions of sum-1 followed by a sum-d break followed by c recursions of sum-1 all from a sum-b starting point. That is my current plan, n.a.b.c.d.e.f.g.h... sum-b,{sum-1}*a, sum-d,{sum-1}*c, sum-f,{sum-1}*e,... the rating applies the deepest leaf of the tree searched to find eliminations, and the elimination must be found in all subbranches. Quote: Nishio: Apply any candidate. Recursively solve sum-1 constraints only. If you end up with a sum-0 constraint, you can discard the candidate. I try to avoid 'obvious' trial and error, whcih is what sum-0 leads to. I am yet to discover a puzzle (over 2million generated) which cannot be solved using the constructive methods only. Ofcourse at the 1million mark i still hadnt found one which was rated > 1.7.3, so its always possible. I also havent found an 18 size symmetrical board yet either. I am thinking of seeing if i can write a dancing links limited recursion solver, since it might be able to generate my ratings faster then my current solver, although it probably wont be much faster, since the primary slowness comes from enforcing that all moves of lower rating are taken before ones of higher rating. Also it should produce 'minimal logic' faster. Hrmm need to think about this more, when there are multiple options for recursion of sum 1, my solver considers them to be all at the same level, so 1.a.b may be less then a recursions, since I can take multiple at once. Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Mon Jul 25, 2005 1:06 pm    Post subject: jaap wrote: or even like this (other kind of x-wings): If the only placements of digit 7 in box 1 are at (1,1) and (2,1), and the only placements of digit 7 in box 2 are (1,4) and (2,6), then any other cells in rows 1 and 2 can have 7 removed as a candidate. (Actually this would most likely be caught by application of the first rule - restricting the 7 in row 3 to box 3, but occasionally things like the above do come up.) This is supposed to always be caught by application of the first rule. Can you give an example where this wouldn't happen? In my solver, I have added a "type" tag to the constraints. When apply the second rule, I limit the types of the constraints involved to this list (left is the type of the two constraints that only have two candidates, tight is the type of the two constraints that cause the confilct): Code: { COLUMN_CELL, COLUMN_ROW  }, { COLUMN_CELL, COLUMN_COL  }, { COLUMN_CELL, COLUMN_BOX  }, { COLUMN_ROW,  COLUMN_CELL }, { COLUMN_COL,  COLUMN_CELL }, { COLUMN_BOX,  COLUMN_CELL }, { COLUMN_ROW,  COLUMN_COL  }, { COLUMN_COL,  COLUMN_ROW  }, Cases 1-3 are naked pairs. Cases 4-6 are hidden pairs. Cases 7-8 are X-Wings. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Setting sudoku All times are GMT Goto page Previous  1, 2 Page 2 of 2   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