Author Topic: Logic Puzzles  (Read 79278 times)

0 Members and 1 Guest are viewing this topic.

Offline Simon

  • Administrator
  • Posts: 3935
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #195 on: April 02, 2022, 11:12:25 AM »


More cute graph theory.

Let G be an undirected graph with n ≥ 2 nodes, with only simple edges, i.e., no multiple edges. Prove the following statement or construct a counterexample: There exist two nodes in G that have exactly the same number of touching kittens edges.

Example: In the picture, both A and B have two edges each.

Example: if G contains only n = 2 nodes, they're either connected (and both have 1 edge) or not (and both have 0 edges); in either case, G contains two nodes with the same number of edges. Thus, the statement is true at least for two-node graphs.

-- Simon

« Last Edit: July 15, 2023, 05:05:13 PM by Simon »

Offline Armani

  • Posts: 574
  • :D
    • View Profile
Re: Logic Puzzles
« Reply #196 on: April 02, 2022, 11:46:38 AM »
Assume no two nodes have exactly the same number of edges.
Then the number of edges of every nods = {0,1,2, ... , n-1}
but this is impossible
contradiction!
My newest Neolemmix level pack : Lemmings Halloween 2023 :D 8-)

About Armani: Armani's Blog
My NL level packs(in chronological order):
  Lemmings Uncharted [Medium~Extreme]
  Xmas Lemmings 2021 [Easy~Very Hard]
  Lemmings Halloween 2023 [Easy-Very Hard]

Offline Simon

  • Administrator
  • Posts: 3935
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #197 on: April 02, 2022, 02:12:08 PM »
Yep! For completeness, elaborate why exactly it's impossible to have excatly the edge counts 0, 1, ..., n − 1.

Your proof was the first that I found, too. Here is a second proof that I found today:
Spoiler (click to show/hide)

-- Simon

Offline Armani

  • Posts: 574
  • :D
    • View Profile
Re: Logic Puzzles
« Reply #198 on: April 02, 2022, 02:22:52 PM »
Quote
Yep! For completeness, elaborate why exactly it's impossible to have excatly the edge counts 0, 1, ..., n − 1.

0 means there's a nod which is connected to no other nods
n-1 means there's a nod which is connected to all other nods
They can't both be true simultaneously 8-)
My newest Neolemmix level pack : Lemmings Halloween 2023 :D 8-)

About Armani: Armani's Blog
My NL level packs(in chronological order):
  Lemmings Uncharted [Medium~Extreme]
  Xmas Lemmings 2021 [Easy~Very Hard]
  Lemmings Halloween 2023 [Easy-Very Hard]

Offline geoo

  • Administrator
  • Posts: 1481
    • View Profile
Re: Logic Puzzles
« Reply #199 on: April 04, 2022, 10:20:13 AM »
Here's a Lix-related logic puzzle (which I haven't solved yet):

You're building a N-player level where each player has M hatches.

The hatches are arranged into a grid of M rows and N columns. But the player order is wrong!
You need that in each column, all hatches belong to the same player, and in each row, the hatches spawn lixes at the same time.
You don't want to move the hatches around (error-prone), but you can fix this by changing the priority of a few of them.
How many hatches do you have to click to be guaranteed to be able to sort this out, regardless of the initial arrangement?

About priorities: If my hatches are ordered 1, 2, 3, 4, 5, and I decrease the priority of #4 down to 2, the priority of #2 and #3 gets increased by 1 each, giving 1, 3, 4, 2, 5.
If the players are A, B, C and the hatches per player are A1, A2, A3, then the hatches are ordered
A1, B1, C1, A2, B2, C2, A3, B3, C3
1   2   3   4   5   6   7   8   9

Example: N=2, M=2.
A2 B1    3 2
B2 A1 or 4 1

If I increase the priority of A1 to A2, I get
B1 A1    2 1
B2 A2 or 4 3

So clicking one hatch is sufficient. Is one hatch sufficient for every starting configuration for N=2, M=2?

Remark: This is from a real example where I was trying to build a level, and clicking hatches was expensive as they were buried under eraser terrain, which had to be removed first to access the hatch.
« Last Edit: April 05, 2022, 09:08:19 PM by geoo »

Offline Dominator_101

  • Posts: 15
    • View Profile
