不限语言解决“三狼三羊过河问题”

老刘1号

某算法课程中看到的一个题，

一个人带三只狼和三只羚羊过河，只有一条船，同船可以容纳一个人和两只动物。没有人在的时候，如果狼的数量不少于羚羊的数量，狼就会吃掉羚羊。请编程求过河方案。

据说练回溯很好，欢迎大家回帖分享自己的代码

vbs版（无效率可言，仅为粗略实现）

Rem Code By 老刘
todo=Array("[人去对岸]","[人回该岸]","[带1狼去对岸]","[带2狼去对岸]","[带1狼回该岸]","[带2狼回该岸]","[带1羊去对岸]","[带2羊去对岸]","[带1羊回该岸]","[带2羊回该岸]","[带狼羊去对岸]","[带狼羊回该岸]")
Dim [方法]
[方法] = 1
recursion New [三狼三羊过河问题],"3,0,3,0,1",""


Sub recursion(ByRef obj,ByVal StatusLog,byVal StepLog)
	Dim nowStatus
	nowStatus = Join(obj.[当前情形],",")
	If nowStatus = "0,3,0,3,2" Then
		wsh.echo "方法"&[方法]&StepLog&vbNewLine
		[方法] = [方法] + 1
	Else
		For i = 0 To UBound(todo)
			If Eval("obj."&todo(i)) = True Then
				If InStr(StatusLog,Join(obj.[当前情形],",")) = 0 Then	'避免执行步骤恢复到以前状态，陷入死循环
					recursion obj,StatusLog & vbNewLine & Join(obj.[当前情形],","),StepLog & vbNewLine & todo(i)
				End If
			End If
			Execute "obj.[加载情形] " & nowStatus
		Next
	End If
End Sub

