FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Another case of avoiding trial/error          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message tilps Joined: 19 Jun 2005 Posts: 44 : Items Posted: Wed Jul 20, 2005 2:45 pm    Post subject: Another case of avoiding trial/error While researching improving the performance of my sudoku generator i came upon the following position. (and lots more like it) Code: .......1. ....5.2.. .783..6.. 8.3...... ..21863.. ......4.6 ..1..879. ..4.2.... .3....... row 6 column 4 cannot be a 7 (just down left from the centre 8), but my program cannot generate logic to prove this fact. Is this situation an example where elimination of a possibility Requires trial/error or is the constructive logic required just so hiddeously complex that my program doesnt go near it? Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 20, 2005 2:54 pm    Post subject: First of all, the problem you posted doesn't have a unique solution. Having said that, you can actually prove that (6,4)<>7. You need a triple forcing chain, however. Code: 234569  2459    569      | 246789  4679    2479     | 589     1       345789  13469   149     69       | 46789   5       1479     | 2       347     34789    12459   7       8        | 3       149     1249     | 6       45      459      -------------------------+--------------------------+------------------------- 8       6       3        | 4579    479     4579     | 159     257     12579    4579    459     2        | 1       8       6        | 3       57      579      1579    159     579      | 2579    379     23579    | 4       8       6        -------------------------+--------------------------+------------------------- 256     25      1        | 456     346     8        | 7       9       2345    5679    8       4        | 5679    2       13579    | 15      356     135      25679   3       5679     | 45679   14679   14579    | 158     2456    12458    Found a forcing chain: (8,1)=7 => (9,3)<>7 => (6,3)=7 => (6,4)<>7 (8,4)=7 => (6,4)<>7 (8,6)=7 => (8,6)<>3 => (6,6)=3 => (6,6)<>2 => (6,4)=2 => (6,4)<>7   - Remove 7 from (6,4) Back to top tilps Joined: 19 Jun 2005 Posts: 44 : Items Posted: Wed Jul 20, 2005 10:55 pm    Post subject: Should have mentioned that I know it doesnt have a unique solution. Its from the middle of the generation phase. I was trying to generate puzzles iteratively, by only placing numbers onto places which are still possible after the previous phase. However, I was producing problems which were unsolvable, much to my distaste. hrmm, the removal of the 7 must not result in progress, or I would have found this myself during my followup testing. Looks like I should seperate n-tupple checking (where n>2) from increased lookahead. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Solving 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