日期:2014-05-20  浏览次数:20736 次

一个回溯法问题
4 在一个4*4的小方格(如图所示)中放置8个*号,使得每行每列放且
 仅放两个*号。

  ┌─┬─┬─┬─┐
  │*│*│ │ │
  ├─┼─┼─┼─┤
  │*│ │*│ │
  ├─┼─┼─┼─┤
  │ │*│ │*│
  ├─┼─┼─┼─┤
  │ │ │*│*│
  └─┴─┴─┴─┘

 求出所有的基本解。
求代码和解释

------解决方案--------------------
不会回溯法,换了一个思路,得到每行可能出现的情况,然后统计各位置的坐标的数量.

Java code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Test {
    public static void main(String args[]) {
        ArrayList list = new ArrayList();
        //计算出每一行的所有情况
        for(int i=0;i<3;i++)
        {
            for(int j=i+1;j<4;j++)
            {
                list.add(i+""+j);
            }
        }
        //取四个(每行都可能是相同的位置)出来去比较位置的重复量
        for(int i=0;i<list.size();i++)
        {
            for(int j=0;j<list.size();j++)
            {
                for(int k=0;k<list.size();k++)
                {
                    for(int l=0;l<list.size();l++)
                    {
                        String str = (String)list.get(i)+(String)list.get(j)+(String)list.get(k)+(String)list.get(l);
                        //统计每个字符出现的次数,如果某一个字符数超过3了,那就是不合法的.
                        int length = str.length();
                        Map<String, Integer> xxx = new HashMap<String, Integer>();
                        boolean flag = false;
                        for(int x=0;x<length;x++)
                        {
                            String t = str.charAt(x)+"";
                            if(xxx.get(t)!=null)
                            {
                                if(xxx.get(t)>1)
                                {
                                    flag=true;
                                    break;
                                }else
                                {
                                    xxx.put(t,xxx.get(t)+1);
                                }
                            }else
                            {
                                xxx.put(t,1);
                            }
                        }
                        if(!flag)
                        {
                            System.out.println(str);
                        }
                    }
                }
            }
        }
    }
}