Class [三狼三羊过河问题]
	Private [该岸羊数],[对岸羊数],[该岸狼数],[对岸狼数],[人的位置]
	
	Private Sub Class_Initialize
		[该岸羊数] = 3
		[对岸羊数] = 0
		[该岸狼数] = 3
		[对岸狼数] = 0
		[人的位置] = 1	'表示该岸，2为对岸
	End Sub
	
	Public Sub [加载情形](a,b,c,d,e)
		[该岸羊数] = a
		[对岸羊数] = b
		[该岸狼数] = c
		[对岸狼数] = d
		[人的位置] = e
	End Sub
	
	Public Function [当前情形]
		[当前情形] = Array([该岸羊数],[对岸羊数],[该岸狼数],[对岸狼数],[人的位置])
	End Function
	
	Private Function [可行性分析]
		If [人的位置] = 1 Then	'人在该岸
			If [对岸狼数] >= [对岸羊数] And [对岸羊数] >= 1 Then
				[可行性分析] = False	'对岸狼会吃羊
			Else
				[可行性分析] = True
			End If
		Else	'人在对岸
			If [该岸狼数] >= [该岸羊数] And [该岸羊数] >= 1 Then
				[可行性分析] = False	'该岸狼会吃羊
			Else
				[可行性分析] = True
			End If
		End If
	End Function
	
	Public Function [人去对岸]
		If [人的位置] = 2 Then
			[人去对岸] = False
		Else
			[人的位置] = 2
			If [可行性分析] = False Then
				[人的位置] = 1
				[人去对岸] = False	'操作不可行
			Else
				[人去对岸] = True	'操作可行
			End If
		End If
	End Function
	
	Public Function [人回该岸]
		If [人的位置] = 1 Then
			[人回该岸] = False
		Else
			[人的位置] = 1
			If [可行性分析] = False Then
				[人的位置] = 2
				[人回该岸] = False	'操作不可行
			Else
				[人回该岸] = True	'操作可行
			End If
		End If
	End Function
	
	Public Function [带1狼去对岸]
		If [人的位置] = 2 Then
			[带1狼去对岸] = False
		Else
			If [该岸狼数] = 0 Then	'该岸无狼
				[带1狼去对岸] = False
			Else
				[人的位置] = 2
				[该岸狼数] = [该岸狼数] - 1
				[对岸狼数] = [对岸狼数] + 1
				If [可行性分析] = False Then
					[带1狼去对岸] = False
				Else
					[带1狼去对岸] = True
				End If
			End If
		End If
	End Function
	
	Public Function [带2狼去对岸]
		If [人的位置] = 2 Then
			[带2狼去对岸] = False
		Else
			If [该岸狼数] <= 1 Then	'该岸狼不够
				[带2狼去对岸] = False
			Else
				[人的位置] = 2
				[该岸狼数] = [该岸狼数] - 2
				[对岸狼数] = [对岸狼数] + 2
				If [可行性分析] = False Then
					[带2狼去对岸] = False
				Else
					[带2狼去对岸] = True
				End If
			End If
		End If
	End Function
	
	Public Function [带1狼回该岸]
		If [人的位置] = 1 Then
			[带1狼回该岸] = False
		Else
			If [对岸狼数] = 0 Then	'对岸无狼
				[带1狼回该岸] = False
			Else
				[人的位置] = 1
				[该岸狼数] = [该岸狼数] + 1
				[对岸狼数] = [对岸狼数] - 1
				If [可行性分析] = False Then
					[带1狼回该岸] = False
				Else
					[带1狼回该岸] = True
				End If
			End If
		End If
		
	End Function
	
	Public Function [带2狼回该岸]
		If [人的位置] = 1 Then
			[带2狼回该岸] = False
		Else
			If [对岸狼数] <= 1 Then	'对岸狼不够
				[带2狼回该岸] = False
			Else
				[人的位置] = 1
				[该岸狼数] = [该岸狼数] + 2
				[对岸狼数] = [对岸狼数] - 2
				If [可行性分析] = False Then
					[带2狼回该岸] = False
				Else
					[带2狼回该岸] = True
				End If
			End If
		End If
	End Function
	
	Public Function [带1羊去对岸]
		If [人的位置] = 2 Then
			[带1羊去对岸] = False
		Else
			If [该岸羊数] = 0 Then	'该岸无羊
				[带1羊去对岸] = False
			Else
				[人的位置] = 2
				[该岸羊数] = [该岸羊数] - 1
				[对岸羊数] = [对岸羊数] + 1
				If [可行性分析] = False Then
					[带1羊去对岸] = False
				Else
					[带1羊去对岸] = True
				End If
			End If
		End If
	End Function
	
	Public Function [带2羊去对岸]
		If [人的位置] = 2 Then
			[带2羊去对岸] = False
		Else
			If [该岸羊数] <= 1 Then	'该岸羊不够
				[带2羊去对岸] = False
			Else
				[人的位置] = 2
				[该岸羊数] = [该岸羊数] - 2
				[对岸羊数] = [对岸羊数] + 2
				If [可行性分析] = False Then
					[带2羊去对岸] = False
				Else
					[带2羊去对岸] = True
				End If
			End If
		End If
	End Function
	
	Public Function [带1羊回该岸]
		If [人的位置] = 1 Then
			[带1羊回该岸] = False
		Else
			If [对岸羊数] = 0 Then	'对岸无羊
				[带1羊回该岸] = False
			Else
				[人的位置] = 1
				[该岸羊数] = [该岸羊数] + 1
				[对岸羊数] = [对岸羊数] - 1
				If [可行性分析] = False Then
					[带1羊回该岸] = False
				Else
					[带1羊回该岸] = True
				End If
			End If
		End If
	End Function
	
	Public Function [带2羊回该岸]
		If [人的位置] = 1 Then
			[带2羊回该岸] = False
		Else
			If [对岸羊数] <= 1 Then	'对岸羊不够
				[带2羊回该岸] = False
			Else
				[人的位置] = 1
				[该岸羊数] = [该岸羊数] + 2
				[对岸羊数] = [对岸羊数] - 2
				If [可行性分析] = False Then
					[带2羊回该岸] = False
				Else
					[带2羊回该岸] = True
				End If
			End If
		End If
	End Function
	
	Public Function [带狼羊去对岸]
		If [人的位置] = 2 Then
			[带狼羊去对岸] = False
		Else
			If [该岸羊数] = 0 Or [该岸狼数] = 0 Then
				[带狼羊去对岸] = False
			Else
				[人的位置] = 2
				[该岸羊数] = [该岸羊数] - 1
				[对岸羊数] = [对岸羊数] + 1
				[该岸狼数] = [该岸狼数] - 1
				[对岸狼数] = [对岸狼数] + 1
				If [可行性分析] = False Then
					[带狼羊去对岸] = False
				Else
					[带狼羊去对岸] = True
				End If
			End If
		End If
	End Function
	
	Public Function [带狼羊回该岸]
		If [人的位置] = 1 Then
			[带狼羊回该岸] = False
		Else
			If [对岸羊数] = 0 Or [对岸狼数] = 0 Then
				[带狼羊回该岸] = False
			Else
				[人的位置] = 1
				[该岸羊数] = [该岸羊数] + 1
				[对岸羊数] = [对岸羊数] - 1
				[该岸狼数] = [该岸狼数] + 1
				[对岸狼数] = [对岸狼数] - 1
				If [可行性分析] = False Then
					[带狼羊回该岸] = False
				Else
					[带狼羊回该岸] = True
				End If
			End If
		End If
	End Function
