![]() ![]() See method check_for_last_in_row_col_3x3. See method check_for_single_occurances in my code.Īlso, if in any row/col/3x3 square, eight of the cells have been solved with a single remaining question mark, then it must be the missing nineth digit. So, if a digit only appears on the candiate list of a single cell in any row/col/3x3 square, then the digit must be in that cell (and the other candiates for that cell removed). Solving - Step Two - EasyĮach digit must appear once (and only once) in each of the nine rows, nine columns, nine 3x3 sub-sqaures. Note that if you reduce any cell's list of possibilites to none, then you have made a mistake - or possibly been given an impossible puzzle. This may, of course, cause other cells to become solved - so we would also have to update the candidate lists for all the other cells in that row/col/3x3 square. When any cell is solved, then that number can be removed from the candidate lists for all the other cells in the same row, column or 3x3 square. I decided to store the 81 cells as a list of lists (the closest I could get to a 9x9 array in simple Python). ![]() In this setup, a cell is "solved" when its list of candidates is just one number. If you are using a recent version of Python it might be more efficient to use a set object instead of a list. To me, this lead to an obvious way to store the information in python - for each of the 81 cells, I would have a python list of the possible candidates (as integers). In each empty grid square (or cell), they write down all nine digits (very small!) and then cross out those which are not allowed due to existing solved squares. ![]() Most "introductions" to solving Sudoku will generally discuss or use what I call "candidate lists". How to represent Sudoku Puzzles in Python They use a full stop (period) for an unknown entry. These are simple text files, with one line of 81 characters per puzzle. top2365 - A set of 2,365 "hard" puzzles.top95 - A set of 95 "hard" puzzles, their favoured benchmark set.subig20 - A very very large set of puzzles.msk_009 - A set of 1011 random (mostly "easy") puzzles.So, where can we find lots of (hard) Sudoku puzzles to test with? It turns out there is an active group on this web forum and they have compiled a whole bunch of test puzzles ( hosted here) including: Of course, any good programmer should test their handy work. Neil reported it took him about three hours to write his solver, mine took a similar time but I was distracted by trying to solve a very nasty puzzle I found online - which I now suspect to be impossible (or at least, ambigous). My Python Sudoku solver is available to download here. I'm sure there are other good sites out there, but that's more than enough links! MotivationĪnyway, after reading Solving Sudoku in the Autumn 2005 issue of Warwick the Magazine (catchy title!) by Psychology lecturer Dr Neil Stewart, I finally got round to trying to solve Sudoku with Python. There is also this Sudoku Dictionary, and Dan Rice's Sudoku Blog which includes puzzles to try and discussions of tactics etc. There are more tactics pages available of course, for example by Simon Armstrong and Angus Johnson. Paul Stephens has a very nice introduction site, Sudoku Paulspages, which includes a rather detailed description of some basic tactics for How to solve Sudoku. Other (mis)spellings include So Duko, Soduko and Suduko. The puzzle was introduced in the USA as Number Place, and later became popular in Japan as Nanpure or Sudoku - an abbreviation of suji wa dokushin ni kagiru ( only single numbers allowed), which is tradedmarked in Japan by Nikoli. Congratulations to Carol Vorderman of "Countdown" fame for cashing in early with her book. To those of you unfamilar with a Sudoku puzzle, they are a logic puzzle that has recently (2005) swept the UK and US, appearing in most newspapers alongside the crosswords and other diversions. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |