Jump to content

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


Recommended Posts

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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?

Link to comment
Share on other sites

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?

?>

 

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.... 🙂

Link to comment
Share on other sites

<!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>

image.png.9604c2a268a8a5e392acd5bbebf2629b.png

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.
Link to comment
Share on other sites

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>

image.png.9604c2a268a8a5e392acd5bbebf2629b.png

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.

 

faster.jpg

Link to comment
Share on other sites

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

FYI - 8 queens solution...

image.png.0bb9dee96cabe02417889ca0aedaaf69.png

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.

 

angler-wrangler-dangler.jpg

Link to comment
Share on other sites

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

FYI - 8 queens solution...

image.png.0bb9dee96cabe02417889ca0aedaaf69.png

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.