Προς το περιεχόμενο

To πρόβλημα των 8 βασιλισσών σε C++

spyros83

Από τον spyros83
στο Προγραμματισμός

Προτεινόμενες αναρτήσεις

spyros83 Proficient

spyros83

Δημοσ.
Δημοσ.

Δεν παίρνω κάποιο λάθος κατά την εκτέλεση αλλά σαν αποτέλεσμα παίρνω αυτό 1222222212222222

Μπορεί να βοηθήσει κάποιος;

 

Υ.Γ. Δεν πρόκειται για εργασία αλλά για δική μου ενασχόληση και μόνο.

Παραθέτω τον κώδικα :

 

>#include <iostream>
using std::cout;
using std::endl;

int a[8];

int place (int k) {
for (int i = 1; i < k; i++){
	if (a[i] == a[k])
		return 0;
	else
		return 1;
}
}
void display() {
for (int i =1; i <=8; i++){
	cout << a[i];
}
}
int main(){
for (int i = 2; i <=8; i++)
	a[i] = 0;
int k = 1;
while (k > 0){
	a[k]++;
	while (!place(k))
		a[k]++;
	if(a[k] > 8){
		a[k] = 0;
		k--;
	}
	if(k == 8){
		display();
	}
	k++;
}
}

defacer Grand Master

defacer

Δημοσ.
Δημοσ.