Re: Logic Puzzles
« Reply #200 on: April 05, 2022, 05:20:56 PM »
So I was thinking of a different approach to the graph problem, but I kept hitting snags in my logic so I might think that over longer.

For Geoo's issue, I'm not sure if I 100% understand the priority orders you laid out. I think I figured out your initial example and was just conceptualizing it differently. I'm still unclear on the second example. You first say that the hatches would go A1, B1, A2, C2 as 1,2,3,4 respectively, but in the side by side examples it looks like A1 is 1 and B2 is 2? I also don't really follow how the rearrangement happens there. Not sure if I'm just missing something.

Here's some thoughts, based on my assumption of how the ordering works:
Spoiler (click to show/hide)

Offline Simon

  • Administrator
  • Posts: 3935
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #201 on: June 14, 2022, 08:19:30 AM »
geoo's hatch distribution is still open.



What is the minimum number of knights to put on an 8x8 chessboard such that the knights attack every vacant square?

Example with 16 knights (click to show/hide)

Can you do better than this? I don't even have intuition whether optimal solutions will be symmetrical or asymmetrical.

Downsides with this kind of puzzle: It's not pure logic, it's optimization, thus borderline off-topic for the thread of pure logic puzzles. And I don't know the solution; I believe that optimiality is hard to prove. Although -- we did a good job on the lights in the wagons: We proved that O(n) is optimal, even though that wasn't part of the initial puzzle.

Thus, feel free to just skip the knights and post another puzzle. :8():

-- Simon
« Last Edit: June 14, 2022, 08:30:10 AM by Simon »

Offline Armani

  • Posts: 574
  • :D
    • View Profile
Re: Logic Puzzles
« Reply #202 on: June 14, 2022, 09:15:56 AM »

Every coloured square can only be covered by unique different knights which means you can't cover the whole board with less than 12knights.

And it's possible to cover the whole chessboard with 12knights. Here's an example:



So the answer is 12.
My newest Neolemmix level pack : Lemmings Halloween 2023 :D 8-)

About Armani: Armani's Blog
My NL level packs(in chronological order):
  Lemmings Uncharted [Medium~Extreme]
  Xmas Lemmings 2021 [Easy~Very Hard]
  Lemmings Halloween 2023 [Easy-Very Hard]

Offline Simon

  • Administrator
  • Posts: 3935
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #203 on: June 14, 2022, 07:26:21 PM »
Excellent solution with proof of minimality, nice!

-- Simon

Offline DireKrow

  • Noisy Crow
  • Posts: 113
    • View Profile
Re: Logic Puzzles
« Reply #204 on: June 18, 2022, 07:49:15 PM »
I've been getting into Nikoli-style logic puzzles recently, solving a few when I have the time, but I also went ahead and created some of my own puzzles. They're nothing too fancy, but I'm pretty happy with them for a first attempt. They use a ruleset which combines Simple Loops with Nonograms. I dub it, the Nonoloop.


Rules

- Draw a single non-intersecting loop through the centers of all cells. The loop may only move horizontally or vertically and may only make 90-degree turns.
- Clues outside the grid represent the lengths of the blocks of consecutive turns that the loop makes in the corresponding row or column, in order.

E.g. "2" means the loop turns in two consecutive cells in that column, while "1 1" means the loop turns in one cell and then another non-consecutively.

Example (click to show/hide)


Puzzles

Nonoloop 1 (click to show/hide)

Nonoloop 2 (click to show/hide)

Nonoloop 3 (click to show/hide)

Nonoloop 4 (click to show/hide)


And attached is a single pdf with the rules and all puzzles, if that's preferred
LOTY 2020 Winner
My NeoLemmix Levels: The Krow Files (File A v1.2 released 21-Feb-2020)

Offline Simon

  • Administrator
  • Posts: 3935
    • View Profile
    • Lix
Re: Logic Puzzles
« Reply #205 on: June 20, 2022, 10:47:26 PM »
The four puzzles are of satisfying quality: solvable with sensible contemplation, but without far-fetched guesswork. Thanks! Attached are my solutions. I printed the PDF and solved with pen and paper.

I knew Nonogram, but didn't know Simple Loop. I discovered several emergent patterns that the Nonoloop solutions must satisfy, and in hindsight, they should apply to Simple Loop, too. Nonetheless -- congrats on designing something with such emergence from only a few given rules! Formalizing the patterns in my mind helped with the later puzzles.

