我曾经参加了一次面试，在面试中被问到了一个看起来很简单的算法问题：“编写一个算法，返回所有可能的井字棋胜利组合。” 我仍然无法找到一个有效的处理方法。是否有一个标准算法或常见算法可应用于类似的问题，而我不知道呢？
所有可能的井字棋获胜组合
7
- DroidT
2
paxdiablo的答案是可行的；你也可以从“另一面”来考虑：从一个空白的棋盘开始，玩出每个可能的游戏，并记录达到的最终获胜位置。这比paxdiablo的答案更费力，但对于比井字棋更复杂的游戏可能会更容易些。 - AakashM
获胜的组合是指最终的棋盘配置还是包括达到该配置的步骤？ - Sebastian
8个回答
10
这其实是一个足够简单，可以用暴力方法解决的问题。虽然你也可以使用组合学、图论或其他复杂工具来解决它，但我会对识别到有一种更简单的方法（至少对于这个问题而言）的申请者印象深刻。
在网格中放置 x,o 或 <blank> 的可能组合只有 39 或 19,683 种，而并非所有都是有效的。
首先，有效的游戏局面是指 x 和 o 数量之差不超过1，因为它们必须轮流移动。
除此之外，不可能出现双方都有三个相连的情况，所以这些情况也可以被排除。如果双方都有三个相连的情况，那么其中一个在前一步就已经获胜了。
事实上，还有一个限制条件，即一个方不能以两种不同的方式获胜且没有公共点（同样，在之前的一步中它们已经获胜），这意味着：
XXX
OOO
XXX
无法实现，但是：
XXX
OOX
OOX
虽然可能存在一种情况，即没有公共单元格而赢得两次。但是我们实际上可以忽略它，因为如果你需要六个单元格，而对手只有三个单元格，则在不违反“最大差异为一”规则的前提下，已经违反了其中一个条件。
因此，我会简单地使用蛮力法，并针对每个计数之间差异为零或一的位置，检查双方的八种获胜可能性。假设只有其中一方获胜，那就是合法且获胜的游戏。
以下是Python的概念证明，但首先运行time并将其发送到/ dev / null以显示它的速度：
real 0m0.169s
user 0m0.109s
sys 0m0.030s
代码：
def won(c, n):
if c[0] == n and c[1] == n and c[2] == n: return 1
if c[3] == n and c[4] == n and c[5] == n: return 1
if c[6] == n and c[7] == n and c[8] == n: return 1
if c[0] == n and c[3] == n and c[6] == n: return 1
if c[1] == n and c[4] == n and c[7] == n: return 1
if c[2] == n and c[5] == n and c[8] == n: return 1
if c[0] == n and c[4] == n and c[8] == n: return 1
if c[2] == n and c[4] == n and c[6] == n: return 1
return 0
pc = [' ', 'x', 'o']
c = [0] * 9
for c[0] in range (3):
for c[1] in range (3):
for c[2] in range (3):
for c[3] in range (3):
for c[4] in range (3):
for c[5] in range (3):
for c[6] in range (3):
for c[7] in range (3):
for c[8] in range (3):
countx = sum([1 for x in c if x == 1])
county = sum([1 for x in c if x == 2])
if abs(countx-county) < 2:
if won(c,1) + won(c,2) == 1:
print " %s | %s | %s" % (pc[c[0]],pc[c[1]],pc[c[2]])
print "---+---+---"
print " %s | %s | %s" % (pc[c[3]],pc[c[4]],pc[c[5]])
print "---+---+---"
print " %s | %s | %s" % (pc[c[6]],pc[c[7]],pc[c[8]])
print
我不会修改代码来考虑这一点，但只需要检查谁拥有最多的细胞（最后一个移动的人），并确保获胜的线条属于他们，这将是一个简单的问题。
- paxdiablo
7
1@Pham，可能是吗？但是为了什么？我们不需要在这里节省时间或空间，使用位意味着打包和解包，这很可能会使代码变得更加复杂。除非我误解了，否则我希望得到澄清。 - paxdiablo
我明白你的意思 :) 完全忘记了空格选项，所以我会撤回我的评论 :) - Pham Trung
1一步之差不应该允许双方都有。输家在对手获胜后不能移动。 - Janne Karila
@JanneKarila，说得好，我会把它加入答案中，但我不会费心去改变代码。 - paxdiablo
感谢@paxdiablo提供详细的答案！您能否为我们这些非PHP开发人员澄清代码中发生了什么，特别是在最后一个for循环中？ - DroidT
显示剩余2条评论
3
另一种方法是从八个获胜的位置中的每一个开始。
xxx ---
--- xxx
--- --- ... etc.,
并递归填充所有合法的组合（从插入2个o开始，然后为每个o添加一个x；避免o获胜的局面）：
xxx xxx xxx
oo- oox oox
--- o-- oox ... etc.,
- גלעד ברקן
1
今天我参加了苹果公司的面试，我遇到了同样的问题。那时我无法好好思考。后来，在去开会之前，我用了15分钟写出了组合函数，当我从会议回来时，我又用了15分钟再次编写了验证函数。我在面试时会很紧张，苹果公司不相信我的简历，他们只相信他们在面试中看到的东西，我不怪他们，很多公司都是这样，我只是认为招聘过程中有些地方看起来不太明智。
无论如何，以下是我在Swift 4中的解决方案，组合函数有8行代码，检查有效棋盘的函数有17行代码。
干杯!!!
// Not used yet: 0
// Used with x : 1
// Used with 0 : 2
// 8 lines code to get the next combination
func increment ( _ list: inout [Int], _ base: Int ) -> Bool {
for digit in 0..<list.count {
list[digit] += 1
if list[digit] < base { return true }
list[digit] = 0
}
return false
}
let incrementTicTacToe = { increment(&$0, 3) }
let win0_ = [0,1,2] // [1,1,1,0,0,0,0,0,0]
let win1_ = [3,4,5] // [0,0,0,1,1,1,0,0,0]
let win2_ = [6,7,8] // [0,0,0,0,0,0,1,1,1]
let win_0 = [0,3,6] // [1,0,0,1,0,0,1,0,0]
let win_1 = [1,4,7] // [0,1,0,0,1,0,0,1,0]
let win_2 = [2,5,8] // [0,0,1,0,0,1,0,0,1]
let win00 = [0,4,8] // [1,0,0,0,1,0,0,0,1]
let win11 = [2,4,6] // [0,0,1,0,1,0,1,0,0]
let winList = [ win0_, win1_, win2_, win_0, win_1, win_2, win00, win11]
// 16 lines to check a valid board, wihtout countin lines of comment.
func winCombination (_ tictactoe: [Int]) -> Bool {
var count = 0
for win in winList {
if tictactoe[win[0]] == tictactoe[win[1]],
tictactoe[win[1]] == tictactoe[win[2]],
tictactoe[win[2]] != 0 {
// If the combination exist increment count by 1.
count += 1
}
if count == 2 {
return false
}
}
var indexes = Array(repeating:0, count:3)
for num in tictactoe { indexes[num] += 1 }
// '0' and 'X' must be used the same times or with a diference of one.
// Must one and only one valid combination
return abs(indexes[1] - indexes[2]) <= 1 && count == 1
}
// Test
var listToIncrement = Array(repeating:0, count:9)
var combinationsCount = 1
var winCount = 0
while incrementTicTacToe(&listToIncrement) {
if winCombination(listToIncrement) == true {
winCount += 1
}
combinationsCount += 1
}
print("There is \(combinationsCount) combinations including possible and impossible ones.")
print("There is \(winCount) combinations for wining positions.")
/*
There are 19683 combinations including possible and impossible ones.
There are 2032 combinations for winning positions.
*/
listToIncrement = Array(repeating:0, count:9)
var listOfIncremented = ""
for _ in 0..<1000 { // Win combinations for the first 1000 combinations
_ = incrementTicTacToe(&listToIncrement)
if winCombination(listToIncrement) == true {
listOfIncremented += ", \(listToIncrement)"
}
}
print("List of combinations: \(listOfIncremented)")
/*
List of combinations: , [2, 2, 2, 1, 1, 0, 0, 0, 0], [1, 1, 1, 2, 2, 0, 0, 0, 0],
[2, 2, 2, 1, 0, 1, 0, 0, 0], [2, 2, 2, 0, 1, 1, 0, 0, 0], [2, 2, 0, 1, 1, 1, 0, 0, 0],
[2, 0, 2, 1, 1, 1, 0, 0, 0], [0, 2, 2, 1, 1, 1, 0, 0, 0], [1, 1, 1, 2, 0, 2, 0, 0, 0],
[1, 1, 1, 0, 2, 2, 0, 0, 0], [1, 1, 0, 2, 2, 2, 0, 0, 0], [1, 0, 1, 2, 2, 2, 0, 0, 0],
[0, 1, 1, 2, 2, 2, 0, 0, 0], [1, 2, 2, 1, 0, 0, 1, 0, 0], [2, 2, 2, 1, 0, 0, 1, 0, 0],
[2, 2, 1, 0, 1, 0, 1, 0, 0], [2, 2, 2, 0, 1, 0, 1, 0, 0], [2, 2, 2, 1, 1, 0, 1, 0, 0],
[2, 0, 1, 2, 1, 0, 1, 0, 0], [0, 2, 1, 2, 1, 0, 1, 0, 0], [2, 2, 1, 2, 1, 0, 1, 0, 0],
[1, 2, 0, 1, 2, 0, 1, 0, 0], [1, 0, 2, 1, 2, 0, 1, 0, 0], [1, 2, 2, 1, 2, 0, 1, 0, 0],
[2, 2, 2, 0, 0, 1, 1, 0, 0]
*/
- ideastouch
0
这个问题可以通过暴力解决，但要记住一些特殊情况，例如当玩家1获胜时，玩家2无法移动，反之亦然。还要记住玩家1和玩家2的移动差不能大于1且小于0。
我已经编写了验证提供的组合是否有效的代码，可能很快会在github上发布。
- Hariom Singh
2
1谢谢您的贡献，但是您所写的内容已经在 @paxdiablo 的答案中涵盖了。 - Masoud Keshavarz
如果player1是赢家，那么他们不能拥有相等的单元格，这是一个未被提及的角落情况。此外，不要认为这需要投反对票，否则新手将难以增加贡献。 - Hariom Singh
0
以下解决方案使用递归生成所有可能的组合。
它已经排除了不可能的组合并返回了888个组合。
下面是一个可行的代码TIC TAC TOE游戏的可能获胜组合。
它已经排除了不可能的组合并返回了888个组合。
下面是一个可行的代码TIC TAC TOE游戏的可能获胜组合。
const players = ['X', 'O'];
let gameBoard = Array.from({ length: 9 });
const winningCombination = [
[ 0, 1, 2 ],
[ 3, 4, 5 ],
[ 6, 7, 8 ],
[ 0, 3, 6 ],
[ 1, 4, 7 ],
[ 2, 5, 8 ],
[ 0, 4, 8 ],
[ 2, 4, 6 ],
];
const isWinningCombination = (board)=> {
if((Math.abs(board.filter(a => a === players[0]).length -
board.filter(a => a === players[1]).length)) > 1) {
return false
}
let winningComb = 0;
players.forEach( player => {
winningCombination.forEach( combinations => {
if (combinations.every(combination => board[combination] === player )) {
winningComb++;
}
});
});
return winningComb === 1;
}
const getCombinations = (board) => {
let currentBoard = [...board];
const firstEmptySquare = board.indexOf(undefined)
if (firstEmptySquare === -1) {
return isWinningCombination(board) ? [board] : [];
} else {
return [...players, ''].reduce((prev, next) => {
currentBoard[firstEmptySquare] = next;
if(next !== '' && board.filter(a => a === next).length > (gameBoard.length / players.length)) {
return [...prev]
}
return [board, ...prev, ...getCombinations(currentBoard)]
}, [])
}
}
const startApp = () => {
let combination = getCombinations(gameBoard).filter(board =>
board.every(item => !(item === undefined)) && isWinningCombination(board)
)
printCombination(combination)
}
const printCombination = (combination)=> {
const ulElement = document.querySelector('.combinations');
combination.forEach(comb => {
let node = document.createElement("li");
let nodePre = document.createElement("pre");
let textnode = document.createTextNode(JSON.stringify(comb));
nodePre.appendChild(textnode);
node.appendChild(nodePre);
ulElement.appendChild(node);
})
}
startApp();
- Owen Kelvin
0
这是一个用递归方法编写的 JavaScript 代码，用于寻找井字棋（255,168）的所有可能组合。尽管并没有进行优化，但可以满足您的需求。
const [EMPTY, O, X] = [0, 4, 1]
let count = 0
let coordinate = [
EMPTY, EMPTY, EMPTY,
EMPTY, EMPTY, EMPTY,
EMPTY, EMPTY, EMPTY
]
function reducer(arr, sumOne, sumTwo = null) {
let func = arr.reduce((sum, a) => sum + a, 0)
if((func === sumOne) || (func === sumTwo)) return true
}
function checkResult() {
let [a1, a2, a3, b1, b2, b3, c1, c2, c3] = coordinate
if(reducer([a1,a2,a3], 3, 12)) return true
if(reducer([a1,b2,c3], 3, 12)) return true
if(reducer([b1,b2,b3], 3, 12)) return true
if(reducer([c1,c2,c3], 3, 12)) return true
if(reducer([a3,b2,c1], 3, 12)) return true
if(reducer([a1,b1,c1], 3, 12)) return true
if(reducer([a2,b2,c2], 3, 12)) return true
if(reducer([a3,b3,c3], 3, 12)) return true
if(reducer([a1,a2,a3,b1,b2,b3,c1,c2,c3], 21)) return true
return false
}
function nextPiece() {
let [countX, countO] = [0, 0]
for(let i = 0; i < coordinate.length; i++) {
if(coordinate[i] === X) countX++
if(coordinate[i] === O) countO++
}
return countX === countO ? X : O
}
function countGames() {
if (checkResult()) {
count++
}else {
for (let i = 0; i < 9; i++) {
if (coordinate[i] === EMPTY) {
coordinate[i] = nextPiece()
countGames()
coordinate[i] = EMPTY
}
}
}
}
countGames()
console.log(count)我将checkResult的返回值分离出来，以防您想要输出各种获胜条件。
- Tim
0
这是一个Java等效的代码示例
包testit;
public class TicTacToe {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 0 1 2
// 3 4 5
// 6 7 8
char[] pc = {' ' ,'o', 'x' };
char[] c = new char[9];
// initialize c
for (int i = 0; i < 9; i++)
c[i] = pc[0];
for (int i = 0; i < 3; i++) {
c[0] = pc[i];
for (int j = 0; j < 3; j++) {
c[1] = pc[j];
for (int k = 0; k < 3; k++) {
c[2] = pc[k];
for (int l = 0; l < 3; l++) {
c[3] = pc[l];
for (int m = 0; m < 3; m++) {
c[4] = pc[m];
for (int n = 0; n < 3; n++) {
c[5] = pc[n];
for (int o = 0; o < 3; o++) {
c[6] = pc[o];
for (int p = 0; p < 3; p++) {
c[7] = pc[p];
for (int q = 0; q < 3; q++) {
c[8] = pc[q];
int countx = 0;
int county = 0;
for(int r = 0 ; r<9 ; r++){
if(c[r] == 'x'){
countx = countx + 1;
}
else if(c[r] == 'o'){
county = county + 1;
}
}
if(Math.abs(countx - county) < 2){
if(won(c, pc[2])+won(c, pc[1]) == 1 ){
System.out.println(c[0] + " " + c[1] + " " + c[2]);
System.out.println(c[3] + " " + c[4] + " " + c[5]);
System.out.println(c[6] + " " + c[7] + " " + c[8]);
System.out.println("*******************************************");
}
}
}
}
}
}
}
}
}
}
}
}
public static int won(char[] c, char n) {
if ((c[0] == n) && (c[1] == n) && (c[2] == n))
return 1;
else if ((c[3] == n) && (c[4] == n) && (c[5] == n))
return 1;
else if ((c[6] == n) && (c[7] == n) && (c[8] == n))
return 1;
else if ((c[0] == n) && (c[3] == n) && (c[6] == n))
return 1;
else if ((c[1] == n) && (c[4] == n) && (c[7] == n))
return 1;
else if ((c[2] == n) && (c[5] == n) && (c[8] == n))
return 1;
else if ((c[0] == n) && (c[4] == n) && (c[8] == n))
return 1;
else if ((c[2] == n) && (c[4] == n) && (c[6] == n))
return 1;
else
return 0;
}
- Vijay Rumao
1
相当于什么？ - Sebastian
0
大多数针对这个问题的答案都相当缓慢，以下是更快的方式。
def won(c, n):
if c[0] == n and c[1] == n and c[2] == n: return 1
if c[3] == n and c[4] == n and c[5] == n: return 1
if c[6] == n and c[7] == n and c[8] == n: return 1
if c[0] == n and c[3] == n and c[6] == n: return 1
if c[1] == n and c[4] == n and c[7] == n: return 1
if c[2] == n and c[5] == n and c[8] == n: return 1
if c[0] == n and c[4] == n and c[8] == n: return 1
if c[2] == n and c[4] == n and c[6] == n: return 1
return 0
for count in range(3**9):
grid = [(count // (3 ** i)) % 3 for i in range(9)]
if won(grid, 1) + won(grid, 2) == 1:
print(grid)
- UnknownEncoder
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接