Toate combinațiile câștigătoare Tic Tac Toe posibile (Programare, Algoritm, Combinații, Algoritm Grafic)

DroidT a intrebat.

Am avut un interviu în care mi s-a pus o întrebare aparent simplă despre algoritmi: „Scrie un algoritm care să-mi returneze toate combinațiile câștigătoare posibile pentru Tic Tac Toe.” Încă nu reușesc să găsesc o modalitate eficientă de a rezolva acest lucru. Există un algoritm standard sau comun care ar trebui aplicat la întrebări similare ca aceasta și de care eu nu sunt conștient?

Comentarii

  • Răspunsul lui paxdiablo funcționează; ați putea, de asemenea, să o abordați din „cealaltă parte”: începeți de la un gol și jucați fiecare joc posibil, ținând evidența pozițiilor finale câștigătoare atinse. Acest lucru ar presupune mai multă muncă decât răspunsul lui paxdiablo, dar pentru un joc mai complex decât tic tac toe s-ar putea dovedi a fi mai ușor. –  > Por AakashM.
5 răspunsuri
paxdiablo

Aceasta este una dintre acele probleme care este de fapt suficient de simplă pentru forța brută și, deși ați putea folosiți combinatorică, teoria grafurilor sau multe alte instrumente complexe pentru a o rezolva, aș fi de fapt impresionat de candidații care recunosc faptul că există o cale mai ușoară (cel puțin pentru această problemă).

Există doar 39, sau 19.683 de combinații posibile de plasare x, , o sau <blank> în grilă, și nu toate sunt valide.

În primul rând, o poziție de joc validă este una în care diferența dintre x și o contează nu este mai mare de unu, deoarece acestea trebuie să alterneze mutările.

În plus, este imposibil să existe o stare în care ambele părți au trei la rând, astfel că și acestea pot fi de asemenea eliminate. Dacă ambele au câte trei la rând, atunci una dintre ele ar fi câștigat în anterioară mișcare anterioară.

Există de fapt o altă limitare, în sensul că este imposibil ca o parte să fi câștigat în două moduri diferite fără o celulă comună (din nou, ar fi câștigat într-o mutare anterioară), ceea ce înseamnă că:

XXX
OOO
XXX

nu poate fi obținut, în timp ce:

XXX
OOX
OOX

poate fi. Dar, de fapt, putem ignora acest lucru, deoarece nu există nicio modalitate de a câștiga în două moduri fără o celulă comună fără a fi încălcat deja regula „diferenței maxime de unu”, deoarece pentru asta ai nevoie de șase celule, iar adversarul are doar trei.

Așadar, aș folosi pur și simplu forța brută și, pentru fiecare poziție în care diferența dintre numărători este zero sau unu, aș verifica cele opt posibilități de câștig pentru ambele părți. Presupunând că doar una dintre ele are câștig, acesta este un joc legal și câștigător.


Mai jos este o demonstrație de concept în Python, dar mai întâi este afișată ieșirea lui time atunci când este rulat pe procesul care trimite ieșirea către /dev/null pentru a arăta cât de rapid este:

real    0m0.169s
user    0m0.109s
sys     0m0.030s

Codul:

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

După cum a subliniat un comentator, mai există o restricție. Câștigătorul pentru o anumită tablă nu poate avea mai puține celule decât învinsul, deoarece acest lucru înseamnă că învinsul tocmai a mutat, în ciuda faptului că învingătorul câștigase deja la ultima mutare.

Nu voi modifica codul pentru a ține cont de acest lucru, dar ar fi o chestiune simplă de a verifica cine are cele mai multe celule (ultima persoană care a mutat) și de a se asigura că linia câștigătoare îi aparține.

Comentarii

  • @Pham, posibil, dar în ce scop? Nu avem nevoie să economisim timp sau spațiu aici, iar folosirea de biți înseamnă împachetarea și despachetarea, ceea ce probabil va face codul mai mult mai complex. Dacă nu cumva am înțeles greșit, caz în care aș aprecia o clarificare. –  > Por paxdiablo.
  • Am înțeles ce vrei să spui 🙂 am uitat complet de opțiunea de spațiu, așa că îmi voi retrage comentariul 🙂 –  > Por Pham Trung.
  • O diferență de o mutare nu ar trebui să fie permisă în ambele sensuri. Învinsul nu se poate muta după ce adversarul a câștigat. –  > Por Janne Karila.
  • @JanneKarila, bună observație, voi adăuga acest lucru în răspuns, dar nu mă voi obosi să modific codul. –  > Por paxdiablo.
  • Mulțumesc @paxdiablo pentru răspunsul detaliat! Vreți să clarificați ce se întâmplă cu codul, mai exact în ultima buclă for, pentru noi, cei care nu suntem dezvoltatori php? –  > Por DroidT.
גלעד ברקן

O altă modalitate ar putea fi să începem cu fiecare dintre cele opt poziții câștigătoare,

xxx ---
--- xxx
--- --- ... etc.,

și să se completeze recursiv toate combinațiile legale (se începe cu inserarea a 2 oapoi adăugați un x pentru fiecare o ; evitați o pozițiile câștigătoare):

xxx xxx xxx
oo- oox oox
--- o-- oox ... etc.,

ideastouch

Astăzi am avut un interviu cu Apple și am avut aceeași întrebare. Nu puteam gândi bine în acel moment. Mai târziu unul, înainte de a merge la o ședință am scris funcția pentru combinații în 15 minute, iar când m-am întors de la ședință am scris din nou funcția de validare în 15 minute. Am emoții la interviuri, Apple nu are încredere în CV-ul meu, au încredere doar în ceea ce văd la interviu, nu îi condamn, multe companii sunt la fel, eu spun doar că ceva în acest proces de angajare nu pare destul de inteligent.

Oricum, iată soluția mea în Swift 4, sunt 8 linii de cod pentru funcția de combinații și 17 linii de cod pentru a verifica o placă validă.

Noroc!!!

// 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]
*/

Vijay Rumao

Aceasta este o mostră de cod echivalent în java

pachet 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;

}

}`

Owen Kelvin

Soluția de mai jos generează toate combinațiile posibile folosind recursivitatea

A eliminat combinațiile imposibile și a returnat 888 Combinații

Mai jos este un cod de lucru Combinații câștigătoare posibile la jocul 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();