FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    How is this approach to generation?          Sudoku Programmers Forum Index -> Setting sudoku View previous topic :: View next topic   Author Message Ikzann Joined: 03 Jan 2006 Posts: 5 : Items Posted: Wed Jan 04, 2006 2:40 am    Post subject: How is this approach to generation? How wold this work (randomness, speed, etc.)? 1. Start out with generic, static grid 2. Rearrange rows and columns within subgroups randomly (for example, swap rows 6 + 4, 5 + 6, 5 + 6, 4 + 5) 3. Rearrange subgroups of rows/columns randomly (ex. swap rows 1-3 with 4-6, etc.) 4. Relabel randomly yet consistently (ex. 123456789 becomes 759423168) Thanks! Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Wed Jan 04, 2006 10:45 am    Post subject: Ikzann wrote: How would this work (randomness, speed, etc.)? randomness: You would only have solutions of a single class. speed: Generating the grid is not the 'heavy' part of Sudoku setting. If you can find a way to speed up checking the validity of the remaining givens, that would really save time. etc 1: Many generators place random digits on an empty grid, not working towards a known solution, but any solution. For these generators, this method is useless. etc 2: It has been posted (and rejected) before on this forum. Ruud. _________________ Meet me at sudocue.net Back to top dom Joined: 10 Nov 2005 Posts: 42 : Items Posted: Fri Jan 06, 2006 2:25 pm    Post subject: I don't know if Ruud isn't being a little overly pessimistic here. If you removed the same cells with two of your generated grids you would have to solve the puzzle in different ways. (would you agree Ruud?) So this shuffling of the grid is a quick way of generating a different board. Although as Ruud says, shuffling isn't enough to gain access to all of the possible starting grids. You'll need to use a different algorithm for that, such as the forwards/backwards search I've suggested in the Programming Sudoku forum (plug!), or a truly random board search to guarantee that your possible boards are evenly distributed in sudoku space. Also as Ruud says you only generate a starting grid once, most of the generation time is typically spent working out which cells to blank out... _________________ Orangeminds Sudoku http://www.orangeminds.com/sudoku/ Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Fri Jan 06, 2006 3:39 pm    Post subject: dom wrote: I don't know if Ruud isn't being a little overly pessimistic here. If you removed the same cells with two of your generated grids you would have to solve the puzzle in different ways. (would you agree Ruud?) Yes, you would be able to generate many Sudokus by permutating a single base grid. My concern would be the quality of that base grid. How many (significantly) different Sudokus can be generated from it? Is it possible to generate sufficient Sudokus for a variety of difficulty levels, spanning the full spectrum of solving techniques? Before I would decide to use this method, I would certainly test this base grid to see how useful it is, otherwise you'll end up with a lot of Sudokus that look different, but 'feel' the same. Cautious, not pessimistic Ruud. _________________ Meet me at sudocue.net Back to top dom Joined: 10 Nov 2005 Posts: 42 : Items Posted: Mon Jan 09, 2006 10:51 am    Post subject: Quote: How many (significantly) different Sudokus can be generated from it? I guess you've hit the nail on the head Ruud. From personal experience I'd guess that shuffling does actually lead to sudoku which have to be solved in a significantly different way, but I've not written a shuffler yet so I can't confirm that. Although the strangely familiar grid might give us hints here. The same base grid has many 18 clue sudoku, some of which are solvable with trivial methods, some of which require far more complex methods. Do they actually feel different to solve though? Even if they don't, the shuffling might give another dimension to the variance so perhaps they would indeed feel distinct. But who knows, needs testing, and I don't have any spare time. Anyone else tried this? _________________ Orangeminds Sudoku http://www.orangeminds.com/sudoku/ 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 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