当前位置: 代码迷 >> J2SE >> 一个回溯法有关问题
  详细解决方案

一个回溯法有关问题

热度:185   发布时间:2016-04-24 02:25:11.0
一个回溯法问题
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);                        }                    }                }            }        }    }}
  相关解决方案