Advertisement
Guest User

Untitled

a guest
Feb 18th, 2011
1,115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.49 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. //trackers
  6. int solutions[92][64];
  7. int found_sltns = 0;
  8.  
  9. //data structure to store args for the find_queen fn
  10. struct queens_arg {
  11. int board[64];
  12. int focus_idx;
  13. };
  14.  
  15. /*
  16. * Counts the number of queens that exists on a board
  17. */
  18. int no_of_queens(int board[64]) {
  19. int idx;
  20. int total = 0;
  21. #pragma omp parallel for
  22. for (idx = 0;idx < 64;idx++) {
  23. if (board[idx] == 1) total++;
  24. }
  25. #pragma end parallel for
  26. return total;
  27. }
  28.  
  29. /*
  30. * Counts the number of queens in a row
  31. */
  32. int on_row(int board[64], int x, int y) {
  33. int count = 0;
  34. int i;
  35. #pragma omp parallel for
  36. for (i = (y * 8); i < ((y * 8)+8) ;i++) {
  37. if (board[i] == 1)
  38. count++;
  39. }
  40. #pragma end parallel for
  41. return count;
  42. }
  43.  
  44. /*
  45. * Counts the number of queens in a column
  46. */
  47. int on_col(int board[64], int x, int y) {
  48. int count = 0;
  49. int i;
  50. #pragma omp parallel for
  51. for (i = x; i < 64 ;i=i+8) {
  52. if (board[i] == 1)
  53. count++;
  54. }
  55. #pragma end parallel for
  56. return count;
  57. }
  58.  
  59. /*
  60. * Counts the number of queens in diagonals that run both ways.
  61. */
  62. int on_diagonal(int board[64], int x, int y) {
  63. int count = 1;
  64. int idx = coord_to_idx(x,y);
  65. int i;
  66.  
  67. //northwest direction
  68. if ((y > 0) && (x > 0))
  69. for (i = idx - 9; (i >= 0) && (i <= 64) ; i = i - 9) {
  70. if ((board[i] == 1) && (i != idx))
  71. count++;
  72. if (on_edge(i))
  73. break;
  74. }
  75. //northeast direction
  76. if ((y < 7) && (x > 0))
  77. for (i = idx - 7; (i >= 0) && (i <= 64) ;i = i - 7) {
  78. if ((board[i] == 1) && (i != idx))
  79. count++;
  80. if (on_edge(i))
  81. break;
  82. }
  83. //southwest direction
  84. if ((y > 0) && (x < 7))
  85. for (i = idx + 7; (i >= 0) && (i <= 64) ;i = i + 7) {
  86. if ((board[i] == 1) && (i != idx))
  87. count++;
  88. if (on_edge(i))
  89. break;
  90. }
  91. //southeast direction
  92. if ((y < 7) && (x < 7))
  93. for (i = idx + 9; (i >= 0) && (i <= 64) ;i = i + 9) {
  94. if ((board[i] == 1) && (i != idx))
  95. count++;
  96. if (on_edge(i))
  97. break;
  98. }
  99.  
  100. return count;
  101. }
  102.  
  103. /*
  104. * Converts a coordinate to an array index. For example (1,1) refers to index 9.
  105. */
  106. int coord_to_idx(int x, int y) {
  107. return (y*8)+x;
  108. }
  109.  
  110. /*
  111. * Checks if an index positioning lies on the edge of the board
  112. */
  113. int on_edge(int idx) {
  114. int x = idx % 8;
  115. int y = idx / 8;
  116. if ((x == 0) || (x == 7) || (y == 0) || (y == 7))
  117. return 1;
  118. return 0;
  119. }
  120.  
  121. /*
  122. * Checks if all the existing queens (irregardless if it has < 9 or not) are in a good position that prevents them from attacking each other.
  123. * If so, returns false (0), else return true.
  124. */
  125. int good_board(int board[64]) {
  126. int i;
  127. for (i = 0;i<64;i++)
  128. if (board[i] == 1) {
  129. int x = i % 8;
  130. int y = i / 8;
  131. if ((on_row(board,x,y) != 1) || (on_col(board,x,y) != 1) || (on_diagonal(board, x, y) != 1))
  132. return 0;
  133. }
  134. return 1;
  135. }
  136.  
  137. /*
  138. * Adds a board to the solution array
  139. */
  140. void add_solution(int board[64]) {
  141. int i;
  142. //check if sltn already exist
  143. for (i = 0;i<92;i++) {
  144. if (solutions[i] == board) return;
  145. }
  146. #pragma omp parallel for
  147. for (i = 0;i<64;i++) {
  148. #pragma omp critical
  149. solutions[found_sltns][i] = board[i];
  150. #pragma end critical
  151. }
  152. #pragma end parallel for
  153. found_sltns++;
  154. }
  155.  
  156. /*
  157. * Prints a board
  158. */
  159. void print_board(int board[64]) {
  160. printf("\n");
  161. int i;
  162. for (i = 0;i<64;i++) {
  163. if (i % 8 == 0) printf("\n");
  164. printf("%d ", board[i]);
  165. }
  166. printf("\n");
  167. }
  168.  
  169. /*
  170. * Copies an array from one to another.
  171. */
  172. void copy_array(int from[64], int to[64]) {
  173. int i;
  174. #pragma omp parallel for
  175. for (i = 0; i<64;i++) {
  176. if (from[i]) to[i] = 1;
  177. else to[i] = 0;
  178. }
  179. #pragma end parallel for
  180. }
  181.  
  182. /*
  183. * Recursive function using backtracking algorithm to find all possible solutions. Solutions are saved with add_solution() method.
  184. */
  185. void *find_queens(void *args) {
  186.  
  187. //vars
  188. struct queens_arg *data = (struct queens_arg *) args;
  189. int board[64];
  190. copy_array(data->board, board);
  191. int focus_idx = data -> focus_idx;
  192.  
  193. //base cases
  194. if (found_sltns == 92) return;
  195. if (focus_idx == 64) return;
  196. if (!good_board(board)) return;
  197.  
  198. if (no_of_queens(board) == 8) {
  199. //found solution
  200. add_solution(board);
  201. return;
  202. }
  203.  
  204. //begin the recursion
  205. if (no_of_queens(board) < 8) {
  206. //add a queen
  207. int new_board1[64];
  208. int new_board2[64];
  209. int i;
  210. copy_array(board,new_board1);
  211. copy_array(board,new_board2);
  212. new_board1[focus_idx] = 1;
  213.  
  214. struct queens_arg *args1 = malloc(sizeof (struct queens_arg));
  215. struct queens_arg *args2 = malloc(sizeof (struct queens_arg));
  216. (*args1).focus_idx = focus_idx+1;
  217. (*args2).focus_idx = focus_idx+1;
  218. copy_array(new_board1, args1->board);
  219. copy_array(new_board2, args2->board);
  220.  
  221. (*find_queens)(args1);
  222. (*find_queens)(args2);
  223.  
  224. free(args1);
  225. free(args2);
  226. }
  227.  
  228. }
  229.  
  230. main() {
  231.  
  232. //build the board
  233. int board[64] = {
  234. 0,0,0,0,0,0,0,0,
  235. 0,0,0,0,0,0,0,0,
  236. 0,0,0,0,0,0,0,0,
  237. 0,0,0,0,0,0,0,0,
  238. 0,0,0,0,0,0,0,0,
  239. 0,0,0,0,0,0,0,0,
  240. 0,0,0,0,0,0,0,0,
  241. 0,0,0,0,0,0,0,0,
  242. };
  243.  
  244. //begin recursion
  245. struct queens_arg *args = malloc(sizeof (struct queens_arg));
  246. args->focus_idx = 0;
  247. copy_array(board,args->board);
  248. (*find_queens)(args);
  249.  
  250. //prints all possible solutions
  251. int i;
  252. for (i = 0;i<found_sltns;i++) {
  253. print_board(solutions[i]);
  254. }
  255.  
  256. //say goodbye :)
  257. return 0;
  258. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement