import java.util.ArrayList;
创新互联专注于企业成都营销网站建设、网站重做改版、凉州网站定制设计、自适应品牌网站建设、H5场景定制、购物商城网站建设、集团公司官网建设、成都外贸网站建设、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为凉州等各大城市提供网站开发制作服务。
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import java.util.Stack;
public class T {
private static final int[][] MOVES = new int[][] { { -2, 1 }, { -1, 2 },
{ 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 }, { -1, -2 }, { -2, -1 } };
private static final int SIZE = 8;
private static final int BASE = SIZE + 4;
private static int[][] board;
private static NeighborComparator neighborComparator = new NeighborComparator();
public static void main(String[] args) {
board = new int[BASE][BASE];
for (int r = 0; r BASE; r++) {
for (int c = 0; c BASE; c++) {
if (r 2 || r BASE - 3 || c 2 || c BASE - 3) {
board[r][c] = -1;
}
}
}
int row = 2 + new Random().nextInt(SIZE);
int col = 2 + new Random().nextInt(SIZE);
solve(row, col);
}
private static void solve(int r, int c) {
StackCell stack = new StackCell();
int count = 1;
Cell cell = new Cell(r, c, neighbors(r, c));
stack.push(cell);
board[r][c] = count++;
while (!stack.isEmpty()) {
if (stack.size() == SIZE * SIZE) {
break;
}
cell = stack.peek();
if (cell.nextNeighbor cell.neighbors.size()) {
int[] neighbor = cell.neighbors.get(cell.nextNeighbor);
r = neighbor[0];
c = neighbor[1];
board[r][c] = count++;
stack.push(new Cell(r, c, neighbors(r, c)));
cell.nextNeighbor++;
} else {
stack.pop();
board[cell.r][cell.c] = 0;
count--;
}
}
if (stack.size() == SIZE * SIZE) {
print();
} else {
System.out.println("无解");
}
}
private static class NeighborComparator implements Comparatorint[] {
public int compare(int[] a, int[] b) {
return a[2] - b[2];
}
}
private static Listint[] neighbors(int r, int c) {
Listint[] neighbors = new ArrayList();
for (int[] m : MOVES) {
int x = m[0];
int y = m[1];
if (board[r + y][c + x] == 0) {
neighbors.add(new int[] { r + y, c + x, countNeighbors(r + y, c + x) });
}
}
Collections.sort(neighbors, neighborComparator);
return neighbors;
}
private static int countNeighbors(int r, int c) {
int num = 0;
for (int[] m : MOVES) {
if (board[r + m[1]][c + m[0]] == 0) {
num++;
}
}
return num;
}
private static void print() {
for (int i = 2; i board.length - 2; i++) {
for (int j = 2; j board[i].length - 2; j++) {
System.out.printf("%2d ", board[i][j]);
}
System.out.println();
}
System.out.println();
}
private static class Cell {
int r;
int c;
Listint[] neighbors;
int nextNeighbor = 0;
public Cell(int r, int c, Listint[] neighbors) {
this.r = r;
this.c = c;
this.neighbors = neighbors;
}
}
}
编者按】吴峰光，Linux 内核守护者，学生时代被同学戏称为“老神仙”，两耳不闻窗外事，一心只搞 Linux。吴峰光的 Linux 内核之路，是天赋、兴趣、耐心、坚持的综合，这从一个补丁前后迭代了 16 个版本后还进行了重写和简化便可一窥。本期《开源英雄》，让我们一起走进吴峰光的技术人生。
采访 | 刘韧、李欣欣
作者 | 李欣欣 责编 | 唐小引
出品 | 《》编辑部
2011 年 4 月 4 日，旧金山，Linux 存储与文件系统、内存管理研讨会（LSF/MM）上，大家正在讨论吴峰光和 Jan Kara 的代码哪个进入内核更合理。此时，远在上海的吴峰光很焦急，像是在等待一场命运对他的判决……结果，捷克人 Jan Kara 获得了多数人的支持。这一集体决策的基调，怕是很难翻转。“我当时真的很失落。”吴峰光说。
Jan Kara 的补丁更合 Andrew Morton（Linux 内核开发者群领导者之一，被称为 Linux 内核守护人）的胃口，是因为多数人认为其方案更简单，一目了然。而吴峰光在方案中深究内核脏页平衡（balance_dirty_pages）偶发的长时间阻塞问题，他们认为是多此一举，他们觉得用户根本无法感知这个内核内部的细微差别，可忽略不计。
时间倒回到 2008 年，31 岁的吴峰光在 Intel 着手优化回写算法。Jan Kara 是 ext3 文件系统的维护者，在开始的头两年，他和吴峰光互相审核回写补丁。2011 年 2 月，在吴峰光发的第六个版本遇到困难，几近搁浅，突然，Jan Kara“乘虚而入”，他简化了目标，提出了更简单的方案，并独立更新了两个版本。
半路杀出程咬金，一个竞争者出现了。
竞争一度很激烈，两人争分夺秒……吴峰光一方面很自信，另一方面又感觉到困难重重：“我认为这个东西本质上是‘控制算法’的问题。其实我是控制专业出身，更有优势。”然而，“真的很难，为了兼顾多重指标，我选择了高难度的算法设计，因而屡屡遭遇技术难题，进展缓慢，甚至需要重构算法，两次推倒重来。”
Peter Zijlstra 是吴峰光的代码复审人，作为 Linux 的四个重要子系统模块的维护者，他以局外人的身份试图理解吴峰光的代码，他先找了本控制理论的书看，看完书后能看懂吴峰光的算法，但依然难以理解动态行为。“我的确贴了很多动态响应曲线图，那是很不好琢磨的一些事情。”吴峰光说。
吴峰光和竞争者 Jan Kara 两种方案相持不下……就在吴峰光即将放弃，打算按大家的意愿把他一些好的东西嫁接到 Jan 的方案之上时 ，他意识到自己方案虽然复杂，但经过大量测试铺垫，趋于成熟；而 Jan 的方案是“未经考验”的简单，很难改进为支持理想中的其它目标（比如 Low Latency）。吴峰光决定背水一战。但是，大家似乎并未觉得他的方案有“不可比拟的优势”，吴峰光又一次陷入了困境。
为了加速推进，Linux 社区决定召开会议，现场评议。结果我们在文章开头都知道了。吴峰光很不甘心，他反复琢磨，想到在一个重要的场景下，竞争者的代码束手无策，他的代码应付自如。第二天，吴峰光给几位核心维护者发邮件，图文并茂，一个星期内，吴峰光连续发了 20 多封邮件深入讨论，为了让大家理解其方案的内在原理中无法拒绝的收益，他用了很多数据和动态图。几天之后，吴峰光收到 Jan Kara 的邮件，他承认吴峰光的代码处理方式有其优越之处。此后，Jan Kara 偃旗息鼓，吴峰光继续完善代码。
2011 年 10 月，布拉格，Kernel Summit 会议上，大家再次讨论吴峰光的代码方案。此时，他的代码已经更新到第 12 个版本。直到 2011 年 11 月 6 日，吴峰光的 IO-less writeback 补丁集最终被 Linus Torvalds（以下简称 Linus）合入了内核主线。这不是吴峰光的代码第一次合进 Linux 内核，也不是吴峰光经历的第一次“好事多磨”。
打开网易新闻 查看精彩图片
吴峰光和 Linux 之父 Linus Torvalds
时间再倒回 2005 年，合肥，中国科学技术大学（以下简称中科大），28 岁的吴峰光正在读博士二年级。每隔几周，他就会更新一个版本到 Linux 内核社区，起因是他在 863 项目里搭建高性能流媒体服务器时，遇到并发能力不足的问题，经过抽丝剥茧的排查后，发现其根本原因是内核预读算法没有按预期检测出视频流和音频流两者交织的顺序读。吴峰光随即动手对预读算法进行优化，接着，他顺手把补丁提交给 Linux 社区，其深层的动机源自于他想让世界上更多的人享受到改进，那样，“技术”就产生了实用的价值。
吴峰光在 Linux 社区连续更新了 5 个版本，无人回应。他的心一直悬着，他认为这个问题必须有人解决。直到 2005 年 10 月 10 日，吴峰光收到一封抄送给他的内部邮件，是技术骨干 Ingo Molnar 对 Linux 内核“看门人”Andrew Morton 说：“这个补丁还不错，你是不是看下？”Andrew Morton 回：“是吧，其实我也注意到。只是我最近没时间，在忙……”然后，Andrew Morton@另外两个人问：“是否可以帮看下？”
读完邮件，吴峰光感觉有戏！他心里一直悬着的石头落地了，更有干劲了。“这事我肯定能给它干到 100 分！”“能通过社区重重考验的才是靠谱的研究成果。是否进入内核是 0 和 1 的价值差别。所以一定要进内核。”
接着，吴峰光收到来自世界各地、各种背景、有不同专业经验的技术高手的反馈。有着深不可测耐心的吴峰光一遍又一遍地修改版本，哪怕一次又一次推翻重写也毫无怨言。每更新一个版本，吴峰光都需要不断做实验测试、分析论证、总结复盘，再发图文到 Linux 社区，供社区成员们公开讨论。“我对任何意见都来者不拒，你们说改什么我就改什么，我把它改进到你们没话可说为止。”“事情不怕难，就怕认真。既然做了这件事，就把相关问题一次性彻底解决掉，之后就不用有人再为此费力了。”吴峰光继续改进，提交了第 16 个版本。在通过了社区的几个审核流程后，他的代码眼看就要进入 Linux 核心，只差最后一步，等待 Andrew Morton 的最后提交操作。
几个星期后，吴峰光意外收到 Andrew Morton 的邮件：“我受不了了，你的补丁越来越复杂了，我不能把它合进 Linux 内核里。”这对吴峰光无疑是个晴天霹雳。有着深不可测耐心的吴峰光又开始反思，又一次重写和简化了代码，直到 Andrew 愉快接受。
2007 年 7 月 19 日，吴峰光打开电脑，整个屏幕被 Andrew Morton 发出的一连串邮件占满，每一个邮件代表一个补丁。接着，Andrew Morton 把补丁集发给 Linus，然后从 -mm tree 里移除消息。至此，提升 IO 性能的文件预读算法代码被 Linux 官方正式接纳。
这一天，对吴峰光来说意义重大，历经一波三折，前后写了 16 个版本，到此时，功德圆满。但他没有与任何人分享，也没有庆祝，吴峰光独自怀揣着这份欢喜，如平日一样。
自此之后，吴峰光一发不可收拾，在 Linux 内核开发的路上披荆斩棘，完成了 readahead、writeback、hwpoison、0day/LKP、 NVDIMM 等 Linux 项目，横穿了他十四年从博士到英特尔的学习和职业生涯。
学习上开窍
刚上小学的吴峰光，身体不好、学习差。到了三年级，老师有意把吴峰光调到跟班上学习最好的学生坐同桌，帮助他的学习。他像突然开了窍，从此，无论学什么，都能轻松拿第一名。
打开网易新闻 查看精彩图片
孩提时代的吴峰光
1977 年 11 月 7 日，吴峰光出生在浙江金华市浦江县的一个小山村。父母务农，每天凌晨 3 点，天还黑着，他们起床开始一天的劳作，挖沙、挖土方、种菜、卖菜……什么脏活累活都做。日复一日，早出晚归。吴峰光的父亲总是铆足了劲，一个人干几个人的活儿。他经常说一句话：“有力气不花，过期作废。”到了冬天，天寒地冻，吴峰光的父母经常在雪地里扒菜，双手被冻，肿得像馒头一样，南方的田间湿气很重，经常在土里劳作的双手会常年开裂，溃烂……到了晚上，劳累了一天的父母回到家里，煤油灯点起来，豆大点的火苗在屋里忽明忽暗地跳跃，吴峰光经常看到他们坐在椅子就已经睡着了……
学习上，父母未曾管教吴峰光，只是常把“考不上大学，就下地干活”挂在嘴边。吴峰光心里明白自己要好好学习，要争气。父亲是个严肃的人，不怒自威，虽从没打过他，但发脾气时气势磅礴，吴峰光很害怕，从来不敢忤逆他。好在吴峰光从小性格安静，能坐得住学习，倒是让父母很省心。
1984 年，7 岁的吴峰光在本村的大溪中心小学上一年级，他长相很憨，胖嘟嘟的。“我那时身体不好，经常流鼻涕，学习成绩也不好。”同学们叫他“蝌蚪”，在浦江话里的意思就是说一个人很“憨傻”。直到吴峰光上了三年级，学习上发生了转机。
小吴峰光喜欢在自家屋后的水渠抓小鱼、小虾 ，跑到大水渠和池塘洗澡。每年暑假，一家人走很远的山路去外婆家，每次快走到村口时，他远远看见两棵像巨大伞盖一样的老樟树矗立在路口，像是站岗的哨兵，他心里便十足地开心，这意味着马上要见到外婆了。
小山村背靠茶山，每次到了采茶的季节，村里人星星点点分散在茶山各处，互相遥望，有人扯着嗓子唱了一句山歌，对面的采茶人来和应，这样的劳动场景让小吴峰光感受到集体劳动欢乐的气氛。夏天，山里的各种水果也熟了，西瓜、桃子、梨……一茬接一茬能吃整个暑假。吴峰光欢乐又轻松的小学时光很快就过去了。
打开网易新闻 查看精彩图片
1989年，吴峰光高小毕业升入中学
1989 年，吴峰光被浦江第二中学录取。小学三年级时的好状态持续了吴峰光的整个中学阶段。他心无旁骛地投入学习，继续轻松拿第一名。浑身上下都充满活力，意气风发，他总是跑着去上学，放学后跑着回家，超过一个又一个同学。“我很喜欢这种感觉。”
中学的课堂上，跟班的老师们有时间与学生个人互动，这让吴峰光感觉很亲近，遇到对他好又有教学魅力的老师，吴峰光的那门课的成绩自然就好。家里条件有限，课余时间，吴峰光喜欢去邻居家看书，连环画、学习类期刊。到了初中，则看起了金庸、梁羽生的武侠小说。
一本书看一周，掌握了 C 语言
高二暑假，16 岁的吴峰光人生中第一次出远门，他被老师选中去杭州参加物理竞赛的培训。在杭州的一家书店里，他翻到一本谭浩强的《C 语言程序设计》，买回来后看了一周，便掌握了 C 语言要点。整个暑假，他的注意力被计算机吸引，物理竞赛不了了之。
1992 年，中考后，吴峰光被当地最好的浦江中学录取。在这所全县掐尖录取学生的学校里，吴峰光很快感受到了压力，原本在初中毫不费力稳居第一的他现在却在班上是中游位置。他只有在课后再加把劲儿学习。半年后，吴峰光重回第一名，之后一直霸榜，成绩有时甚至远超第二名。
吴峰光的中考物理成绩是 100 分，高中物理老师看好他，有意培养，选他当物理课代表，派他去杭州上物理竞赛培训班……直到他的兴趣在杭州悄然发生了转向。暑假回家后，吴峰光把主要时间和精力都花在自学计算机上，无暇顾及正课，原本稳居第一名的成绩开始变得飘忽不定。
高二，学校有了机房。吴峰光第一次接触苹果 II 电脑，学习简单编程。计算机老师为了统计学生成绩编写了一个 BASIC 程序，在机器里运行半天的时间才能统计出成绩排名结果。这颠覆了吴峰光的认知——电脑这么快，为什么还需要这么长时间？
他开始着手优化老师的算法，跳过老师先排序的方法，直接统计每个分数出现的次数，再做累加，很快得出学生成绩降序排名结果。从那以后，计算机老师给“很喜欢的学生”吴峰光配了把机房钥匙。
到了高三，吴峰光的身体又不行了，他日常有气无力，精神涣散。他一边吃药一边学习，勉强撑到高考。高考吴峰光考了 600 多分，是县里前几名，可圈可点的是物理和化学两门成绩。“物理能考好，得益于我高二暑假时去杭州上物理竞赛培训班，老师们的赛题讲解打通了我学习物理的任督二脉，之后哪怕遇到再难的题，我都能轻松解答。”“化学老师是我的班主任，每次上他的课我都战战兢兢，他一进教室就在黑板上写一道题，然后随机叫三个学生上台解题。这招真的很厉害！我们不得不做好课前预习。”
中科大的招生老师找到吴峰光，问他：“愿不愿来中科大？”吴峰光就在志愿表上填了中科大。随后，他被录取到第二志愿“自动控制专业”，与心仪的第一志愿“计算机专业”失之交臂。
自学 Linux
1999 年，合肥，中科大，男生宿舍楼，606 号寝室。22 岁的吴峰光默默站在他的同学弓岱伟的身后，看着弓岱伟在笔记本上噼里啪啦地敲击着键盘，娴熟地操作 Linux 控制台。他边心生羡慕，边像海绵一样快速学习吸收。“我后来觉得这是最理想的学习方式，有个师傅带我飞奔。”
1995 年，18 岁吴峰光第一次坐火车，从老家到合肥的中科大，这是他人生中第二次出远门。一路上的奔波劳累，导致旧疾复发，吴峰光在医院住了几个月，第一学期勉强读完，为了调理巩固身体，他又休学了一年。到了第二个学期，吴峰光被顺延至下一届的 96 级，继续学业。
中科大每年招生很少，本科 5 年制的培养周期比其他大学要长一年，吴峰光和同学们的学习更加扎实。吴峰光说：“从专业方面，我所在的自动化学科分为两大类：一类是计算机知识，五花八门，像 C 语言、数据库、Unix 操作系统等；另一类是各种理论知识，像数学、物理等，理科是科大的优势学科，课程设置比其他学校更难。”
打开网易新闻 查看精彩图片
本科时期某个大雪天，吴峰光和同学梁家恩（云知声创始人）于中科大校园内合影
进入地处偏僻但高手如云的中科大后，吴峰光一头扎进学习里，两耳不闻窗外事。一学期后，吴峰光的成绩从入学时班里的中游水平上升到第一名的位置。他被同学们戏称为“老神仙”，形容他不食人间烟火、心中自有丘壑的超脱个性。计算机依然是吴峰光最着迷的东西。他和室友们合伙买了台计算机，放在宿舍里四个人轮流使用。
1999 年，大三，吴峰光帮老乡安装 Linux，第一次接触 Linux 后，他意犹未尽。吴峰光的同学弓岱伟已经是学习了多年 Linux 的高手，恰巧住在他隔壁宿舍。近水楼台，吴峰光常常到弓岱伟的宿舍，静静坐在他的身后看着他玩儿 Linux。
吴峰光在啃过大部头 Borland C++ 之后更钟情于 Linux。他立志在 GNU/Linux 里深耕。他意识到 Linux 的世界宽广又深邃，经得起时间的考验，值得深潜；GNU/Linux 开放源代码，可以深入学习；一应俱全的命令行工具好像乐高模块，组合灵活，一旦掌握了做事的效率翻飞，很多原本想想都难的事情，现在也唾手可得。“学了之后终身受用。”
打开网易新闻 查看精彩图片
2001 年，吴峰光本科毕业随即开启硕博之路
2001 年，24 岁的吴峰光本科毕业。彼时，吴峰光的父亲希望家里能出一位博士，尽管家里的经济条件一直不宽裕，但全家人支持他继续学业。吴峰光遵从父命。同年，他考上了中科大“模式识别与智能系统”硕士研究生。硕士期间，吴峰光跟实验室老师一起做实验，深入了神经网络等课题。2004 年，吴峰光升入本校“控制理论与控制工程”专业读博士，终于实现了父亲的愿望。
中科大，瀚海星云 BBS 上，性格内向的吴峰光找到了社交杠杆，他活跃其中，发帖子，讨论技术，甚至当上了 Linux 版主。除了计算机系的同学，吴峰光认识了一大批背景多元的学习 Linux 的同学，生物系、物理系、数学系……吴峰光眼界大开，他了解到物理系和生物系用 Linux 是在做超算。作为自动化系学 Linux 的人，他感觉自己不再单枪匹马，有了共同学习的氛围感。“我们系里的网络有 IP 冲突，我发现服务器在实验室的一个角落里，风扇坏了还能运行，我写了一个 IP 冲突的解决程序，当时蛮有成就感的。”“我一直对服务器很有感情，也喜欢为别人提供服务，只要是跟服务器相关的问题，我都乐意研究搞定。”吴峰光的 Linux 水平悄无声息地突飞猛进。
后来，吴峰光和弓岱伟把他们的计算机用一根网线互连，一起尝试做网络服务，弓岱伟搭建 BBS，吴峰光做文件服务。“后来，我跟弓岱伟的关系非常好，他很活跃，无论是在计算机还是社交上都非常厉害，吃得开，不像我一直笨笨的。我那时很崇拜他。”吴峰光在寝室摸了三年的 Linux 控制台，后来，他顺理成章变成了实验室里的网络管理员，帮老师接管了机房。
博士期间，吴峰光所在的大实验室里的几位老师都是数学出身，吴峰光本计划跟老师们做理论方面的研究，博士论文的选题方向锁定在控制理论研究方向上。未曾想，实验室接了 863 项目，擅长 Linux 服务与编程的吴峰光自然成了此项目中的关键力量，他很难再分出时间和精力继续原定的理论研究。吴峰光索性把手头的 863 项目当成论文的新选题，开始转向计算机方向的研究——Linux 的 IO 优化。自此，吴峰光开始对预读算法进行优化，并向 Linux 社区提交。
打开网易新闻 查看精彩图片
吴峰光旧照
从 1995 年到 2008 年，吴峰光在中科大深造了十三年，分别在本科两届同学，硕士和博士同学，两个实验室里认识了很多同学，跟这么密集的高手打交道，像是在积累无形的财富。中科大里有人格魅力的人比比皆是，有的同学对《红楼梦》有透彻研究；有的同学能记住全套卡牌，推算出对方手里的牌面。有的同学平常吊儿郎当，考试前突击学习几天，总能过关斩将。“跟他们一起真是太有意思了
boolean[] diagonal = new boolean[16]; // 对角线安全标志
boolean[] undiagonal = new boolean[16]; // 反对角线安全标志
用上两个判断是否能放置棋子
在 n 行 n 列的国际象棋棋盘上，最多可布n个皇后。
若两个皇后位于同一行、同一列、同一对角线上，
则称为它们为互相攻击。
n皇后问题是指找到这 n 个皇后的互不攻击的布局。
n 行 n 列的棋盘上，主次对角线各有2n-1条。
利用行号i和列号j计算
主对角线编号k的方法是k = n+i-j-1；
计算次对角线编号k的方法是k = i+j
你主要是算法有些模糊罢了，现在我怕我说的不好将你弄的越来越混乱所以给你个叫形象的若是还不明白，call me
package 百度;
//演示程序：n个皇后问题
import java.io.*;
/*
在 n 行 n 列的国际象棋棋盘上，最多可布n个皇后。
若两个皇后位于同一行、同一列、同一对角线上，
则称为它们为互相攻击。
n皇后问题是指找到这 n 个皇后的互不攻击的布局。
n 行 n 列的棋盘上，主次对角线各有2n-1条。
利用行号i和列号j计算
主对角线编号k的方法是k = n+i-j-1；
计算次对角线编号k的方法是k = i+j
*/
//"n个皇后问题"之类定义
public class cQueen {
int n; //皇后问题的大小
int col[]; //数组，各列上有无皇后(0，1)
int md[]; //数组，各主对角线有无皇后(0，1)
int sd[]; //数组，各次对角线有无皇后(0，1)
int q[]; //数组，第i行上皇后在第几列(0,n-1)
int Q; //已布皇后数，计数
int r; //n皇后问题的解的组数
//构造函数 n皇后问题的初始化
public cQueen(int m) {
n=m;Q=0;r=0;
col=new int[n];
md=new int[2*n-1]; //初始化0
sd=new int[2*n-1];
q=new int[n];
}
//函数：打印棋盘
public void showBoard() {
int i,j;
for(i=0;in;i++) {
for(j=0;jn;j++)
if(q[i]==j) System.out.print("1 ");
else System.out.print("0 ");
System.out.println();
}
r++; //解的组数
System.out.println("---------------");
}
//求解n皇后问题
/*
此函数试图在n*n的棋盘的第i行上放一个皇后,
若找到可以放的位置,就递归调用自身试图在i+1行
放另一个皇后,若第i行是最后一行，则打印棋盘。
*/
public void resolve(int i) {
int j;
// 在第i行给定后检查棋盘上的每一列
for(j=0;jn;j++) {
//如果在第i行的第j列可以布放皇后
if(col[j]==0md[n+i-j-1]==0sd[i+j]==0){
Q++;q[i]=j; //布放皇后，第i行皇后在第几列
// 标记新布皇后的攻击范围
col[j]=md[n+i-j-1]=sd[i+j]=1;
// 如果已经布了n个皇后（得到了一组解）,
// 把棋盘（解）打印出来。
if(Q==n) showBoard();
// 否则，递归。在第i行第j列布放皇后的前提下，
//试探下一行(i+1行)在哪一列布皇后？
else if(in-1) resolve(i+1);
else resolve(0); //因为约定起始行可以任选
//移除在第i行的第j列新布的皇后，
//并消除所标记的攻击范围，为回溯作准备。
Q--; q[i]=0;
col[j]=md[n+i-j-1]=sd[i+j]=0;
//试探在第i行的第j+1列新布皇后的方案（新解）
}
} //下一列，j循环
//对于给定的行,列扫描完毕后，从这里回溯。
}
//输出解的个数
public void HowMany() {
System.out.println(n+"皇后问题共有解"+r+"组。");
}
//主方法main()
public static void main(String []args) {
//定义一个8皇后问题（有92组解）
cQueen Q1=new cQueen(8); //大于10，你的微机可能要死机！
//第一个皇后可以在任意一行布放
Q1.resolve(0); //参数在0到n-1之间任选
Q1.HowMany();
}
} //类Queen定义结束
关于看代码的人人都知道的小技巧，最小试探法来输出结果进行比较和分析
猪哥回答：
呵呵，很经典的回溯法练习题，题我会解，不过国际象棋我不会，如果是马走日字的话，我就给你写一个吧。
原理很简单，一个棋盘看成一个什么二维什么来着，忘了，猪哥离开校门很多年。就是X轴、Y轴，棋盘左下角做原点，因为走日字，假定骑士起始坐标为(X,Y)，那么他的移动规则是(X-1,Y-2)或(X-1,Y+2)或(X-2,Y-1)或(X-2,Y+1)或(X+1,Y+2)或(X+1,Y-2)或(X+2,Y+1)或(X+2,Y-1)这8种移动规则，也不知道你看懂了没，下面我开始写代码。。。。
我事情比较多，先不急。。代码我慢慢写。
写了个简单的例子，List也是栈实现的一种方式，你先看看吧，不知道对你有没有帮助，当然你最好用3*4、4*5这样的小数字调试，大棋盘程序执行的时间很长，非常长。
import java.util.ArrayList;
import java.util.List;
/**
* 骑士周游demo,没有做防呆处理
* 棋盘模拟图，A假定为骑士起始位置
* 3
* 2
* 1
* 0 A
* 0 1 2 3
* @author 猪哥甲
*
*/
public class DemoKnight
{
private static int NX = 3;//棋盘横向大小
private static int NY = 4;//棋盘纵向大小
private static int[] dx = { 2, 1, -1, -2, -2, -1, 1, 2 };
private static int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 };
private int sx = 0;//骑士起始横坐标
private int sy = 0;//骑士起始纵坐标
private List points = new ArrayList();//用来有解的路线
private List steps = new ArrayList();//用来记录骑士走过的路线
public static void main(String[] args)
{
DemoKnight dkt = new DemoKnight();
dkt.sx = 0;
dkt.sy = 0;
List list = new ArrayList();
dkt.steps.add(dkt.getPointStr(dkt.sx, dkt.sy));
dkt.KnightTrav(dkt.sx, dkt.sy);
int size = dkt.points.size();
System.out.println("终于走完了。。。共找到"+size+"种解决方案");
for(int i=0;isize;i++){
List list2 = (List) dkt.points.get(i);
for(int j=0;jlist2.size();j++){
System.out.print(list2.get(j)+"--");
}
System.out.println();
}
}
public boolean KnightTrav(int x, int y)
{
String str = null;
boolean flag = false;
//8种方向，每种方向假定有一个解法，8次循环
for(int tx=0,ty=0,count=0;count8;count++){
tx = x + dx[count];
ty = y + dy[count];
str = this.getPointStr(tx, ty);
if((tx=0txNX)(ty=0tyNY)!this.steps.contains(str)){
flag = true;
this.steps.add(str);
int size = this.steps.size();
if(!KnightTrav(tx, ty)){
System.out.println("一条路走到尽头,共走了"+size+"步");
}
if(size==NX*NY){
points.add(new ArrayList(this.steps));
}
this.steps.remove(size-1);
}
}
return flag;
}
private String getPointStr(int x,int y){
StringBuffer sb = new StringBuffer("{");
sb.append(x);
sb.append(",");
sb.append(y);
sb.append("}");
return sb.toString();
}
}
重庆分公司
重庆分公司
