准备去长期潜伏，最后和大家探讨一下几个经典的回朔算法

Question

前些天看到了有人发布有关算法的贴子，说来惭愧，本人几乎忘记了如何做回溯了，花了很长时间，不段在草稿纸上模拟，上天不负有心人，最终还是做出了以前做过的几个经典案例，与大家分享一下。下载地址
        /// <summary>
        /// 获取数列
        /// </summary>
        protected void getNumList()
        {            int[] ary = new int[] { 0, 1, 2, 2 };
            ary.CopyTo(ary, 0);
            int s = 3;
            string num = "1234";
            char[] ary_num = num.ToCharArray();
            int n = ary_num.Length - 1;
            int cout = 0;
            string txt = string.Empty;
            while (s >= 0)
            {            loop: if (ary[s] >= n)
                {                    ary[s] = -1;
                    s = s - 1;                }
                else
                {
                    ary[s] = ary[s] + 1;
                    for (int i = s - 1; i >= 0; i--)
                    {
                        if (ary[s] == ary[i])
                        {
                            goto loop;
                        }
                    }
                    if (s == 3 && !txt.Contains(string.Format("{0}{1}{2}{3}", ary_num[ary[0]], ary_num[ary[1]], ary_num[ary[2]], ary_num[ary[3]])))
                    {
                        cout++;
                        txt = txt + "," + string.Format("{0}{1}{2}{3}", ary_num[ary[0]], ary_num[ary[1]], ary_num[ary[2]], ary_num[ary[3]]);
                        Response.Write(string.Format("{0}{1}{2}{3}<br/>", ary_num[ary[0]], ary_num[ary[1]], ary_num[ary[2]], ary_num[ary[3]]));
                    }                    if (s < 3)
                    {
                        s = s + 1;
                    }                }
            }
            Response.Write(string.Format("{1}总数为：{0} 个数列", cout, num));        }
        /// <summary>
        /// 走迷宫
        /// </summary>
        protected void findPath()
        {
            //初使化地图
            int[,] ary_map = new int[8, 12]
            {
                { 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1 },
                { 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1 },
                { 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1 },
                { 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1 },
                { 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 },
                { 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0 },
                { 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1 },
                { 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0 }
            };
            
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 12; j++)
                {
                    Response.Write(ary_map[i, j]);
                }
                Response.Write("<br/>");
            }
            
            //开始询址
            int s = 0;//记录第几步
            int[] st = new int[8 * 12];//记录每步的方向y - 1(上),x + 1(左),y - 1(下),x - 1(右)
            int x = 0;//第几步的x
            int y = 0;//第几步的y
            while (s >= 0)
            {
                //判断方向
                switch (st[s])
                {
                    case 0:
                        y = y - 1;//向上走
                        break;
                    case 1:
                        x = x + 1;//向左走
                        break;
                    case 2:
                        y = y + 1;//向下走
                        break;
                    case 3:
                        x = x - 1;//向右走
                        break;
                }
                //如果碰壁就往回走
                if (st[s] > 4 || x < 0 || y < 0 || x >= 12 || y >= 8 || ary_map[y, x] == 1 || ary_map[y, x] == -1)
                {
                Loop://判断方向，回退到上一步
                    switch (st[s])
                    {
                        case 0:
                            y = y + 1;
                            break;
                        case 1:
                            x = x - 1;
                            break;
                        case 2:
                            y = y - 1;
                            break;
                        case 3:
                            x = x + 1;
                            break;                    }
                    //换一个方向
                    st[s] = st[s] + 1;                    //所有方向都走不通就返回上一步
                    if (st[s] > 3)
                    {
                        st[s] = 0;
                        s = s - 1;
                        if (s > 0)
                            goto Loop;
                    }
                }
                else
                {
                    //将走过的路径设为-1
                    ary_map[y, x] = -1;                    //下一步
                    s = s + 1;
                    if (x == 11 && y == 7)
                    {
                        break;
                    }
                }
            }
            //询址结束
            //输出路径
            x = 0;
            y = 0;
            string txt=string.Empty;
            for (int i = 0; i < s; i++)
            {
                switch (st[i])
                {
                    case 0:
                        y = y - 1;
                        break;
                    case 1:
                        x = x + 1;
                        break;
                    case 2:
                        y = y + 1;
                        break;
                    case 3:
                        x = x - 1;
                        break;
                }
                if (st[i] <= 0)
                {
                    break;
                }
                else
                {
                    txt = (txt == "" ? "" : txt + ",") + string.Format("(x:{0},y:{1})", x, y);
                }
            }
            Response.Write(string.Format("<p>路径为:(x:0,y:0),{0}</p>", txt));
        }