Rule clarifications that I took for granted: When a row contains clues, not only these clues denote the lengths of the blocks of consecutive turns, in order, but also:
  • Any two blocks of the row are separated by one or more straight-loop squares.
  • The clues cover all the blocks of the row, i.e., there are no more turns in that row other than those denoted by the clues.
-- Simon
« Last Edit: September 11, 2022, 01:44:42 PM by Simon »

Offline mobius

  • Posts: 2761
  • relax.
    • View Profile
Re: Logic Puzzles
« Reply #206 on: May 03, 2023, 11:03:10 PM »
I started messing around with Chat GPT 4 recently. I gave it this puzzle:
https://www.lemmingsforums.net/index.php?topic=1389.msg39003#msg39003

It gave the correct answer; its description of the process was pretty thorough as well; more detailed than mine and used two tables. Of course this was a while ago and I can't remember exactly how I solved it myself except what I wrote there, but my description was much shorter than chat GTP's.

Next I gave it this puzzle;

https://www.lemmingsforums.net/index.php?topic=1389.msg96371#msg96371

This was the answer:

Quote
The minimum number of knights required to put on an 8x8 chessboard such that they attack every vacant square is 32. Here's one possible arrangement that achieves this:

mathematica

N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .

In this arrangement, the knights are placed on every other square of the board, such that they attack all the remaining squares. It's important to note that the knights only attack squares that are not occupied by other knights, so we can't simply place 64 knights on the board to cover every square.

Also, this is the minimum number of knights required to cover all the vacant squares on the board, but it doesn't necessarily mean that it's the only solution. There may be other valid arrangements that achieve the same result.

I then asked if it could do it with "all knights themselves are attacked by other knights" and the answer was; no none can be placed and then I realized why it got it wrong but I don't know how to word this correctly.

I was confused at first as well until I realized the question is... well as I said I don't know how to phrase the question correctly, but it is missing a bit of information imo, in the statement of the problem. Chat GPT is solving it as if each square can only be taken in one 'instance'.

also an oddity: why it "forgot" the last column on the chessboard? I'll ask it that later.

I've been getting into Nikoli-style logic puzzles recently, solving a few when I have the time, but I also went ahead and created some of my own puzzles. They're nothing too fancy, but I'm pretty happy with them for a first attempt. They use a ruleset which combines Simple Loops with Nonograms. I dub it, the Nonoloop.

Next I might try the loop puzzles and nonograms and other puzzles but idk if drawing and images is possible with this version I'm using.

Btw; those puzzles are fun but tough! I started trying one myself at work today :D
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


Offline mobius

  • Posts: 2761
  • relax.
    • View Profile
Re: Logic Puzzles
« Reply #207 on: May 04, 2023, 10:57:34 PM »
well this was interesting; I rephrased the question to "what if the theoretical attacks of the knights can overlap?"

It then answered with "If we allow the theoretical attacks of the knights to overlap, then the minimum number of knights needed to cover every square on an 8x8 chessboard reduces to 14."

but the diagram it gave was identical to the first; trying again different yielded the same diagram. So it got closer to the minimal answer (pretty close) but seem to fail at drawing this for some reason. As such I can't be certain if it's really still understanding the problem correctly.

In any case I just realized I'm using Chat GPT 3 not 4, which is supposedly shockingly better than 3. 4 must be paid for it looks like. 3 is still pretty impressive for what it can do and how it does it.
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


Offline chaos_defrost

  • Posts: 908
  • the artist formerly known as Insane Steve
    • View Profile
Re: Logic Puzzles
« Reply #208 on: May 07, 2023, 08:20:40 PM »
If you like pencil and paper style puzzles, I highly recommend Instructionless Grid:
https://ig.logicpuzzle.app

It's.... as the name suggests, there's 100 puzzles, I think I got about 30 or so on my own but I believe the dev intended to have them solved as teams.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Offline mobius

  • Posts: 2761
  • relax.
    • View Profile
Re: Logic Puzzles
« Reply #209 on: June 10, 2024, 10:56:46 PM »
from a discord server I joined recently (cracking the cryptic) I'm learning of tons of kinds of simple puzzle games like this one:

https://puzz.link/p?cocktail/10/10/qhl3aml66ccldaolhb0f7v1guf00uf1gvsu02g13223113930130g31001322

this involves shading a particular number of squares in regions. There's another called Kouchoku that's about drawing loops around nodes.
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain