Can't understand why backtracking works here


  • 0
    Z

    The backtracking method assumes that once the first player made his first move, then the second player can't win by iterating all the possibilities.

    However, what if the second player could win when the first player made a sub-optimal move after his first move? In other words, the first player could guarantee a win only when every move he made is the best. Otherwise, he may lose to the second player. Then apparently, backtracking can't guarantee the best move.


  • 0

    @zizhengwu said in Can't understand why backtracking works here:

    what if [...] the first player makes a sub-optimal move after his first move?

    For the question of whether you can guarantee a win (by playing optimally), it's irrelevant what happens if you play sub-optimally.


  • 0
    Z

    @StefanPochmann However the backtracking method will include those games that you didn't play optimally since it iterates all the possibilities. Then why is it correct?


  • 0

    @zizhengwu Because it discards non-optimal plays and keeps only optimal plays?


  • 0
    Z

    @StefanPochmann Thanks, you are right.

    int len;
    string ss;
    bool canWin(string s) {
        len = s.size();
        ss = s;
        return canWin();
    }
    bool canWin() {
        for (int is = 0; is <= len-2; ++is) {
            if (ss[is] == '+' && ss[is+1] == '+') {
                ss[is] = '-'; ss[is+1] = '-';
                bool wins = !canWin(); 
                ss[is] = '+'; ss[is+1] = '+';
                if (wins) return true; // (*)
            }
        }
        return false; // (#)
    } 
    

    the lines * and # actually alternate in ∀ and ∃ between two players during the recursive process which is really tricky.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.