Can you solve 4 queens problem without using 2d arrays, recursion/backtracking? Just display 1 such solution.

[oslon]

https://www.cs.drexel.edu/~johnsojr/2017-18/fall/CS270/Lectures/8/sat.pdf

How'd you proceed? Language doesn't matter technique matters. You can as well write that into SQL.

[requinix]

Easy: brute force it.

[oslon]

Yeah that's my problem. I am not getting ideas to brute force it.(How to convert it to code)...

 

I know how to solve, but converting it to code is something crazy tough for this problem.

[jodunno]

no arrays, recursion/backtracking?

I had to research what is meant by "4 queens problem". I am not a chess player and i'm a self taught coder. If i am understanding the rules correctly: one per diagonal per row. m4 x n4 and four queens. I would convert the vertices using pythagorean theorem to find the diagonals. Place your marks and store the row and column in a variable. It would be much faster than recursion and arrays anyway. One solution is what you mentioned.

[requinix]

Pythagorean theorem? What?

 

10 hours ago, oslon said:

Yeah that's my problem. I am not getting ideas to brute force it.(How to convert it to code)...

Describe the solution you have in mind and we'll figure out how to convert it into code.

[oslon]

3 hours ago, requinix said:

Pythagorean theorem? What?

 

Describe the solution you have in mind and we'll figure out how to convert it into code.

Here is my solution.

(I only need to find 1 such solution)

Place a queen on board when there is no conflict with the other queen(diagonalwise, row-wise, col-wise)

Do this till you reach the last column.

If there is conflict, reset and start again.

[oslon]

public class Example {
    public static void main(String[] args) {
        int rows = 4;
        int cols = 4;
        int[] queens = {-1, -1, -1, -1, -1, -1, -1, -1};
        displayBoard(rows, cols);

    }

    public static void displayBoard(int r, int c) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                System.out.print("| ");
            }
            System.out.print("|");
            System.out.println();
        }
    }
}

So far I've got upto here but I am unable to process further code. Please don't provide chatgpt solution as my goal is to learn not to solve this problem.

[requinix]

13 minutes ago, oslon said:

Place a queen on board when there is no conflict with the other queen(diagonalwise, row-wise, col-wise)

But where? How do you decide where to make each move? And how do you make sure you don't make the same set of moves in future attempts?

15 minutes ago, oslon said:

If there is conflict, reset and start again.

Doesn't that count as backtracking?

[oslon]

Backtracking allowed with 1d array(no 2d array allowed).

[jodunno]

one mark (queen if you want to play chess) per row per column is not rocket science and not an exercise that is worthy of programming exercise. add vision to your code and logic. If you asked me to find, quote, one solution, then let us prey:

<?php

for ($i = 1; $i <= 4; $i++) {
  echo '<div>';
  for ($j = 1; $j <= 4; $j++) {
      echo '<div style="display: inline-block; padding: 8px; width: 40px;">' . pow($i,2) + pow($j,2) . '</div>';
  } echo '</div>';
}
//instructions: find the matching numbers around the perimiters
//example: find the 5 and opposite 10. find the 25 and the 20
//queens are set one per column per row. finished. what?

?>

 

[oslon]

I've no idea what beer they serve in germany.

[oslon]

I've written a FSM as well.

However, having hard time to translate to code:

if(!solved)

- place queen on 1st col->2nd col->3rd col->4th col

else

- quit

 

[oslon]

How to solve the 4 queens puzzle in Java ? – Memoirs of a Software developer (ajayiyengar.com)

I even see a solution lol but can't formulate my own. 

[requinix]

12 hours ago, jodunno said:

one mark (queen if you want to play chess) per row per column is not rocket science

That's right, it wouldn't be - if that was what the Queens Problem actually was.

But it isn't, as you missed an important restriction in the puzzle: at most one queen per diagonal.

12 hours ago, oslon said:

Backtracking allowed with 1d array(no 2d array allowed).

...but the title says no 2D arrays (a trivial restriction to get around) or recursion or backtracking?

If you can do recursion and backtracking then do recursion and backtracking. That's the straightforward solution.

Which means you need to think about how to do recursion. Recursion is about breaking the problem down into a tiny example, solving that, and then figuring out how to take that tiny solution and expand it a little bit more.
So you should be thinking like this:
1. How can I solve this for a 1x1 grid?
2. How can I take a NxN grid that is valid and place another queen in a valid position using either the N+1 row or N+1 column?

5 hours ago, oslon said:

I've written a FSM as well.

However, having hard time to translate to code:

if(!solved)

- place queen on 1st col->2nd col->3rd col->4th col

else

- quit

You're having a hard time because you're not describing your solution in enough detail.

Programming is about telling the computer how to do what you have in mind. But that means you have to have something in mind first. Don't have that and you won't be able to tell the computer anything.

[jodunno]

27 minutes ago, requinix said:

That's right, it wouldn't be - if that was what the Queens Problem actually was.

