scratchpad - User contributions [en]

Main Page

2026-09-11T03:59:00Z

Admin:

{{DISPLAYTITLE:scratchpad}}
Welcome to '''scratchpad''' — my personal notes, diagrams, and random thoughts.

<div class="sc-adminonly"><span id="sc-newnote"></span></div>

== Browse notes ==
<div id="sc-notes-tree">Loading notes…</div>

== Other ==
* [[Special:RecentChanges|Recent changes]]
* [[Special:AllPages|Flat list of all pages]]
* [{{fullurl:Private:Journal/{{LOCALYEAR}}/{{LOCALMONTH}}/{{LOCALDAY2}}|action=edit&preload=Template:DailyJournalPreload}} Create today's note]

Main Page

2026-09-04T03:57:00Z

Admin:

{{DISPLAYTITLE:scratchpad}}
Welcome to '''scratchpad''' — my personal notes, diagrams, and random thoughts.

<div class="sc-adminonly"><span id="sc-newnote"></span></div>

== Browse notes ==
<div id="sc-notes-tree">Loading notes…</div>

== Other ==
* [[Special:RecentChanges|Recent changes]]
* [[Special:AllPages|Flat list of all pages]]
* [{{fullurl:Private:Journal/{{LOCALYEAR}}/{{LOCALMONTH}}/{{LOCALDAY2}}|veaction=edit&preload=Template:DailyJournalPreload}} Create today's note]

DSA/Chessboards and Queens

2026-09-03T04:51:52Z

Admin:

= Chessboard and Queens (CSES) — Backtracking Notes =

'''Problem:''' Place 8 queens on an 8×8 chessboard so that no two queens attack each other. Some squares are ''reserved'' (marked with a star in the input) and cannot hold a queen. Count the number of valid placements.

== Why Is This a Recursion Problem? ==

There are two strong signals that point to recursion (specifically '''backtracking'''):

# '''No natural iterative solution.''' We're placing 8 queens, and the number of valid choices for queen ''k'' depends entirely on how queens 1..k-1 were placed. You'd need 8 nested for-loops, one per queen — and even that doesn't work cleanly, since the number of ''valid'' choices at each level changes dynamically.
# '''Tiny constraints.''' An 8×8 board is a dead giveaway. Constraints this small almost always mean the intended complexity is something like <code>O(2^n)</code> or <code>O(n!)</code> — both are hallmarks of brute-force / backtracking search.

== The Core Idea ==

Since we need exactly one queen per row (8 queens, 8 rows), we can place them '''row by row''':

* Write a recursive function <code>place(row)</code>.
* For the current row, try every column from 0 to 7.
* If the square is free (not reserved) and not attacked, place a queen there, recurse into <code>row + 1</code>, then '''undo the placement''' (this is the "backtrack" step) before trying the next column.
* If <code>row == n</code>, it means all 8 queens were placed successfully — increment the answer.

The undo step is critical: after exploring one branch, the board must be restored to its previous state so the next column can be tried cleanly.

== First Working Version: Brute-Force Attack Checks ==

The simplest (but slowest) way to check if a square is attacked is to literally scan:

* '''Upward''' in the same column, for an existing queen.
* '''Diagonally up-left''' (decrementing both row and column).
* '''Diagonally up-right''' (decrementing row, incrementing column).

This works, and on the actual 8×8 test case it's already fast (a couple of milliseconds), because the search space collapses quickly once conflicts are found. But it does unnecessary work — every single placement attempt re-scans the whole column and both diagonals.

== Optimizing: O(1) Attack Checks ==

Instead of scanning every time, keep track of which columns and diagonals are '''already occupied''' using boolean arrays, updated incrementally as queens are placed and removed.

=== Columns ===

Trivial — one boolean array indexed by column:

<syntaxhighlight lang="cpp">
vector<bool> colAttacked(n, false);
</syntaxhighlight>

=== Diagonals: The Grid Math Trick ===

This is the part worth internalizing, since it comes up in many other grid problems.

There are two diagonal directions on a grid, and each has a simple invariant:

'''Diagonal type 1 (↘ direction, i.e. going down-right / cells where row and column both increase together):'''

Take a 4×4 board and look at the diagonal containing (0,3), (1,2), (2,1), (3,0). Notice:

<math>row + col = 3 \quad \text{for every cell on this diagonal}</math>

The next diagonal over — (1,3), (2,2), (3,1) — satisfies <math>row + col = 4</math>. In general:

: '''Two cells lie on the same "↘"-type diagonal if and only if <math>row + col</math> is the same for both.'''

This matches the geometric fact that a line of the form <math>y + x = c</math> is a straight line tilted at 45°.

'''Diagonal type 2 (↙ direction):'''

Look at (1,0), (2,1), (3,2): here <math>row - col = 1</math> for all of them. In general:

: '''Two cells lie on the same "↙"-type diagonal if and only if <math>row - col</math> is the same for both.'''

'''The negative-index problem:''' <math>row - col</math> can be negative (e.g. row=0, col=7 gives −7), and arrays can't have negative indices. The fix is a constant offset: since the minimum possible value of <math>row - col</math> is <math>-(n-1)</math>, add <math>n - 1</math> to shift everything into the non-negative range:

<math>index = row - col + (n - 1)</math>

Both diagonal arrays need size <math>2n - 1</math> (for n=8, that's 15 — matching the fact that an 8×8 board really does have 15 diagonals in each direction).

== Final Code ==

Same algorithm, three languages. The logic is identical in all three: row-by-row backtracking with O(1) column/diagonal checks via boolean arrays.

<tabber>
|-|C++=
<syntaxhighlight lang="cpp">
#include <bits/stdc++.h>
using namespace std;

int n = 8;
vector<string> grid;

vector<bool> colAttacked(8, false);
vector<bool> diag1Attacked(15, false); // indexed by row + col
vector<bool> diag2Attacked(15, false); // indexed by row - col + (n - 1)

long long answer = 0;

void place(int row) {
if (row == n) {
answer++;
return;
}
for (int col = 0; col < n; col++) {
if (grid[row][col] == '*') continue; // reserved square
if (colAttacked[col]) continue;
if (diag1Attacked[row + col]) continue;
if (diag2Attacked[row - col + n - 1]) continue;

// place queen
colAttacked[col] = true;
diag1Attacked[row + col] = true;
diag2Attacked[row - col + n - 1] = true;

place(row + 1);

// backtrack: undo placement
colAttacked[col] = false;
diag1Attacked[row + col] = false;
diag2Attacked[row - col + n - 1] = false;
}
}

int main() {
grid.resize(n);
for (auto &row : grid) cin >> row;

place(0);
cout << answer << endl;
}
</syntaxhighlight>
|-|Python=
<syntaxhighlight lang="python">
import sys

def place(row):
global answer
if row == n:
answer += 1
return
for col in range(n):
if grid[row][col] == '*':
continue
if col_attacked[col]:
continue
if diag1_attacked[row + col]:
continue
if diag2_attacked[row - col + n - 1]:
continue

col_attacked[col] = True
diag1_attacked[row + col] = True
diag2_attacked[row - col + n - 1] = True

place(row + 1)

col_attacked[col] = False
diag1_attacked[row + col] = False
diag2_attacked[row - col + n - 1] = False

def main():
global n, grid, col_attacked, diag1_attacked, diag2_attacked, answer
n = 8
grid = [input() for _ in range(n)]
col_attacked = [False] * n
diag1_attacked = [False] * (2 * n - 1)
diag2_attacked = [False] * (2 * n - 1)
answer = 0

sys.setrecursionlimit(10000)
place(0)
print(answer)

if __name__ == "__main__":
main()
</syntaxhighlight>
|-|Rust=
<syntaxhighlight lang="rust">
use std::io::{self, Read};

const N: usize = 8;

struct Solver {
grid: Vec<Vec<u8>>,
col_attacked: [bool; N],
diag1_attacked: [bool; 2 * N - 1], // indexed by row + col
diag2_attacked: [bool; 2 * N - 1], // indexed by row + (N - 1) - col
answer: u64,
}

impl Solver {
fn place(&mut self, row: usize) {
if row == N {
self.answer += 1;
return;
}
for col in 0..N {
if self.grid[row][col] == b'*' {
continue; // reserved square
}
if self.col_attacked[col] {
continue;
}
let d1 = row + col;
let d2 = row + N - 1 - col; // usize-safe version of row - col + (N - 1)
if self.diag1_attacked[d1] || self.diag2_attacked[d2] {
continue;
}

self.col_attacked[col] = true;
self.diag1_attacked[d1] = true;
self.diag2_attacked[d2] = true;

self.place(row + 1);

// backtrack: undo placement
self.col_attacked[col] = false;
self.diag1_attacked[d1] = false;
self.diag2_attacked[d2] = false;
}
}
}

fn main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
let grid: Vec<Vec<u8>> = input
.lines()
.take(N)
.map(|line| line.as_bytes().to_vec())
.collect();

let mut solver = Solver {
grid,
col_attacked: [false; N],
diag1_attacked: [false; 2 * N - 1],
diag2_attacked: [false; 2 * N - 1],
answer: 0,
};

solver.place(0);
println!("{}", solver.answer);
}
</syntaxhighlight>
</tabber>

Note: it's '''not necessary''' to actually mark the square in <code>grid</code> as a queen ('Q'); the three boolean arrays already fully capture every constraint we need to check, so there's nothing to gain from also mutating the grid string. The Rust version sidesteps the negative-index offset by rewriting <math>row - col + (n-1)</math> as <math>row + (n-1) - col</math>, which is equivalent but never underflows a <code>usize</code> mid-expression.

== Complexity ==

* Row 0 has at most 8 choices, row 1 has at most 7 (one column already taken), and so on — giving a rough bound of '''O(n!)''', possibly with an extra factor of n from the per-row scan: '''O(n! · n)'''.
* In practice it's '''much faster''' than this bound suggests, because diagonal constraints prune the search tree aggressively. On the empty 8×8 board (the worst case, since nothing is reserved), the recursion has exactly '''92 leaves''' (the well-known number of solutions to the 8-queens problem) and runs in about a millisecond.
* This approach does '''not''' scale to large n (e.g. n = 1000). Placing n non-attacking queens under arbitrary reserved-square constraints is a much harder problem in general — for large boards you need entirely different techniques (or the instance may simply be intractable).

== What Is Backtracking? ==

'''Backtracking''' is the name for exactly this pattern: recursively try a choice, recurse further assuming that choice, and if a later step hits a dead end (no valid moves possible), '''undo the choice''' ("backtrack") and try the next alternative. The name comes from the fact that the recursion tree doesn't just go forward — it routinely retreats and retries.

Some useful mental models:

* It's the same technique behind '''Sudoku solvers''': try a digit, recurse, and if a contradiction is eventually reached, undo and try a different digit.
* Backtracking is typically used to find '''one valid solution''' (Sudoku) or to '''count all valid solutions''' (this problem) when there's no faster closed-form or DP approach — often because the problem is NP-hard in general.
* Backtracking problems are almost always about a "good enough" solution rather than a provably optimal one. There is nearly always room to add smarter pruning:
** Example: if you can detect ''before'' recursing that some later row has only one legal column left, you can propagate that constraint early and cut off huge unproductive branches. This kind of look-ahead pruning can make backtracking '''hundreds or even thousands of times faster''' — but it's an enhancement on top of the base algorithm, not a change to its fundamental structure.

== Key Takeaways ==

* Small constraints (like n = 8) are a strong hint that the intended solution is exponential/factorial-time backtracking.
* Always pair "make a move" with "undo the move" (backtrack) after the recursive call returns — this is what makes the search correct.
* For diagonal checks on a grid, remember:
** <math>row + col</math> is constant along one diagonal direction.
** <math>row - col</math> is constant along the other (add an offset of <math>n - 1</math> to keep indices non-negative).
* Prefer O(1) incremental state (boolean arrays) over re-scanning the board on every check — it turns an already-fast solution into a very fast one.
* Global arrays/variables are common in competitive programming for exactly this kind of state — avoids passing/copying containers on every recursive call.

[[Category:DSA]]
[[Category:Backtracking]]

MediaWiki:Tabberneue-tabbertransclude-category

2026-09-03T04:49:55Z

Admin: Created blank page

MediaWiki:Tabberneue-tabber-category

2026-09-03T04:49:46Z

Admin: Created blank page

2026-08-31T05:04:38Z

Admin: Created page with "== Non-Attacking Knights on a k×k Board == '''Problem.''' For every board size <math>k = 1, 2, \dots, n</math>, count the number of ways to place ''two'' knights on a <math>k \times k</math> chessboard so that they do not attack each other. The core is instead of calculating the possible combinations of placements which is confusing we can do ''total_possibilities - attacking_squares'' ---- === Step 1: Total ways to place two knights, ignoring attacks === A <math>k..."

== Non-Attacking Knights on a k×k Board ==

'''Problem.''' For every board size <math>k = 1, 2, \dots, n</math>, count the number of ways to place ''two'' knights on a <math>k \times k</math> chessboard so that they do not attack each other.

The core is instead of calculating the possible combinations of placements which is confusing we can do ''total_possibilities - attacking_squares''

----

=== Step 1: Total ways to place two knights, ignoring attacks ===

A <math>k \times k</math> board has <math>k^2</math> squares. Placing two (identical, unlabeled) knights on two different squares is just "choose 2 squares out of <math>k^2</math>":

<math display="block">\binom{k^2}{2} = \frac{k^2(k^2-1)}{2}</math>

This is the total number of placements '''before''' removing the ones where the knights attack each other.

----

=== Step 2: Counting the attacking pairs ===

A knight standing at square <math>(x, y)</math> attacks any square that is offset by one of these 8 vectors:

{| class="wikitable"
|-
! Offset (dx, dy)
|-
| (1, 2) || (1, −2) || (−1, 2) || (−1, −2)
|-
| (2, 1) || (2, −1) || (−2, 1) || (−2, −1)
|}

Notice: in '''every''' one of these 8 vectors, the two numbers <math>|dx|</math> and <math>|dy|</math> are just 1 and 2 in some order, with some sign.

'''How many placements exist for one fixed offset (dx, dy)?'''

For the pair of squares <math>(x,y)</math> and <math>(x+dx, y+dy)</math> to both lie on the board, <math>x</math> has <math>k - |dx|</math> valid choices, and <math>y</math> has <math>k - |dy|</math> valid choices. So the count is:

<math>(k - |dx|)(k - |dy|)</math>

Since <math>\{|dx|, |dy|\} = \{1, 2\}</math> for all 8 vectors, this is always:

<math>(k-1)(k-2)</math>

(No need to clamp negative values to zero — if <math>k=1</math>, the factor <math>(k-1)=0</math> already kills the product; if <math>k=2</math>, the factor <math>(k-2)=0</math> does the same. The algebra takes care of small boards automatically.)

'''Summing over all 8 offsets''' gives the total number of ''ordered'' attacking pairs (i.e., "knight A attacks square B" counted separately from "knight B attacks square A"):

<math>8(k-1)(k-2)</math>

But an unordered ''pair'' of squares gets counted twice this way (once in each direction), so the number of unordered attacking pairs is:

<math>E(k) = \frac{8(k-1)(k-2)}{2} = 4(k-1)(k-2)</math>

----

=== Step 3: Subtract to get non-attacking pairs ===

<math>
\text{Answer}(k) = \binom{k^2}{2} - E(k) = \frac{k^2(k^2-1)}{2} - 4(k-1)(k-2)
</math>

----

=== Step 4: Simplify into one closed-form polynomial ===

Expand each piece separately.

'''First term:'''
<math>\frac{k^2(k^2-1)}{2} = \frac{k^4 - k^2}{2}</math>

'''Second term:'''
<math>4(k-1)(k-2) = 4(k^2 - 3k + 2) = 4k^2 - 12k + 8</math>

Put both over a common denominator of 2:

<math>
\text{Answer}(k) = \frac{k^4 - k^2}{2} - \frac{8k^2 - 24k + 16}{2}
= \frac{k^4 - k^2 - 8k^2 + 24k - 16}{2}
</math>

Combine like terms (<math>-k^2 - 8k^2 = -9k^2</math>):

<math>
\text{Answer}(k) = \frac{k^4 - 9k^2 + 24k - 16}{2}
</math>

----

=== Step 5: Sanity check against the example ===

{| class="wikitable"
|-
! k !! Answer(k)
|-
| 1 || 0
|-
| 2 || 6
|-
| 3 || 28
|-
| 4 || 96
|-
| 5 || 252
|-
| 6 || 550
|-
| 7 || 1056
|-
| 8 || 1848
|}

Matches the sample output exactly.

'''Intuition for k=1 and k=2:''' On a 1×1 board there's only one square, so you can't even place two knights (0 ways). On a 2×2 board, <math>\binom{4}{2}=6</math> pairs exist, and a knight move needs at least a 3-wide gap in one direction, so ''none'' of them attack — all 6 count.

----

=== Step 6: Implementation ===

Since the formula is closed-form, each answer is <math>O(1)</math> to compute, so the whole solution is <math>O(n)</math> — trivially fast for <math>n \le 10000</math>.

<syntaxhighlight lang="python">
def f(k):
return (pow(k, 4) - 9 * pow(k, 2) + 24 * k - 16) // 2

n = int(input())

for i in range(1, n + 1):
print(f(i))
</syntaxhighlight>

'''Note:''' the division by 2 is safe as integer division (<code>//</code>) because <math>k^4 - 9k^2 + 24k - 16</math> is always even — this follows directly from the derivation, since it came from summing two integer-valued combinatorial counts (<math>\binom{k^2}{2}</math> and <math>E(k)</math>) that are each themselves always integers, and their difference stays an integer after the <math>\times 2</math> common denominator was cleared.

[[Category:DSA]]