Trgt_2021_explosion's blog

General Idea for Solving Chess based problems
By Trgt_2021_explosion, history, 4 years ago, In English

Hi Almighty CF Community,

First I googled a lot but didn't get any explanation.(However code is available)

I feel it difficult to solve problems of type "no of ways to arrange some elements of chess so that they are attacking/not attacking each other." I was solving CSES Two Knights problem and I am struggling to come up by a general formula.

I will request if any one can explain the idea behind such problems in general? or at least for this Two Knights problem.

$$$If \,you\, know \,some \,chess \,based \,problems, \,I \,will\, request\, you \,to \,please \,share \,it. \,Thanks.$$$

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If two knight attack each other then they will be in 2*3 rectangle or 3*2 rectangle. So the number of ways of placing them is (n-1)*(n-2)+(n-2)*(n-1). Also in each rectangle no ways of placing the knight is 2. So total ways of placing knight so that they attack each other will be 2*2*(n-1)*(n-2). So the number of ways such that knight do not attack each other will be n*n*(n*n-1)/2 — 4*(n-1)*(n-2)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the reply. One doubt total no of arrangement is $$$n^2(n^2-1)$$$ right? Because all the cells of chess are unique and this two knights are also different.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Two knights are same as it is not mentioned different explicitly in the question.

      So interchanging the knights position will not going to create new ways.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is no need to think. For each number of possible moves (2, 3, 4, 6 and 8) it is very easy to count the number of squares where you have this number of possible moves. For example, 2 moves are possible only from the corners, and there are 4 corners.

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

you can use Lagrange polynomial to find the expression, just take enough points( n, answer pairs) and brute force it.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Can you explain why it is a polynomial?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it -12 Vote: I do not like it

      actually, sometime back I was solving a problem in which I used this and got the correct result. I don't have solid proof, but these were my thoughts that kinda convinced me and might convince you though I agree it's somewhat wage, let's increase the size of the chessboard by 1 unit, f(n+1)-f(n) is a polynomial in n because only polynomial more new places/orientation are created. (to be specific O($$$n^2$$$))

      (you can argue it might be a difference of some Taylor series expansion of some non-polynomial, but then again that function must be a mapping to infinite integer set, so that makes it difficult to not be polynomial according to my understanding, I am open to any suggestion on this.)

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$f(n + 1) - f(n)$$$ is $$$O(n^2)$$$, but that doesn't make it a polynomial, it only means that it's bounded above by a polynomial. I don't know what the text in the brackets means.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 4   Vote: I like it +12 Vote: I do not like it

          do you agree f(n+1)-f(n) will be polynomial? Rest of this only make sense to me if you agree to it, I don't know, seeing the downvotes I think everybody knows/says it's not polynomial,then it's fine, I should be wrong, just igonre it, or give it downvotes.

          In bracket, I meant that as some nonpolynomial can be written as polynomial as their Taylor series expansion, but I couldn't think of such a valid function, that have f(n+1)-f(n) O($$$n^2$$$) and an integer as output for every integer input.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It will, but only if we don't look at $$$n \le 5$$$ and not for the reasons you mentioned. I just did the math like dalex told.

            There are many functions that have $$$f(n+1)-f(n) \in O(n^2)$$$ that are not polynomial. For example the minimum of two cubics. And a lot of functions that are the answer to some combinatorics problem.

            → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can watch this video : Editorial to 3 knights variation of the same problem. The audio is not that clear though, Still, you can understand the concept from this. Also, these sequences are generally available in OEIS, and hence googling the first few values works most of the time.

→ Reply