language: C (gcc-4.7.2)
date: 616 days 3 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* crude */
 
#define QUEEN 'Q'
#define BLANK '.'
 
int is_valid (char **board, int n, int a, int b)
{
  int i, j;
  
  for (i=0; i<n; i++)
  {
    if (board[a][i] == QUEEN)
      return 0;
    if (board[i][b] == QUEEN)
      return 0;
  }
  
  for (i=a, j=b; (i>=0) && (j>=0); i--, j--)
  {
    if (board[i][j] == QUEEN)
      return 0;
  }
  
  for (i=a, j=b; (i<n) && (j<n); i++, j++)
  {
    if (board[i][j] == QUEEN)
      return 0;
  }
  
  for (i=a, j=b; (i>=0) && (j<n); i--, j++)
  {
    if (board[i][j] == QUEEN)
      return 0;
  }
  
  for (i=a, j=b; (i<n) && (j>=0); i++, j--)
  {
    if (board[i][j] == QUEEN)
      return 0;
  }
  return 1;
}
 
void show_board (char **board, int n)
{
  int i, j;
  
  for (i=0; i<n; i++)
  {
    printf ("\n");
    for (j=0; j<n; j++)
    {
      printf (" %c", board[i][j]);
    }
  }
}
 
int nqdfs_all (char **board, int n, int d)
{
  int i, j, ret = 0;
  
  /* the last queen was placed on the last depth
   * therefore this dfs branch in the recursion 
   * tree is a solution, return 1
   */
  if (d == n)
  {
    /* Print whenever we find one solution */
    printf ("\n");
    show_board (board, n);
    return 1;
  }
    
  /* check all position */
  for (i=0; i<n; i++)
  {
    for (j=0; j<n; j++)
    {
      if (is_valid (board, n, i, j))
      {
        board[i][j] = QUEEN;
        nqdfs_all (board, n, d + 1);
        board[i][j] = BLANK;
      }
    }
  }
  
  return ret;  
}
 
int nqdfs_first (char **board, int n, int d)
{
  int i, j, ret = 0;
  
  /* the last queen was placed on the last depth
   * therefore this dfs branch in the recursion 
   * tree is a solution, return 1
   */
  if (d == n)
    return 1;
    
  /* check all position */
  for (i=0; i<n; i++)
  {
    for (j=0; j<n; j++)
    {
      if (is_valid (board, n, i, j))
      {
        board[i][j] = QUEEN;
        ret = nqdfs_first (board, n, d + 1);
        if (ret)
        {
          /* if the first branch is found, tell about its 
           * success to its parent, we will not look in other
           * solutions in this function.
           */
          return ret;
        }
        else
        {
          /* this was not a successful path, so replace the
           * queen with a blank, and prepare board for next
           * pass
           */
          board[i][j] = BLANK;
        }
      }
    }
  }
  
  return ret;
}
 
int main (void)
{
  char **board;
  int n, i, j, ret;
  
  printf ("\nEnter \"n\": ");
  scanf ("%d", &n);
  
  board = malloc (sizeof (char *) * n);
  for (i=0; i<n; i++)
  {
    board[i] = malloc (sizeof (char) * n);
    memset (board[i], BLANK, n * sizeof (char));
  }
  
  nqdfs_first (board, n, 0);
  show_board (board, n);
  
  printf ("\n");
  return 0;
}
  
 
prog.c: In function ‘main’:
prog.c:141: warning: unused variable ‘ret’
prog.c:141: warning: unused variable ‘j’
prog.c:144: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
  • upload with new input
  • # 5:   show   clone   input   77 days 19 hours ago    Success
  • # 4:   show   clone   input   147 days 0 hours ago    Success
  • # 3:   show   clone   input   147 days 0 hours ago    Success
  • # 2:   show   clone   input   147 days 0 hours ago    Success
  • # 1:   hide   clone   input   616 days 3 hours ago

    result: Success     time: 0.03s    memory: 1856 kB     returned value: 0 

    8
    Enter "n": 
 Q . . . . . . .
 . . . . Q . . .
 . . . . . . . Q
 . . . . . Q . .
 . . Q . . . . .
 . . . . . . Q .
 . Q . . . . . .
 . . . Q . . . .