FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Maximum Minimum sudoku size.          Sudoku Programmers Forum Index -> The mathematics of sudoku View previous topic :: View next topic   Author Message tilps Joined: 19 Jun 2005 Posts: 44 : Items Posted: Sun Jul 24, 2005 10:09 am    Post subject: Maximum Minimum sudoku size. Many people know that there exists a size 18 symmetric sudoku But a different question is what is the sudoku with the most number of clues, of which each clue is important. Given a set of clues, none can be removed and still have a single solution. The highest i've seen so far (but dont have onhand to post) is 34. Edit: given a set of clues, none can be removed and still have a symmetrical board with a single solution, although the other question is also interesting. Last edited by tilps on Mon Jul 25, 2005 9:56 am; edited 1 time in total Back to top tilps Joined: 19 Jun 2005 Posts: 44 : Items Posted: Sun Jul 24, 2005 10:48 pm    Post subject: Code: .1.|9.2|85. .5.|...|... 4..|583|... ---+---+--- ...|.24|57. 78.|6.9|.34 .45|13.|... ---+---+--- ...|216|..9 ...|...|.2. .72|4.8|.6. ...|.27|83. 87.|.53|..4 ...|...|7.. ---+---+--- .9.|.3.|54. .37|2.9|68. .61|.7.|.2. ---+---+--- ..4|...|... 9..|78.|.13 .83|41.|... A couple of examples of size 34. Back to top jaap Joined: 13 Jun 2005 Posts: 24 : Location: NL Items Posted: Mon Jul 25, 2005 6:21 am    Post subject: tilps wrote: Code: .1.|9.2|85. .5.|...|... 4..|583|... ---+---+--- ...|.24|57. 78.|6.9|.34 .45|13.|... ---+---+--- ...|216|..9 ...|...|.2. .72|4.8|.6. Not all of the clues are necessary: Code: ...|..2|85. .5.|...|... 4..|.83|... ---+---+--- ...|...|57. 78.|..9|.34 ..5|13.|... ---+---+--- ...|.16|..9 ...|...|.2. .72|4.8|.6. This is still solvable trivially. The other one also can have many clues removed. I simply put the puzzle in my solver/generator, had it mark the excess clues, and removed them one by one until no were still marked. Jaap http://www.geocities.com/jaapsch/sudoku.htm _________________ 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 7:45 am    Post subject: yes, but its no longer symmetrical. I guess I didnt explain that condition properly. Back to top jaap Joined: 13 Jun 2005 Posts: 24 : Location: NL Items Posted: Mon Jul 25, 2005 8:51 am    Post subject: tilps wrote: yes, but its no longer symmetrical. Ok, I didn't realise. I actually find rotational symmetry hard to spot in puzzles posted on this forum. What is the highest number of necessary clues in without any symmetry constraints? I know the fewest is thought to be 17, but what is the most? _________________ Jaap -- Jaap's Puzzle Page: http://www.geocities.com/jaapsch/puzzles Back to top antony Joined: 22 Jul 2005 Posts: 13 : Items Posted: Fri Jul 29, 2005 2:47 am    Post subject: Just generated this one within a few minutes [edited] even better: Code: grid #1: (36 cells)  . . 8 | . 5 6 | . 3 2  . 6 . | . 1 2 | 5 7 8  . . 5 | . . . | 9 6 .  ------+-------+------  7 . 2 | 1 6 . | . . .  . . . | . . . | . . .  . . . | . 2 5 | 7 . 1  ------+-------+------  . 3 7 | . . . | 2 . .  5 8 4 | 2 3 . | . 1 .  6 2 . | 5 8 . | 4 . . Solution is unique. You can't remove any hint without losing symmetry or solution unicity. It is solvable with simple logic. Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Fri Sep 09, 2005 4:37 am    Post subject: http://www.sudoku.com/forums/viewtopic.php?t=1448 Back to top Rostis Joined: 12 Sep 2005 Posts: 1 : Items Posted: Mon Sep 12, 2005 9:06 pm    Post subject: antony wrote: Code: grid #1: (36 cells)  . . 8 | . 5 6 | . 3 2  . 6 . | . 1 2 | 5 7 8  . . 5 | . . . | 9 6 .  ------+-------+------  7 . 2 | 1 6 . | . . .  . . . | . . . | . . .  . . . | . 2 5 | 7 . 1  ------+-------+------  . 3 7 | . . . | 2 . .  5 8 4 | 2 3 . | . 1 .  6 2 . | 5 8 . | 4 . . Solution is unique. You can't remove any hint without losing symmetry or solution unicity. It is solvable with simple logic. Yea, OK, but what if we skip the symmetry constraint, how many hints can we fit in there? This one obviously has some hints that can be left out then. And how many is really necessary if the solution should be by simple methods? I had my pretty slow random generator work day and night for a week to generate 10+million sudokus and one(!) had 19 hints. I think I have to improve the algorithm to get further than that. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> The mathematics of 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