java实现九宫格解锁_Java计算手机九宫格锁屏图案连接9个点的方案总数
(一)問題
九宮格圖案解鎖連接9個點共有多少種方案？
(二)初步思考
可以把問題抽象為求滿足一定條件的1-9的排列數(shù)(類似于“八皇后問題”)，例如123456789和987654321都是合法的(按照從上到下、從左到右、從1到9編號)，解決此類問題一般都用遞歸方法，因為問題規(guī)模較大，且沒有明確的計算方法
(三)深度思考
不難想出下面的簡單思路：
1.先窮舉，再排除不合法結果(過濾窮舉的結果)
大略估計一下復雜度，A99=362880(計算機應該可以接受)，方案總數(shù)不超過A99，也就是說窮舉的結果是A99，再濾去不合法的結果即可，理論上此方法可行
2.按條件窮舉(在窮舉的過程中排除不合法結果)
1>正常思維
---a.選擇起點位置(i,j)
---b.在起點周圍尋找合法終點，規(guī)則如下：(共有12個方向)
------1.上(i - 1, j)--5.左上斜(i - 1, j - 1)---9.左上長斜(i - 2, j - 1)
------2.下(i + 1, j) -6.左下斜(i + 1, j - 1) -10.左下長斜(i + 2, j - 1)
------3.左(i, j - 1)--7.右上斜(i - 1, j + 1)--11.右上長斜(i - 2, j + 1)
------4.右(i, j + 1) -8.右下斜(i + 1, j + 1)-12.右下長斜(i + 2, j + 1)
---c.記錄路徑(起點 + 終點)
---d.判滿，若路徑長度小于9執(zhí)行e步驟，否則執(zhí)行f步驟
---e.終點變起點，返回a步驟
---f.輸出結果(路徑)
2>逆向思維
---a.排除(1.排除已選擇的點2.排除從起點不能到達的點)得到臨時剩余點集
---b.在臨時剩余點集中選擇下一個點
---c.判滿，路徑長度小于9，執(zhí)行d步驟，否則執(zhí)行e步驟
---d.執(zhí)行a步驟
---e.輸出結果(路徑)
P.S.正常思維比較容易理解，逆向思維更容易實現(xiàn)
(四)編碼
[最初想用方案2的逆向思維方案來實現(xiàn)，結果失敗了，原因是遞歸內嵌循環(huán)，程序執(zhí)行軌跡難以捉摸...頭疼良久之后放棄了，改用方案1，簡單粗暴]
[核心代碼類]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ScreenLock {
//將NUM設置為待排列數(shù)組的長度即實現(xiàn)全排列
private int NUM = 0;
private int count = 0;
private String[] strSource;
String string = null;
private static String[] wrongPos = {//各點對應的不能到達的位置
"379","8","179",
"6","#","4",
"139","2","137"};
public ScreenLock(String[] strSource)
{//strSource格式為以逗號分隔的數(shù)字串，如1,2,3,4
//初始化
this.strSource = strSource;
this.NUM = strSource.length;
}
public int getCount()
{
sort(Arrays.asList(strSource), new ArrayList());
return count;
}
private void sort(List datas, List target) {
if (target.size() == NUM) {
StringBuilder sb = new StringBuilder();
for (Object obj : target)
sb.append(obj);
String ans = sb.toString();
if(isValid(ans))
count++;
return;
}
for (int i = 0; i < datas.size(); i++) {
List newDatas = new ArrayList(datas);
List newTarget = new ArrayList(target);
newTarget.add(newDatas.get(i));
newDatas.remove(i);
sort(newDatas, newTarget);
}
}
private boolean isValid(String ans)
{//判斷ans是否合法
for(int i = 0;i < ans.length() - 1;i++)
{
//獲取當前位置的字符的值
int currPos = Integer.parseInt(ans.charAt(i) + "");
//獲取路徑子串
String path = ans.substring(0, i + 1);
//獲取錯誤值
String wrrPos = wrongPos[currPos - 1];
//獲取可變錯誤值
if(currPos != 5)//5不可能變
{
for(int j = 0;j < wrrPos.length();j++)
{
//獲取中間值
String wrong = wrrPos.charAt(j) + "";
int mid = (currPos + Integer.parseInt(wrong)) / 2;
//若中間值已被連接，則錯誤終點可用
if(path.contains(mid + ""))
wrrPos = wrrPos.replace(wrong, "#");
//若下一位是錯誤值則ans不合法
if(wrrPos.contains(ans.charAt(i + 1) + ""))
return false;
}
}
}
return true;
}
}
[測試類]
public class CountLockPlans {
public static void main(String[] args) {
//計算手機九宮格鎖屏圖案連接9個點的方案總數(shù)
String s = "1,2,3,4,5,6,7,8,9";
String[] str = s.split(",");
ScreenLock lock = new ScreenLock(str);
int num = lock.getCount();
System.out.println("連接9個點共有 " + num + " 種方案");
}
}
(五)運行結果
連接9個點共有 62632 種方案【此結果是錯的，詳情見最下方第(十)點】
(六)程序正確性檢驗
1.能否生成1-9的全排列？
注釋掉無關代碼，直接輸出所有全排列，同時計數(shù)，結果無誤(全部輸出需要17秒左右)
2.isValid()方法是否能夠正確判斷方案的合法性？
單獨調用isValid()傳入各種參數(shù)測試，結果無誤
3.算法邏輯是否無誤？
求排列的同時過濾不合法解，邏輯無誤
[綜上，理論上輸出的結果是正確的]
(七)答案正確性確認
上網(wǎng)找找有沒有人算出結果，濾去所有看起來不靠譜的答案，選定果殼網(wǎng)答案(據(jù)說用了Mathematica，乍看高上大)
文章中的解決思路也是：合法方案數(shù) = 全排列總數(shù) - 不合法方案數(shù)
仔細看過文章后發(fā)現(xiàn)原文的結論可能是錯的(雖然不知道其具體算法)
1.從原文的貼圖可以看到先求出了方案總數(shù)985 824(這個我們不必關心，只需要關注連接9個點的計算結果就好)
2.原文貼圖記下不能直接連的點對(和我們的wrongPos數(shù)組作用類似，用來排除)
3.接著往下看是：根據(jù)上一步的點對生成所有不合法方案(仍然不知道具體是怎么算的，但是這里肯定存在漏洞)
原作者的思路應該是按照相鄰點來判斷生成不合法方案(例如：假設第一位是1那么如果第二位選擇3，則以13開頭的所有方案全部PASS掉)
不難發(fā)現(xiàn)這樣一個BUG：第一位選擇2，第二位選擇1，那么第三位能不能選擇3呢？
實際情況是Yes，但如果按照上面假設的判斷方法則是No，因為(1,3)屬于不合法點對！
這就又出現(xiàn)新問題了，因為我們發(fā)現(xiàn)所謂的不合法點對好像是一個動態(tài)的集合，如果中間點被選了，那么非法點對就變成合法的了(例如2被選了之后1可以和3連接，3和1也可以連接)
我們的算法會不會存在這個問題呢？
private boolean isValid(String ans)
{//判斷ans是否合法
for(int i = 0;i < ans.length() - 1;i++)
{
//獲取當前位置的字符的值
int currPos = Integer.parseInt(ans.charAt(i) + "");
//獲取路徑子串
String path = ans.substring(0, i + 1);
//獲取錯誤值
String wrrPos = wrongPos[currPos - 1];
//獲取可變錯誤值
if(currPos != 5)//5不可能變
{
for(int j = 0;j < wrrPos.length();j++)
{
//獲取中間值
String wrong = wrrPos.charAt(j) + "";
int mid = (currPos + Integer.parseInt(wrong)) / 2;
//若中間值已被連接，則錯誤終點可用
if(path.contains(mid + ""))
wrrPos = wrrPos.replace(wrong, "#");
//若下一位是錯誤值則ans不合法
if(wrrPos.contains(ans.charAt(i + 1) + ""))
return false;
}
}
}
return true;
}
從上面的代碼不難看出我們的算法已經(jīng)考慮到了這樣的情況(動態(tài)修正wrrPos)
(八)思考延伸
按照這樣的方法，我們不難算出一共有多少種方案(從四個點到九個點)，在此作簡單分析：
1>9個點和8個點的數(shù)目應該相等(前8位數(shù)都定了，最后一位也就不能變了)
2>9個點和7個點的數(shù)目應該是2倍關系(前7位數(shù)定了，后兩位只有兩種排列方式，如果去掉后2位則前7位數(shù)有一半重復了)
...
設總方案數(shù)為 num，連接 i 個點的方案總數(shù)為 n( i )，例如n( 9 ) = 62632
則：1式：num = n( 4 ) + n( 5 ) + n( 6 ) + n( 7 ) + n( 8 ) + n( 9 )
2式：n( 8 ) = n( 9 ), n( 7 ) = n( 9 ) / 2, n( 6 ) = n( 9 ) / 6, n( 5 ) = n( 9 ) / 24, n( 4 ) = n( 9 ) / 120 [規(guī)律：n( i ) = n( 9 ) / A(9 - i)(9 - i)]
把2式帶入1式即可求得方案總數(shù)，在此不再贅述
(九)總結
探索過程中雖然走了很多彎路，但也有不少收獲，例如動態(tài)不合法判斷的BUG是在嘗試方案2時發(fā)現(xiàn)的，雖然方案2失敗了，但避免了在方案1中出現(xiàn)類似的問題
只要思路明晰，敢于嘗試，絕對沒有plain try
(十)BUG修正
文中對果殼網(wǎng)算法提出的質疑是錯誤的，原文結果是對的
經(jīng)過驗證，本文算法存在BUG，信息如下：
當前路徑是 12345687
錯誤原因是下一位 9被錯誤值#39包含
錯誤串為 123456879
BUG分析：出現(xiàn)這個BUG的原因是對自己的算法太過自信，設計算法的時候過分考慮了算法復雜度，省掉了一個不能省的循環(huán)(應該先動態(tài)修改wrrPos再對結果進行判斷，原算法把二者放在一個循環(huán)里了)
現(xiàn)對isValid方法修改如下：
private static boolean isValid(String ans)
{//判斷ans是否合法
for(int i = 0;i < ans.length() - 1;i++)
{
//獲取當前位置的字符的值
int currPos = Integer.parseInt(ans.charAt(i) + "");
//獲取路徑子串
String path = ans.substring(0, i + 1);
//獲取錯誤值
String wrrPos = wrongPos[currPos - 1];
//獲取可變錯誤值
if(currPos != 5)//5不可能變
{
for(int j = 0;j < wrrPos.length();j++)
{
//獲取中間值
String wrong = wrrPos.charAt(j) + "";
int mid = (currPos + Integer.parseInt(wrong)) / 2;
//若中間值已被連接，則錯誤終點可用
if(path.contains(mid + ""))
wrrPos = wrrPos.replace(wrong, "#");
}
//若下一位是錯誤值則ans不合法
if(wrrPos.contains(ans.charAt(i + 1) + ""))
return false;
}
}
return true;
}
[與原算法唯一的區(qū)別是把if判斷語句從循環(huán)里拿出來了，當時想法是為了節(jié)省一個循環(huán)...結果，哎...]
修正后運行結果：
連接9個點共有 140704 種方案
結論：果殼網(wǎng)的結論是正確的！之前對其內部算法的猜測可能有誤，實屬抱歉。
總結
以上是生活随笔為你收集整理的java实现九宫格解锁_Java计算手机九宫格锁屏图案连接9个点的方案总数的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 实录 | 计算未来轻沙龙：人工智能前沿与
- 下一篇： APP自动化--元素操作之九宫格解锁密码