End Class
复制代码

部分结果

方法1
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带2羊去对岸]
[带2狼回该岸]
[带1羊去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]

方法2
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带2羊去对岸]
[带2狼回该岸]
[带1羊去对岸]
[人回该岸]
[带2狼去对岸]

方法3
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带2羊去对岸]
[带2狼回该岸]
[带1羊去对岸]
[带1狼回该岸]
[带2狼去对岸]
[人回该岸]
[带1狼去对岸]

方法4
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带2羊去对岸]
[带2狼回该岸]
[带1羊去对岸]
[带1狼回该岸]
[带2狼去对岸]
[带1狼回该岸]
[带2狼去对岸]

...

方法260
[带2狼去对岸]
[带1狼回该岸]
[带狼羊去对岸]
[带1羊回该岸]
[带狼羊去对岸]
[带1羊回该岸]
[带2羊去对岸]
[带2狼回该岸]
[带狼羊去对岸]
[带2狼回该岸]
[带1狼去对岸]
[人回该岸]
[带2狼去对岸]

老刘1号

回复 2# xczxczxcz


    哈哈，这只是一种方法吧，欢迎编程求所有状态不和历史重复下的方法（260种）

老刘1号

回复 5# 523066680


    第二条学习了，
第一条，其实限制没有那么严，因为船舱中可以“常驻”生物（我研究我代码跑出的结果时偶然发现的
假设船舱容量8，狼、羊均17只，
可以如下操作：

拉8狼过，回 此时wolf=9,8
拉7狼过，回 此时wolf=2,15
拉8羊过，拉8狼回 此时wolf=10,7 sheep=9,8
船上放置2狼，每次载3狼3羊过去即可。
复制代码

其实也没必要太纠结这个问题本身，现实意义不大，
主要是练下回溯法，让程序深度优先遍历所有可能路径。
程序跑出来就有，跑不出就没有，不用动脑，岂不美哉。

老刘1号

回复 7# 523066680


    哈哈，这个不穷举一下有时候人脑就是考虑不全，正常正常
刚看你的说法也觉得没有毛病，突然觉得有些不太对，就测试了一下

递归枚举这个一类题的套路都一样，只不过每个题要求“回溯”的条件不同，有的还需要判断历史状态
什么人狼羊菜过河，八皇后问题，3水桶分8升水问题，走迷宫问题不是都差不多嘛，基本属于一劳永逸型

老刘1号

回复 7# 523066680


    装载量的话，当狼、羊数=1的时候，>0即可，当狼、羊数=2,3,4的时候，>1即可，当狼、羊数=5,6的时候，>2即可，当狼、羊数>6的时候，>3即可

设狼、羊数目为n，装载量为4
可以

载4狼过，回
载3狼过，回
载4羊过，载4狼回
船上装2狼，每次运送1狼1羊
复制代码

题目的关键点在于让人不在的位置羊>狼
而准确说有3个位置，当岸、对岸，船
当岸和对岸，人有时候在，有时候不在，而船上人永远是在的
所以船可以无视题目条件，来做“周转”

其实可以假设题目条件为 n羊，n-2狼
这样只要先在对岸放1羊，两岸羊数就都比狼数大1，
每次移动1狼1羊，都不会触发狼吃羊条件。
而上面的结论是将2狼加回来，放在“船上”得到的

更直观的离子

载2狼1羊过，载2狼回
船上装2狼，每次运送1狼1羊
复制代码