写一个 java 回溯法农夫过河代码

好的，这里是一个简单的Java回溯算法，用于解决农夫过河问题:

import java.util.ArrayList;
 java.util.List;

public class FarmerCrossRiver {
	
	public static void main(String[] args) {
		// 定义农夫、狼、羊、菜的编号为1,2,3,4
		List<Integer> start = new ArrayList<Integer>() {{
			add(1);
			add(2);
			add(3);
			add(4);
		}};
		
		List<Integer> end = new ArrayList<Integer>();
		
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		
		crossRiver(start, end, result);
		
        System.out.println(result);
	}

	private static void crossRiver(List<Integer> start, List<Integer> end, List<List<Integer>> result) {
		// 如果start都过了河，就可以加入记录
		if (start.isEmpty()) {
			result.add(new ArrayList<Integer>(end));
			return;
		}
		
		// 遍历start中所有人和物品
		for (int i = 0; i < start.size(); i++) {
			// 选取第i个人或物品过河
			int person = start.get(i);
			// 如果选择农夫，就把农夫从列表中移除
			if (person == 1) {
				start.remove(i);
				// 遍历所有可能的搭配进行过河
				for (int j = 0; j < start.size(); j++) {
					// 如果农夫与狼、羊、菜在一侧就不能搭配过河
					if (start.get(j) != 1 && person * start.get(j) != 4) {
						// 把该人或物品从原来的列表中移除
						int temp = start.remove(j);
						end.add(temp);
						// 继续递归搜索
						crossRiver(start, end, result);
						// 把该人或物品添加回原来的列表中，以便下一轮搜索
						end.remove(end.size() - 1);
						start.add(temp);
					}
				}
				start.add(i, person);
			} 
			// 如果不是农夫，就需要检查该人或物品与农夫的搭配是否合法
			else if (person * start.get(0) != 4) {
				start.remove(i);
				end.add(person);
				// 继续递归搜索
				crossRiver(start, end, result);
				// 把该人或物品添加回原来的列表中，以便下一轮搜索
				end.remove(end.size() - 1);
				start.add(i, person);
			}
		}
	}
	
}

这个算法使用了回溯法，分步解决农夫过河问题，通过遍历状态空间搜索所有可能的方案，找到符合要求的解。

注意：这个算法假设狼、羊、菜、农夫都能够独立把船划过河，而且河的对岸没有其它船可以使用。