From jhnieto@my-dejanews.com Tue Feb 16 02:05:32 CST 1999 Article: 235799 of sci.math Path: news.math.niu.edu!husk.cso.niu.edu!vixen.cso.uiuc.edu!logbridge.uoregon.edu!news-peer.gip.net!news.gsl.net!gip.net!newsfeed.cwix.com!204.238.120.130!news-feeds.jump.net!nntp2.dejanews.com!nnrp1.dejanews.com!not-for-mail From: jhnieto@my-dejanews.com Newsgroups: sci.math Subject: Re: Parity of "sliding" puzzle Date: Tue, 16 Feb 1999 02:37:18 GMT Organization: Deja News - The Leader in Internet Discussion Lines: 48 Message-ID: <7aalkt$ldh$1@nnrp1.dejanews.com> References: <36C75B2A.9066B216@rocketmail.com> NNTP-Posting-Host: 206.49.130.5 X-Article-Creation-Date: Tue Feb 16 02:37:18 1999 GMT X-Http-User-Agent: Mozilla/2.0 (compatible; MSIE 3.0; Windows 95) X-Http-Proxy: 1.0 x4.dejanews.com:80 (Squid/1.1.22) for client 206.49.130.5 Xref: news.math.niu.edu sci.math:235799 In article <36C75B2A.9066B216@rocketmail.com>, Peter_Ammon@rocketmail.com wrote: > I plan on programming the classic game where you are given a 4x4 (or > more) board with one piece removed, and you have to organize the pieces > into order (usually to form a picture) by sliding them around on the > board. It seems to me that only half of the possible configurations for > the board will allow it to be solved; either it can be solved, or two > adjacent pieces will be switched and no amount of sliding them around > can fix that. My question is, given a random configuration, how can I > quickly and easily show that it is either solvable or not solvable? > Number the squares from 1 to 15. Associate to each configuration a permutation of 1,2,...,15, reading the numbers from left to right and top to bottom. Let's say that the hole (denoted by *) is "odd" if it is in rows 1 or 3, otherwise it is "even". For example, in 3 6 4 2 1 11 * 7 5 10 9 12 8 13 15 14 the permutation is (3,6,4,2,1,11,7,5,10,9,12,8,13,15,14) and the hole is even. You also need the concept of "parity" of a permutation, which may be defined as the parity of the number of "inversions" (pairs out of order). For example the permutation above has 20 inversions: 3-2, 3-1, 6-4, 6-2, 6-1, 6-5, 4-2, 4-1, 2-1, 11-7, 11-5, 11-10, 11-9, 11-8, 7-5, 10-9, 10-8, 9-8, 12-8 and 15-14, hence it is even. Well, two configurations are mutually accessible if and only if: 1) their permutations have the same parity and their holes too, or 2) their permutations have different parity and their holes too. This holds as well for nXn boards when n is even. For odd n two configurations are mutually accessible if and only if their permutations have the same parity, regardless of the position of the holes. Greetings, Jose H. Nieto -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own