Alle Möglichen Tic Tac Toe Gewinnen-Kombinationen

Hatte ich ein interview waren, wurde ich gebeten, eine scheinbar einfache Algorithmus Frage: "Schreiben Sie einen Algorithmus, um zurückzukehren, mir alle möglichen Gewinnkombinationen für tic tac toe." Ich kann immer noch nicht herausfinden, eine effiziente Möglichkeit, dies zu behandeln. Gibt es einen standard-Algorithmus oder gemeinsam angewendet werden sollen, um ähnliche Fragen wie diese, ich bin mir nicht bewusst?

paxdiablo Antwort funktioniert; Sie könnte auch den Ansatz der "anderen Seite": start von leer board, und spielen alle möglichen Spiel, verfolgen Sie den final gewinnen-Positionen erreicht. Dies würde mehr Arbeit als paxdiablo Antwort, aber für ein komplexeres Spiel als tic tac toe könnte dann einfacher sein.

InformationsquelleAutor DroidT | 2015-02-25

7

Dies ist eines jener Probleme, das ist eigentlich einfach genug für brute-force-und, während Sie könnte verwenden Kombinatorik, Graphentheorie, oder viele andere komplexe tools, um es zu lösen, ich würde eigentlich beeindruckt sein von den Antragstellern, die Tatsache anzuerkennen, es gibt einen einfacheren Weg (zumindest für dieses problem).

Gibt es nur 3⁹, oder 19,683 möglichen Kombinationen der Platzierung x, o oder <blank> im Netz, und nicht alle von denen sind gültig.

Erste, eine gültige Spiel-position ist eine, wo der Unterschied zwischen x und o zählt, ist nicht mehr als eine, da Sie abwechselnd bewegt.

Darüber hinaus ist es unmöglich, einen Zustand, in dem beide Seiten drei in einer Reihe, so können Sie abgezogen werden, wie gut. Wenn beide haben drei in einer Reihe, dann eine von Ihnen gewonnen hätte, die in der vorherigen bewegen.

Es ist tatsächlich eine weitere Einschränkung ist, dass es unmöglich für eine Seite gewonnen zu haben zwei verschiedene Möglichkeiten, ohne eine gemeinsame Zelle (wieder, Sie würde gewonnen haben in einem früheren verschieben), was bedeutet, dass:
```
XXX
OOO
XXX
```
nicht erreicht werden kann, während:
```
XXX
OOX
OOX
```
werden kann. Aber können wir eigentlich ignorieren, da es keine Möglichkeit zu gewinnen, zwei Wege, ohne eine gemeinsame Zelle, ohne schon gegen die "maximale Differenz von eins" - Regel, da braucht man sechs Zellen, wobei der Gegner nur mit drei.

Also ich würde einfach mit roher Gewalt und, für jede position, wo der Unterschied ist null oder eins zwischen den Grafen, überprüfen Sie die acht ausgezeichneten Möglichkeiten für beide Seiten. Unter der Annahme nur einer von Ihnen hat den Sieg, das ist legal, zu-gewinnen-Spiel.

Unten ist ein proof-of-concept in Python, aber erst die Ausgabe von time bei Ausführung auf dem Prozess der das senden der Ausgabe /dev/null zu zeigen, wie schnell es ist:
```
real    0m0.169s
user    0m0.109s
sys     0m0.030s
```
Code:
```
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
```
Als ein Kommentator hat darauf hingewiesen, gibt es eine weitere Einschränkung. Der Gewinner für ein bestimmtes board kann nicht weniger Zellen als die Verlierer da, dass heißt der Verlierer nur verschoben, obwohl der Gewinner schon gewonnen auf den letzten Zug.

Werde ich nicht ändern Sie den code das zu berücksichtigen, aber es wäre eine einfache Materie, zu überprüfen, wer hat die meisten Zellen (die Letzte person, die umgezogen ist) und die Sicherstellung der Gewinnlinie zu Ihnen gehörte.

möglich, aber zu welchem Zweck? Brauchen wir nicht, um Zeit zu sparen oder Raum hier, und mit bits bedeutet, Verpackung und Auspacken das ist wahrscheinlich, um den code more - Komplex. Es sei denn, ich habe missverstanden, in dem Fall würde ich apprciate Klärung.
Ich bekam Ihren Punkt 🙂 Total vergaß Raum option, also nehme ich wieder mein Kommentar 🙂
Ein Unterschied, der einen bewegen sollte nicht erlaubt sein, in beide Richtungen. Der Verlierer kann sich nicht bewegen, nachdem der Gegner gewonnen hat.
guter Punkt, werde ich hinzufügen, dass in der Antwort, aber ich nicht die Mühe mit dem ändern des Codes.
Danke @paxdiablo für die ausführliche Antwort! Würden Sie bitte klären, was Los ist mit dem code, speziell in der letzten for-Schleife, für uns nicht php-Entwickler?

InformationsquelleAutor paxdiablo
1

Andere Möglichkeit könnte sein, starten Sie mit jeder der acht Positionen gewinnen,
```
xxx ---
--- xxx
--- --- ... etc.,
```
und rekursiv füllen Sie alle rechtlichen Kombinationen (beginnen Sie mit dem einfügen von 2 o's, dann fügen Sie eine x für jeden o ; vermeiden o Gewinn-Positionen):
```
xxx xxx xxx
oo- oox oox
--- o-- oox ... etc.,
```
InformationsquelleAutor גלעד ברקן

Dies ist ein java-äquivalent-code-Beispiel

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

}

}
`

InformationsquelleAutor Vijay Rumao

Heute hatte ich ein interview mit Apple und ich hatte die gleiche Frage. Ich konnte nicht denken, nun, in diesem moment. Später wird man auf, bevor Sie sich zu einem treffen schrieb ich die Funktion für die Kombinationen in 15 Minuten, und als ich zurück kam aus der Versammlung schrieb ich die überprüfung der Funktion wieder in 15 Minuten. Ich werde nervös bei interviews, die Apple nicht vertraut meinem Lebenslauf, den Sie nur glauben, was Sie sehen in dem interview, ich gebe Ihnen keine Schuld, viele Unternehmen sind die gleichen, ich sage nur, dass etwas in dieser Einstellung sieht nicht ganz schlau.

Sowieso, hier ist meine Lösung in Swift 4, es sind 8 Zeilen code, die für die Kombinationen-Funktion und 17 Zeilen code zu überprüfen, die eine gültige board.

Prost!!!

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

InformationsquelleAutor user5117217

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.