While solving backtracking problems, I stumbled upon different puzzle problems which can be solved using backtracking. I was wondering if anyone has some interesting problems regarding puzzle problems, which seems to be quite interesting to me for a moment. Google recently asked the puzzle, 'Lights Out' which seemed quite interesting when I read through the problem. Link - https://leetcode.com/discuss/interview-question/422725/google-phone-screen-lights-out-puzzle
Problems which are non-trivial, though I am more interested in puzzles 😛
If you know a good algorithmic way of solving lights out please share ur thoughts here. It can be solved using linear algebra. I gave this problem a good thought and the search space is always exponential without matrix inversions or guassian elimination.
It's an NP hard problem. Only way to solve it is using backtracking in exponential time
It's not np hard. It can be solved by linear algebra in polynomial time
Could you explain a bit how do you backtrack the solution? ... Have been thinking about it but don't get it ..
I imagine a BFS type thing, right?
India
Yesterday
694
'Hindutva': The Radical Hindu Ideology That Seeks to 'Push Christianity Out of India’
India
6h
184
Modiji the greatest ever?
2024 Presidential Election
Yesterday
177
Canceling debt isn’t inflationary or costing tax payers
Personal Finance
Yesterday
1354
Thank you AAPL and NVDA
World Conflicts
Yesterday
570
Is "From the River to the Sea" So Wrong?
YeetCode
*dab*