Πέραν του ότι μετράς από το 1 (just don't do it!) και άρα το πρόγραμμα έχει τουλάχιστον ένα undefined behavior σημείο, όπου κάνει access το 9ο στοιχείο του a (δηλαδή το a[8]) ενώ ο a έχει μόνο 8 στοιχεία (a[0] μέχρι α[7]):

 

>
void display() {
       for (int i =1; i <=8; i++){
               cout << a[i];
       }
}

 

...ο κώδικάς σου είναι δυσνόητος. Ίσως θα ήταν καλύτερα να τον ξαναγράψεις έτσι που να είναι πιο εύκολα κατανοητός γιατί αναγκάζεις τον κόσμο να καταβάλλει αχρείαστο κόπο προκειμένου να σε βοηθήσει, κάτι που κάποιος μπορεί να μην είναι διατεθειμένος να κάνει.

dewn735 Veteran

dewn735

Δημοσ.
Δημοσ.

Spyros83, η λύση προϋποθέτει την ύπαρξη δισδιάστατου πίνακα θέσεων 8x8 (σκακιέρα γαρ!) οπότε αυτό που γράφεις είναι καταδικασμένο να πάει άπατο. Είσαι σίγουρος ότι έχεις καταλάβει ποιο είναι το πρόβλημα και τι ακριβώς ζητάει σαν λύση; Και τι ακριβώς προσπάθησες να κάνεις με αυτόν κώδικα;

V.I.Smirnov Experienced

V.I.Smirnov

Δημοσ.
Δημοσ.

Δες εδώ μια λύση της προκοπής.

Κομψή και πλήρως αντικειμενοστρεφής.

 

>
/*

***************************
*  8 Queens problem demo  *
*                         *
******************************


       V.I.Smirnov 
      ~~~~~~~~~~~~~

******************************

*/

#include <stdio.h>

const int TRUE  = 1;
const int FALSE = 0;



class Queens {
 private:
   int      BOARD_SIZE;   
   int      *chessboard;
   void     init_chessboard(void);

 public:
   Queens(int bd_size);  
   ~Queens();             
   int      is_safe_to_move(void);
   int      add_nonattacking_queen (int position);
   void     display_chessboard(void);
};


Queens::Queens(int bd_size)
{
  BOARD_SIZE = bd_size;
  chessboard = new int [bOARD_SIZE * BOARD_SIZE];
  init_chessboard();
}

Queens::~Queens(void)
{
  delete  [] chessboard;
}

void Queens::init_chessboard(void)
{
  for (int i = 0; i < BOARD_SIZE; i++)
     for (int j = 0; j < BOARD_SIZE; j++)
        //  chessboard[i][j] = FALSE;
        chessboard[i * BOARD_SIZE + j] = FALSE;
}



int Queens::is_safe_to_move(void)
{

  int i,j,k,l;

  for (i = 0; i < BOARD_SIZE; i++)
    for (j = 0; j < BOARD_SIZE; j++)
       if (chessboard[i * BOARD_SIZE + j] == TRUE) {
         for (k = 0; k < BOARD_SIZE; k++)
            if ((chessboard[k * BOARD_SIZE + j] == TRUE)
                 && k != i)
               return FALSE;

         for (l = 0; l < BOARD_SIZE; l++)
            if ((chessboard[i * BOARD_SIZE + l] == TRUE)
                 && l != j)
               return FALSE;

         for (k = i + 1, l = j + 1;
              k < BOARD_SIZE && l < BOARD_SIZE; k++, l++)
            if (chessboard[k * BOARD_SIZE + l] == TRUE)
               return FALSE;

         for (k = i - 1, l = j - 1;
              k >= 0 && l >= 0; k--, l--)
            if (chessboard[k * BOARD_SIZE + l] == TRUE)
               return FALSE;

         for (k = i + 1, l = j - 1;
              k < BOARD_SIZE && l >= 0; k++, l--)
            if (chessboard[k * BOARD_SIZE + l] == TRUE)
               return FALSE;

         for (k = i - 1, l = j + 1;
              k >= 0 && l < BOARD_SIZE; k--, l++)
            if (chessboard[k * BOARD_SIZE + l] == TRUE)
               return FALSE;
       }
  return TRUE;
}



int Queens::add_nonattacking_queen (int position)
{
  int  outcome = FALSE;
  for (int k = 0; k < BOARD_SIZE && outcome == FALSE;
           k++) {
     if (position >= BOARD_SIZE)
        return TRUE;
     else {
       chessboard[position * BOARD_SIZE + k] = TRUE;
       if ((add_nonattacking_queen(position + 1) == TRUE) && 
           (is_safe_to_move() == TRUE))
           outcome = TRUE;
       else
         chessboard[position * BOARD_SIZE + k] = FALSE;
     }
  }
  return outcome;
}



void Queens::display_chessboard (void)
{
  for (int i = 0; i < BOARD_SIZE; i++) {
     int  printQ_flag = 0;
     printf("---------------------------------\n");
     for (int j = 0; j < BOARD_SIZE; j++) {
        if (chessboard[i * BOARD_SIZE + j] == TRUE) {
          if ((j == 0 && printQ_flag == 0) ||
              (printQ_flag != 0))
             printf("| Q ");
          else
             printf(" Q ");
          printQ_flag = 1;
        }
        else {
          if (printQ_flag == 1) {
             printf("|   |");
             printQ_flag = 0;
          }
          else if (j == 0)
             printf("|   |");
          else
             printf("   |");
        }
     }
     if (printQ_flag == 1)
        printf("|");
     printf("\n");
   }
   printf("---------------------------------\n");
}



void main(void)
{
  Queens EightQ(8);

    printf("\n **  OOP implementation %s ** %s\n",
         "of 8 Queens Problem", 
         "\n\n            (c) V.I.Smirnov\n");

  if (EightQ.add_nonattacking_queen(0) == TRUE)
    EightQ.display_chessboard();
  else
    printf("\n Failed to place Queens.\n");
}

 

Τα σχόλια τα έχω βγάλει επίτηδες...

 

-

defacer Grand Master

defacer

Δημοσ.
Δημοσ.

Spyros83, η λύση προϋποθέτει την ύπαρξη δισδιάστατου πίνακα θέσεων 8x8 (σκακιέρα γαρ!) οπότε αυτό που γράφεις είναι καταδικασμένο να πάει άπατο. Είσαι σίγουρος ότι έχεις καταλάβει ποιο είναι το πρόβλημα και τι ακριβώς ζητάει σαν λύση; Και τι ακριβώς προσπάθησες να κάνεις με αυτόν κώδικα;

 

Δεν είναι ακριβώς έτσι. Όταν κάποτε έλυσα και γω αυτή την άσκηση χρησιμοποίησα μονοδιάστατο πίνακα όπου αποθηκεύεις μόνο τη μία συντεταγμένη (η άλλη συντεταγμένη είναι implied από το index του πίνακα, μιας και δε μπορούν να υπάρξουν 2 βασίλισσες στην ίδια γραμμή ή στήλη). Μου φαινόταν πιο απλό και λογικό τότε, κι εξακολουθεί να μου φαίνεται το ίδιο τώρα.

 

Για ποιό λόγο να παιδεύεσαι με 7 έξτρα τιμές ανά συντεταγμένη αφού δε χρειάζεται;

dewn735 Veteran

dewn735

Δημοσ.
Δημοσ.

Δεν την έχω λύσει ποτέ την άσκηση, οπότε σαν πρώτη λύση μου ήρθε η "οπτική" αναπαράσταση.... ούτε καν το σκέφτηκα αυτό!

η άλλη συντεταγμένη είναι implied από το index του πίνακα, μιας και δε μπορούν να υπάρξουν 2 βασίλισσες στην ίδια γραμμή ή στήλη
defacer Grand Master

defacer

Δημοσ.
Δημοσ.

Έτσι για το χαβαλέ, έγραψα και γω μια λύση σε C++. Προσπάθησα να ακολουθήσω την ίδια ιδέα που είχα όταν την πρωτοέκανα αλλά πάνε πολλά χρόνια και σίγουρα αυτή εδώ είναι καλύτερη λόγω εμπειρίας. Το πνεύμα όμως είναι το ίδιο (βγάλε τη λύση με όσο το δυνατόν λιγότερη δουλειά και όχι πολύ κώδικα παρακαλώ).

 

Δείτε την στο ideone.

spyros83 Proficient

spyros83

Δημοσ.
  • Μέλος
Δημοσ.

Δεν είναι ακριβώς έτσι. Όταν κάποτε έλυσα και γω αυτή την άσκηση χρησιμοποίησα μονοδιάστατο πίνακα όπου αποθηκεύεις μόνο τη μία συντεταγμένη (η άλλη συντεταγμένη είναι implied από το index του πίνακα, μιας και δε μπορούν να υπάρξουν 2 βασίλισσες στην ίδια γραμμή ή στήλη). Μου φαινόταν πιο απλό και λογικό τότε, κι εξακολουθεί να μου φαίνεται το ίδιο τώρα.

 

Για ποιό λόγο να παιδεύεσαι με 7 έξτρα τιμές ανά συντεταγμένη αφού δε χρειάζεται;

 

 

Φίλε όλο αυτό το έκανες εσύ και για τον χαβαλέ κιόλας...?χαχαχα... νιώθω πολύ λίγος πραγματικά... Τα solutions 92 που γράφεις είναι οι λύσεις? Γιατί εγώ ήξερα ότι έχει 12 μοναδικές λύσεις...!!!

Αρχειοθετημένο

Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.

Προς την λίστα θεμάτων
  • Δημιουργία νέου...