From - Tue Sep 8 13:01:25 1998 From: puzzles@jte.com Newsgroups: rec.puzzles,alt.math.recreational,sci.math Subject: Metapuzzle involving NUMBER PLACE Puzzles Date: Tue, 08 Sep 1998 07:07:20 GMT Organization: Frontier GlobalCenter Inc. A NUMBER PLACE puzzle starts with a 9x9 grid divided into 9 3x3 areas with some of the cells filled with 'clues', that is, a digit from 1 to 9. Typically there are between 27 and 36 clues given. Here is an example from DELL'S BEST OF MATH PUZZLES AND LOGIC PROBLEMS, February 1998: +-----+-----+-----+ |- 5 -|2 1 -|- 7 -| |3 - -|- - 6|9 - 4| |2 - 9|- 3 -|- - 5| +-----+-----+-----+ |- 3 2|- - 1|- 6 -| |- 9 -|4 - -|8 3 -| |7 - -|6 2 -|- - 1| +-----+-----+-----+ |6 2 -|- - 5|- 1 -| |- - 1|3 - -|2 - 6| |- - 8|- 6 2|3 - -| +-----+-----+-----+ The goal is to fill in all the remaining cells so that each row, column and 3x3 area has one of each digit. A puzzle should have only one possible solution. Solution to the above example: +-----+-----+-----+ |8 5 4|2 1 9|6 7 3| |3 1 7|5 8 6|9 2 4| |2 6 9|7 3 4|1 8 5| +-----+-----+-----+ |4 3 2|8 9 1|5 6 7| |1 9 6|4 5 7|8 3 2| |7 8 5|6 2 3|4 9 1| +-----+-----+-----+ |6 2 3|9 4 5|7 1 8| |9 4 1|3 7 8|2 5 6| |5 7 8|1 6 2|3 4 9| +-----+-----+-----+ Although the puzzles typically use numbers, any 9 different letters or other symbols may be used since no math is involved. METAPUZZLE ================================================================ + + -What is the fewest number clues that must + be given in order to have a unique solution? + + Give a proof and an minimum clue example. + ================================================================ Also, -When creating one of these puzzles, how does one go about ensuring that only the minimum information needed to solve the puzzle is given? ADDITIONAL INFORMATION ABOUT N U M B E R P L A C E PUZZLES: DELL publishes some of theses puzzles in their Math and Logic Puzzles magazines. All of their puzzles are always the same -- 4 clues in each of the 9 areas are given for a total of 36 clue numbers, giving more information then is required to reach a unique solution. All their number place puzzles have the same difficulty level -- easy. Once you've solved a few they get repetitive. Some Japanese magazines publish these puzzles and there is also a website -- http://www.pro.or.jp/~fuji/java/index-eng.html -- with 110 puzzles by a Japanese composer, complete with a nice Java implementation. This puzzles are difficulty rated from 1 to 10 stars. (The hard ones are really far more challenging than the easy ones.) The Japanese version is identical except that they have more variety in the number and arrangement of the starting clues. Typically the numbers are arranged in a pleasing way forming a picture or identifiable pattern. This serves several purposes. First, it's just nicer to work on puzzles that look different from each other. Second, it's easier to see which one's you have worked on as they can be recognized at a glance. Third, different arrangements lead to different problems within the puzzle and varying difficulty. The Japanese versions start with different numbers of clues. I've seen some with as many as 36 and as few as 22. Obviously, in general, the fewer clues given, the harder the puzzle. However, the puzzle must contain enough clues so that only one solution is possible. Below is an example of a Japanese Number Place puzzle from a recent Japanese puzzle magazine. (I can't tell you the name of the magazine -- the title is in Japanese and I can't read it.) Notice that the clues are placed symetrically about the vertical axis and roughly form a face. The solution is at the bottom of this post. +-----+-----+-----+ |- 3 -|8 6 4|- 1 -| |- 4 6|5 - 1|3 2 -| |- 5 -|- - -|- 9 -| +-----+-----+-----+ |5 - -|- - -|- - 1| |3 6 -|- 7 -|- 8 9| |- 8 -|- - -|- 7 -| +-----+-----+-----+ |- - 5|- - -|9 - -| |- - 4|6 - 7|8 - -| |8 - -|9 4 5|- - 7| +-----+-----+-----+ (this example is from a Japanese "Picture Logic Mate" aka Paint By Numbers puzzle magazine) Web sites with Number Place puzzles include: -Java and Puzzle World by Hirofumi Fujiwara http://www.pro.or.jp/~fuji/java/index-eng.html Hirofumi has 110 Number Place puzzles here which he rates in difficulty from 1 to 10. The site includes Java implementations of Cross Sums, Paint By Numbers and Sliding Block puzzles. A very good site with great puzzles. -http://www.pluto.dti.ne.jp/~rcn/Java/Puzzle/np.html This site has a Number Place SOLVER that works very well. The site is mostly in Japanese but it's simple enough to figure out how it works. The page includes 11 problems. You can input your own and use it to manually solve a problem or let it solve it partially or completely in an instant. The site also has covers Cross Sums in a similar fashion. -http://www3.osk.3web.ne.jp/~bs1484/np_p1.html -http://www3.osk.3web.ne.jp/~bs1484/np_p2.html Two Number Place puzzles with just 22 clues. -http://altair.prec.kyoto-u.ac.jp/~chihara/java/NumberPlace.html -http://altair.prec.kyoto-u.ac.jp/~chihara/java/NumberPlace1.html Two puzzles, one with 27 and another with 28 clues. Please post information on where to find published Number Place puzzles, both on and off the web. +-----+-----+-----+ |2 3 9|8 6 4|7 1 5| |7 4 6|5 9 1|3 2 8| |1 5 8|7 2 3|4 9 6| +-----+-----+-----+ |5 9 7|3 8 6|2 4 1| |3 6 1|4 7 2|5 8 9| |4 8 2|1 5 9|6 7 3| +-----+-----+-----+ |6 7 5|2 1 8|9 3 4| |9 1 4|6 3 7|8 5 2| |8 2 3|9 4 5|1 6 7| +-----+-----+-----+ (Solution of puzzle from a Japanese "picture logic mate" magazine) ------------------------------- Edward - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Here are two sparse Number Place puzzles, each starting with 20 spaces filled. Both were found in Puzzler magazine from Japan. They are both good challenges, but not horribly difficult - a must for any Number Place fan! +-----+-----+-----+ +-----+-----+-----+ |7 - -|- - -|- - 3| |7 4 -|- - -|- 2 -| |- 2 -|8 - -|- - -| |- - -|- 9 -|- - 1| |- - 9|- 6 -|1 - -| |- - 8|- - 3|- - -| +-----+-----+-----+ +-----+-----+-----+ |- - -|- - 3|- 9 -| |- - -|7 - -|8 - -| |4 - -|- - -|- - 6| |- 1 -|- - -|- 4 -| |- 1 -|7 - -|- - -| |- - 3|- - 2|- - -| +-----+-----+-----+ +-----+-----+-----+ |- - 3|- 5 -|8 - -| |- - -|8 - -|3 - -| |- - -|- - 2|- 1 -| |1 - -|- 5 -|- - -| |8 - -|- - -|- - 7| |- 9 -|- - -|- 7 2| +-----+-----+-----+ +-----+-----+-----+ According to editors at Puzzler magazine, the Number Place record for fewest starting numbers is 18. (The best for a symmetrical arrangement is 20.) Here is an example of 18: +-----+-----+-----+ |- - 5|- - -|- 4 -| |- - -|8 - -|- - 6| |3 - 2|- - 1|- - -| +-----+-----+-----+ |- - -|- - 4|- 2 -| |- - 9|- - -|5 - -| |- 6 -|3 - -|- - -| +-----+-----+-----+ |- - -|- - -|- - 3| |- - -|- - 5|- - -| |- 1 -|- - -|6 8 -| +-----+-----+-----+ By popular demand, here are two more Number Place puzzles from Puzzler in Japan. These are a bit harder than those previously posted. If you want more, I recommend the puzzles on Hirofumi Fujiwara's page: http://kjmcci.kct.ne.jp/~fuji/java/puzzle/numplace/book1/index-eng.html Enjoy. +-----+-----+-----+ |- - -|7 - -|4 - -| |- 3 -|- 9 -|- 2 -| |4 - -|- - 5|- - -| +-----+-----+-----+ |- - 8|- - -|- - 5| |- 9 -|- 3 -|- 7 -| |6 - -|- - -|3 - -| +-----+-----+-----+ |- - -|4 - -|- - 6| |- 7 -|- 2 -|- 9 -| |- - 5|- - 8|- - -| +-----+-----+-----+ +-----+-----+-----+ |6 - -|- - -|- - 3| |- 4 -|- 5 -|- 1 -| |- - -|7 - 2|- - -| +-----+-----+-----+ |- - 7|- 3 -|4 - -| |- 3 -|8 - 4|- 2 -| |- - 9|- 1 -|8 - -| +-----+-----+-----+ |- - -|9 - 7|- - -| |- 5 -|- 6 -|- 7 -| |3 - -|- - -|- - 6| +-----+-----+-----+ Nick Baxter -- From: Nick Baxter - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - I could change this a little , to get an example of 17 with 2 solutions. You can fill in the first 68 entries , and then you can choose ... : +-----+-----+-----+ |- - 5|- - -|- - -| |- - -|8 - -|- 1 6| |3 - 2|- - 9|- - -| +-----+-----+-----+ |- - -|- - 4|- 2 -| |- - 9|- - -|5 - -| |- 6 -|3 - -|- - -| +-----+-----+-----+ |- - -|- - -|- - 3| |- - -|- - 5|- - -| |- - -|- - -|6 8 -| +-----+-----+-----+ -- From: qscgz@aol.com (QSCGZ) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - I've come across a few symmetricals with 20 starting numbers. Here's a variant: 2 2 6 +-----+-----+-----+ |1 - -|- - -|- - 3| 8 |- - -|- 8 -|- - -| |- - 4|- - -|9 - -| +-----+-----+-----+ 2 |- - -|1 - 9|- - -| |- 6 -|- - -|- 7 -| 4 |- - -|7 - 5|- - -| +-----+-----+-----+ |- - 1|- - -|2 - -| 7 |- - -|- 3 -|- - -| |4 - -|- - -|- - 7| +-----+-----+-----+ The external numbers represent the difference between the numbers on the ends of their row or column. That is: 2 2 6 +-----+-----+-----+ |1 w -|- - -|- - 3| 8 |x - -|- 8 -|- - y| |- - 4|- - -|9 - -| +-----+-----+-----+ 2 |- - -|1 - 9|- - -| |- 6 -|- - -|- 7 -| 4 |- - -|7 - 5|- - -| +-----+-----+-----+ |- - 1|- - -|2 - -| 7 |- - -|- 3 -|- - -| |4 z -|- - -|- - 7| +-----+-----+-----+ |x-y| = 8, so x = 9 or 1 and y = 1 or 9. |w-z| = 2, etc What sort of puzzle selection does Puzzler magazine have? Are most or all solvable without knowing Japanese? Are subscriptions available in the US? I just picked up a couple of other Japanese puzzle magazines. Both have several Number Place puzzles including a few 16x16. Even better, both have some overlapping puzzles like this from the September issue of PUZZLE PARADISE: +-----+-----+-----+ +-----+-----+-----+ |- - -|- - -|- - -| |- - -|- - -|- - -| |- - -|1 8 2|- - -| |- - -|7 5 3|- - -| |- - 5|6 - 4|8 - -| |- - 8|9 - 6|7 - -| +-----+-----+-----+ +-----+-----+-----+ |- 2 9|- - -|5 8 -| |- 6 1|- - -|4 2 -| |- 3 -|- 9 -|- 1 -| |- 7 -|- 1 -|- 9 -| |- 8 6|- - -|2 7 -| |- 9 5|- - -|6 7 -| +-----+-----+-----+-----+-----+-----+-----+ |- - 4|3 - 6|- - -|- - -|- - -|4 - 1|8 - -| |- - -|8 4 9|- - -|3 9 2|- - -|3 6 7|- - -| |- - -|- - -|- - -|8 - 5|- - -|- - -|- - -| +-----+-----+-----+-----+-----+-----+-----+ |- 8 1|- - -|6 7 -| |- 7 -|- 5 -|- 4 -| |- 4 3|- - -|9 1 -| +-----+-----+-----+-----+-----+-----+-----+ |- - -|- - -|- - -|9 - 8|- - -|- - -|- - -| |- - -|7 1 4|- - -|7 3 1|- - -|1 3 8|- - -| |- - 1|8 - 6|- - -|- - -|- - -|7 - 2|3 - -| +-----+-----+-----+-----+-----+-----+-----+ |- 9 4|- - -|7 6 -| |- 2 9|- - -|7 8 -| |- 5 -|- 7 -|- 4 -| |- 4 -|- 6 -|- 1 -| |- 7 6|- - -|2 8 -| |- 1 8|- - -|4 3 -| +-----+-----+-----+ +-----+-----+-----+ |- - 7|5 - 2|6 - -| |- - 4|5 - 9|8 - -| |- - -|4 3 1|- - -| |- - -|4 7 3|- - -| |- - -|- - -|- - -| |- - -|- - -|- - -| +-----+-----+-----+ +-----+-----+-----+ Each 9x9 will have a normal solution. Edward -- From: edward@jte.com (Edward Jackman) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - I found 46656 solutions ("rcc9s") , to place 9 queens (or whatever) into a 9x9 square , such that no two queens are in the same row,column or cell. Two such rcc9s are called disjoint , if all their 18 queens are on different squares. A solved NPP (number place puzzle) is nothing but a set of 9 mutually disjoint rcc9s. Now I wrote a program that tried to generate solved NPPs in 9 steps: On each step s : count the number n(s) of rcc9s that are disjoint to all the other previously selected rcc9s , and select one of those disjoint rcc9s at random. some typical outcomes for the n(s) were: 46656,17972,6121,1848,443,96,24,2,1 46656,17972,6200,1716,470,81,10,0,- 46656,17972,6121,1848,443,96,24,2,1 46656,17972,6190,1879,426,96,18,4,1 46656,17972,6021,1784,359,63,4,0,- 46656,17972,6022,1688,383,82,10,0,- 46656,17972,6046,1748,420,82,11,0,- 46656,17972,6096,1680,392,88,14,2,1 46656,17972,6021,1712,306,72,14,0,- 46656,17972,6254,1942,528,122,11,0,- Now I multiplied the n(s) , divided by 9! since the order doesn't matter and got 1.5*10^16 in average. qscgz -- From: qscgz@aol.com (QSCGZ) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Three number place puzzles taken from Gakken Mook Pocket Puzzle 100 Series 20: Pocket Number Place 8 All three are rated (****) meaning difficult. (64) +-----+-----+-----+ |4 - -|3 - 7|- - 8| |- 2 -|- 1 -|- 7 -| |- - 8|- - -|5 - -| +-----+-----+-----+ |- - 2|5 - 8|9 - -| |- 4 -|- - -|- 8 -| |- - 6|1 - 3|7 - -| +-----+-----+-----+ |- - 3|- - -|1 - -| |- 6 -|- 8 -|- 9 -| |2 - -|6 - 1|- - 4| +-----+-----+-----+ (65) +-----+-----+-----+ |- - -|9 1 6|- - -| |- - 3|- - -|1 - -| |- 4 -|- - -|- 9 -| +-----+-----+-----+ |1 - -|- 8 -|- - 7| |5 - -|3 - 9|- - 1| |6 - -|- 2 -|- - 5| +-----+-----+-----+ |- 9 -|- - -|- 4 -| |- - 8|- - -|2 - -| |- - -|4 5 8|- - -| +-----+-----+-----+ (67) +-----+-----+-----+ |- - 5|- 1 -|7 - -| |- 2 -|- - -|- 4 -| |4 - 7|9 - 6|2 - 8| +-----+-----+-----+ |- - 1|- 8 -|4 - -| |7 - -|1 - 4|- - 3| |- - 4|- 9 -|6 - -| +-----+-----+-----+ |6 - 3|8 - 1|5 - 9| |- 5 -|- - -|- 6 -| |- - 2|- 6 -|3 - -| +-----+-----+-----+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Hirofumi Fujiwara Hobbit's Room is a site where Hirofumi Fujiwara has ported some of his puzzles (and made new ones) for the Palm." Hobbit's Room http://hobbit.spire.timedia.co.jp/ Number Place = Sudoku http://hobbit.spire.timedia.co.jp/sudoku/index_e.html - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - (101) Zeit +-----+-----+-----+ |- - -|2 1 -|5 - -| |- - -|- - -|6 9 7| |- 8 3|- - -|- - -| +-----+-----+-----+ |7 - -|4 3 -|- - -| |5 - -|- - -|- - 3| |- - -|- 9 6|- - 1| +-----+-----+-----+ |- - -|- - -|4 2 -| |3 9 6|- - -|- - -| |- - 1|- 5 8|- - -| +-----+-----+-----+ bd=000210500000000697083000000700430000500000003000096001000000420396000000001058000 bd=647219538152384697983675214769431852514827963238596741875163429396742185421958376 +-----+-----+-----+ |- - -|1 - 4|- - -| |- - 1|- - -|9 - -| |- 9 -|7 - 3|- 6 -| +-----+-----+-----+ |8 - 7|- - -|1 - 6| |- - -|- - -|- - -| |3 - 4|- - -|5 - 9| +-----+-----+-----+ |- 5 -|4 - 2|- 3 -| |- - 8|- - -|6 - -| |- - -|8 - 6|- - -| +-----+-----+-----+ bd=000104000001000900090703060807000106000000000304000509050402030008000600000806000 bd=682194357731568924495723861827935146519647283364281579956412738248379615173856492 Nanpure Fan 2004-10 +-----+-----+-----+ |- - -|- - -|8 - 6| |- - 9|- - -|- - -| |- - 6|- 4 2|- - -| +-----+-----+-----+ |- 8 -|1 - -|- - -| |- 1 -|- - -|- 2 -| |- - -|- - 9|- 4 -| +-----+-----+-----+ |- - -|8 3 -|1 - -| |- - -|- - -|9 - -| |2 - 5|- - -|- - -| +-----+-----+-----+ bd=000000806009000000006042000080100000010000020000009040000830100000000900205000000 bd=421597836359618274876342519784123695913456728562789341697834152148275963235961487 Nanpure Fan 2004-10 +-----+-----+-----+ |- 5 -|- - -|- 7 -| |9 - -|6 - 1|- - 8| |- - 6|- 2 -|1 - -| +-----+-----+-----+ |- 6 -|- - 2|- 1 -| |- - 3|- - -|2 - -| |- 4 -|3 - -|- 5 -| +-----+-----+-----+ |- - 4|- 3 -|5 - -| |2 - -|4 - 5|- - 9| |- 3 -|- - -|- 6 -| +-----+-----+-----+ +-----+-----+-----+ |- - -|- - -|- - -| |- - -|- - -|- - -| |- - -|- - -|- - -| +-----+-----+-----+ |- - -|- - -|- - -| |- - -|- - -|- - -| |- - -|- - -|- - -| +-----+-----+-----+ |- - -|- - -|- - -| |- - -|- - -|- - -| |- - -|- - -|- - -| +-----+-----+-----+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - (107) Zeit . . 4 . . . . 8 7 . . . . . 6 . . 3 . . . . 7 2 5 . . . . . 5 . 3 . . 9 2 . . . . . . . 4 6 . . 7 . 1 . . . . . 3 2 5 . . . . 5 . . 9 . . . . . 7 8 . . . . 1 . . bd=004000087000006003000072500000503009200000004600701000003250000500900000780000100 . 2 4 . . 5 6 8 7 . . . . . 6 . . 3 . . . . 7 2 5 . 1 . . 1 5 . 3 . 6 9 2 . . . . 9 . 1 4 6 . . 7 . 1 . . . . 1 3 2 5 . . . 6 5 . . 9 1 . . . . 7 8 . . . 4 1 . . bd=024005687000006003000072501001503069200009014600701000013250006500910000780004100 Y-Wing . 2 4 . . 5 6 8 7 . . . . . 6 . . 3 . Y . . 7 2 5 X 1 . . 1 5 . 3 . 6 9 2 . . . . 9 . 1 4 6 . . 7 . 1 . . . . 1 3 2 5 . . . 6 5 Z . 9 1 . . W . 7 8 . . . 4 1 . . X-Y-Z = 49-96-64 either end of the chain is 4. Therefore W is not 4. Y-Wing W 2 4 . . 5 6 8 7 W . . . . 6 . . 3 W Y . . 7 2 5 . 1 . . 1 5 . 3 . 6 9 2 . . . . 9 . 1 4 6 . . 7 . 1 . . . T 1 3 2 5 . . . 6 5 Z . 9 1 . . . . 7 8 . . . 4 1 . . Y-Z-T = 96-64-49 either end of the chain is 9. Therefore W is not 9. solution 3 2 4 1 9 5 6 8 7 1 5 7 4 8 6 9 2 3 8 6 9 3 7 2 5 4 1 4 7 1 5 2 3 8 6 9 2 3 5 8 6 9 7 1 4 6 9 8 7 4 1 3 5 2 9 1 3 2 5 8 4 7 6 5 4 6 9 1 7 2 3 8 7 8 2 6 3 4 1 9 5 bd=324195687157486923869372541471523869235869714698741352913258476546917238782634195 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - (2005-11-02) FR 8 . . . . 2 . 7 . . 7 . 8 6 . . . 3 . . . 4 . . 2 . . . 1 5 . 2 . . . . . 8 . 1 . 7 9 . . 2 . . . 8 . . . 1 . . 6 . 5 . 8 . 2 3 . . . . . . 1 6 . 2 . . . 1 5 9 . bd=800002070070860003000400200015020000080107900200080001006050802300000016020001590 8 3 . 5 1 2 6 7 . . 7 2 8 6 9 1 . 3 . 6 1 4 7 3 2 . . . 1 5 . 2 6 . . . 6 8 3 1 4 7 9 2 5 2 4 . . 8 5 . 6 1 1 9 6 7 5 4 8 3 2 3 5 . 2 9 8 . 1 6 . 2 8 6 3 1 5 9 . bd=830512670072869103061473200015026000683147925240085061196754832350298016028631590 Y-Wing Chain 8 3 . 5 1 2 6 7 W Z 7 2 8 6 9 1 T 3 . 6 1 4 7 3 2 . . . 1 5 . 2 6 . . . 6 8 3 1 4 7 9 2 5 2 4 . . 8 5 . 6 1 1 9 6 7 5 4 8 3 2 3 5 . 2 9 8 . 1 6 Y 2 8 6 3 1 5 9 X X-Y-Z-T = 47-74-45-54 either end of the chain is 4. Therefore W is not 4. Coloring is another method handling this problem coloring number 4 with w, b, (x not colored): 8 3 w 5 1 2 6 7 b b 7 2 8 6 9 1 w 3 . 6 1 4 7 3 2 . . . 1 5 . 2 6 b b x 6 8 3 1 4 7 9 2 5 2 4 . . 8 5 . 6 1 1 9 6 7 5 4 8 3 2 3 5 b 2 9 8 w 1 6 w 2 8 6 3 1 5 9 b you see that b is impossible (4th row or 9th column) 8 3 4 5 1 2 6 7 . . 7 2 8 6 9 1 4 3 . 6 1 4 7 3 2 . . . 1 5 . 2 6 . . 4 6 8 3 1 4 7 9 2 5 2 4 . . 8 5 . 6 1 1 9 6 7 5 4 8 3 2 3 5 . 2 9 8 4 1 6 4 2 8 6 3 1 5 9 . solution 8 3 4 5 1 2 6 7 9 5 7 2 8 6 9 1 4 3 9 6 1 4 7 3 2 5 8 7 1 5 9 2 6 3 8 4 6 8 3 1 4 7 9 2 5 2 4 9 3 8 5 7 6 1 1 9 6 7 5 4 8 3 2 3 5 7 2 9 8 4 1 6 4 2 8 6 3 1 5 9 7 bd=834512679572869143961473258715926384683147925249385761196754832357298416428631597