But it isn't, as you missed an important restriction in the puzzle: at most one queen per diagonal.

Hello? you disappoint me. The code that i posted must be far over your heads. Two solutions are revealed in the code but two people here are unable to see it. LOL. Pythagorean theorem reveals diagonals (id est right angle triangles), which will place the queens in different diagonals, LOL, in different rows and columns. LOL.

good lord! I feel like i'm talking to a wall. Nevermind. The concept is beyond the both of you. Carry on.... 🙂

[Barand]

<!DOCTYPE html>
<html lang="en">
<head>
<title>4 Queens</title>
<meta charset="utf-8">
<style type='text/css'>
    table {
        border-collapse: collapse;
    }
    td {
        width: 40px;
        height: 40px;
        text-align: center;
        font-size: 16pt;
    }
    tr:nth-child(odd) td:nth-child(even),
    tr:nth-child(even) td:nth-child(odd) {
        background-color: lightgreen;
    }
</style>
</head>
<body>
    <?php
        echo '<table border="1">';
        for ($i = 1; $i <= 4; $i++) {
            echo "<tr>";
            for ($j = 1; $j <= 4; $j++) {
                echo '<td>' . pow($i,2) + pow($j,2) . '</td>';
            } 
            echo '</tr>';
        }
        echo "</table>\n";
    ?>
</body>
</html>

Dear Supreme Being,

Can you put aside your arrogance for a moment and assume that we are 5 year olds (not a wall) and

1. explain the theory behind your Pythagorean solution to the problem and why it "works"
2. explain how the above square then tells us where the four queens should be positioned?

• I've found the 5s but there are no "opposite 10s", only 20s opposite the 5s, so the description is somewhat vague..
• Having found the 5s, 10s, 20s and 25s (why those values in particular?), I now have 8 squares. Given that these are the candidates, the code then needs to find which 4 of these 8 fit the bill.

[jodunno]

14 minutes ago, Barand said:

<!DOCTYPE html>
<html lang="en">
<head>
<title>4 Queens</title>
<meta charset="utf-8">
<style type='text/css'>
    table {
        border-collapse: collapse;
    }
    td {
        width: 40px;
        height: 40px;
        text-align: center;
        font-size: 16pt;
    }
    tr:nth-child(odd) td:nth-child(even),
    tr:nth-child(even) td:nth-child(odd) {
        background-color: lightgreen;
    }
</style>
</head>
<body>
    <?php
        echo '<table border="1">';
        for ($i = 1; $i <= 4; $i++) {
            echo "<tr>";
            for ($j = 1; $j <= 4; $j++) {
                echo '<td>' . pow($i,2) + pow($j,2) . '</td>';
            } 
            echo '</tr>';
        }
        echo "</table>\n";
    ?>
</body>
</html>

Dear Supreme Being,

Can you put aside your arrogance for a moment and assume that we are 5 year olds (not a wall) and

1. explain the theory behind your Pythagorean solution to the problem and why it "works"
2. explain how the above square then tells us where the four queens should be positioned?

• I've found the 5s but there are no "opposite 10s", only 20s opposite the 5s, so the description is somewhat vague..
• Having found the 5s, 10s, 20s and 25s (why those values in particular?), I now have 8 squares. Given that these are the candidates, the code then needs to find which 4 of these 8 fit the bill.

explain nothing. you figure it out. And i'm the guy that only had remedial math classes. And some of my code is already posted in the grid graph thread. pointer: perimeters. Nevermind. Make your mountain out of a mole hill.

 

[Barand]

FYI - 8 queens solution...

The Pythagorean numbers were as much use as a chocolate teapot

[jodunno]

On 9/25/2024 at 3:56 PM, Barand said:

FYI - 8 queens solution...

The Pythagorean numbers were as much use as a chocolate teapot

For Your Information and speaking of arrogance:

"Can you solve 4 queens problem without using 2d arrays, recursion/backtracking? Just display 1 such solution."

4 queens not 8. which simply involves the 40deg connected vertices of the perimiters, which offers two immediate solutions.

the pythagorean theorem affords your consciousness a visual of the process, so that you can better understand it. I guess it doesn't help.

recursion and backtracking is silly and time consuming.

But if you want to discuss an 8x8 matrix, then:
Using the left/west side of the central 40deg diagonal as an example:
we can create a (10 lines of code) loop to gather all of the diagonals and 90deg right triangles (while we're at it).

attached image.

However, i already have 'diagonals' stored in a vertex adjacency of ordinal directions (neighbor) array. One could easily check NW vertex, thus NW vertex loop to the N/S border. Clearing rows and columns requires no further code (if one has constructed a grid graph properly).

I drink coffee.

 

[gizmola]

On 9/25/2024 at 6:56 AM, Barand said:

FYI - 8 queens solution...

The Pythagorean numbers were as much use as a chocolate teapot

Hi Barry,

I think there's a problem with this solution:  2 and 128 are in check with each other.

[Barand]

Dammit!. I Googled for an image of a solution.

So much for AI