Answer 1

        /// <summary>
        /// 马的走法，从(0,0)走到(3,5)
        /// </summary>
        protected void moveHorse()
        {
            //棋盘
            string txt_form = string.Empty;
            txt_form += "        <table width=\"300\" height=\"150\" border=\"1\" cellpadding=\"0\" cellspacing=\"0\" bordercolor=\"#000000\">\r\n";
            txt_form += "          <tr>\r\n";
            txt_form += "            <td bgcolor=\"#666666\">&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "          </tr>\r\n";
            txt_form += "          <tr>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "          </tr>\r\n";
            txt_form += "          <tr>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td>&nbsp;</td>\r\n";
            txt_form += "            <td bgcolor=\"#666666\">&nbsp;</td>\r\n";
            txt_form += "          </tr>\r\n";
            txt_form += "        </table>\r\n";
            Response.Write(txt_form);
            int[,] ary_map = new int[4, 6];
            int[] st = new int[4 * 6];
            int x = 0, y = 0, s = 0;
            int cout = 0;
            string path = "(x:0,y:0)";
            while (s >= 0)
            {                #region 判断方向
                //判断方向
                switch (st[s])
                {
                    case 0://左上方
                        y = y - 2;
                        x = x + 1;
                        break;
                    case 1://左靠上
                        y = y - 1;
                        x = x + 2;
                        break;
                    case 2://左靠下
                        y = y + 1;
                        x = x + 2;
                        break;
                    case 3://左下方
                        y = y + 2;
                        x = x + 1;
                        break;
                    case 4://右下方
                        y = y + 2;
                        x = x - 1;
                        break;
                    case 5://右靠下
                        y = y + 1;
                        x = x - 2;
                        break;
                    case 6://右靠上
                        y = y - 1;
                        x = x - 2;
                        break;
                    case 7://右上方
                        y = y - 2;
                        x = x - 1;
                        break;
                }
                #endregion                //如果走不通，则进行回朔处理
                if (st[s] > 7 || x < 0 || x >= 6 || y < 0 || y >= 4 || path.Contains(string.Format("(x:{0},y:{1})", x, y)))
                {
                    #region 判断方向，返回上一步
                //判断方向
                Loop:
                    switch (st[s])
                    {
                        case 0://左上方
                            y = y + 2;
                            x = x - 1;
                            break;
                        case 1://左靠上
                            y = y + 1;
                            x = x - 2;
                            break;
                        case 2://左靠下
                            y = y - 1;
                            x = x - 2;
                            break;
                        case 3://左下方
                            y = y - 2;
                            x = x - 1;
                            break;
                        case 4://右下方
                            y = y - 2;
                            x = x + 1;
                            break;
                        case 5://右靠下
                            y = y - 1;
                            x = x + 2;
                            break;
                        case 6://右靠上
                            y = y + 1;
                            x = x + 2;
                            break;
                        case 7://右上方
                            y = y + 2;
                            x = x + 1;
                            break;
                    }
                    #endregion                    //换一个方向
                    st[s] = st[s] + 1;                    if (st[s] > 7)
                    {
                        st[s] = 0;
                        s = s - 1;
                        if (s > 0)
                        {
                            path = path.Remove(path.LastIndexOf('(') - 1);
                            goto Loop;
                        }
                    }                }
                else
                {
                    path = path + string.Format(",(x:{0},y:{1})", x, y);
                    //ary_map[y, x] = -1;//走过的方向打个标志
                    s = s + 1;//进行下一步                    #region 输出结果
                    if (x == 5 && y == 3)
                    {
                        cout = cout + 1;
                        Response.Write(string.Format("方案({0}),共{1}步:{2}<br/>", cout, s, path));
                    }
                    #endregion
                }            }
        }

Answer 2

        /// <summary>
        /// 八王后互不冲突
        /// </summary>
        protected void moveQueen(int num)
        {
            int[] st = new int[num];
            for (int i = 0; i < num; i++)
                st[i] = -1;            int s = 0;
            int count = 0;
            while (s >= 0)
            {
            Loop: 
                st[s] = st[s] + 1;
                if (st[s] > num -1)
                {
                    st[s] = -1;
                    s = s - 1;
                }
                else
                {
                    
                    
                    for (int i = s-1; i >= 0; i--)
                    {
                        if ( st[s] == st[i] || s - st[s] == i - st[i] || s + st[s] == i + st[i])
                        {
                            goto Loop;
                        }
                    }
                    if (s == num - 1)
                    {
                        count = count + 1;
                        string txt=string.Format( "方案({0}):",count);
                        for (int i = 0; i < num; i++)
                        {
                            txt = (i == 0 ? txt : txt + ",") + string.Format("(x:{0},y:{1})", i, st[i]);
                        }
                        Response.Write(txt + "<br/>");
                    }
                    if (s < num - 1)
                        s = s + 1;
                }
                
            }        }