Permalink
Cannot retrieve contributors at this time
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
136 lines (128 sloc)
3.74 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Author: Justin Stevens | |
// Date: November 12th, 2019 | |
// Purpose: Solves 8 queens puzzle from any starting location using stochastic hill-climbing algorithm | |
// Possible Improvements: ASCII Art for printing out the solution :-) | |
// Possible Bug Tests: With the randomness, I doubt it would get stuck in a loop, but would be good to check possible starting configs | |
// References: Peter Norvig's "AI: A Modern Approach" | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <math.h> | |
#include <stdbool.h> | |
#define SIZE 8 | |
int conflict_check(int board[SIZE]){ | |
int counter=0; | |
for(int i=0; i<SIZE; i++){ | |
for(int j=i+1; j<SIZE; j++){ | |
if(board[i]==board[j]){ | |
// if they lie in the same row | |
counter++; | |
} | |
else if(abs(board[i]-board[j])==(j-i)){ | |
// if they lie on the same diagonal | |
counter++; | |
} | |
} | |
} | |
return counter; | |
} | |
void find_best_neighbor(int board[SIZE]){ | |
// make a shallow copy to avoid pointers | |
int neighbor[SIZE]; | |
for(int i=0; i<SIZE; i++){ | |
neighbor[i]=board[i]; | |
} | |
// this saved variable will be used as the starting position of the column | |
int saved=0; | |
int best_heuristic=28; // worst possible heuristic to start | |
// best_col and best_row are used as pointers for the best rows and columns | |
int* best_col=(int *)malloc(1*sizeof(int)); | |
int* best_row=(int *)malloc(1*sizeof(int)); | |
// length of array is the length of the above pointers | |
int length_array=1; | |
for(int col=0; col<SIZE; col++){ | |
// start by saving the current value of the column | |
saved=neighbor[col]; | |
for(int row=0; row<SIZE; row++){ | |
// for all rows that are *not* the original one | |
if(row!=saved){ | |
// try updating it | |
neighbor[col]=row; | |
// check how many conflicts now | |
if(conflict_check(neighbor)<best_heuristic){ | |
// if it decreased strictly reset array to 1 | |
length_array=1; | |
// reset heuristic | |
best_heuristic=conflict_check(neighbor); | |
best_col=realloc(best_col, length_array*sizeof(int)); | |
best_col[0]=col; | |
best_row=realloc(best_row, length_array*sizeof(int)); | |
best_row[0]=row; | |
} | |
else if(conflict_check(neighbor)==best_heuristic){ | |
length_array++; | |
// no need to update heuristic | |
best_col=realloc(best_col, length_array*sizeof(int)); | |
best_col[length_array-1]=col; | |
best_row=realloc(best_row, length_array*sizeof(int)); | |
best_row[length_array-1]=row; | |
} | |
} | |
} | |
// back to what it was originally | |
neighbor[col]=saved; | |
} | |
// initializes random number generator | |
int random_swap=rand() % length_array; | |
// adds some stochasticity in how we swap things up :-) | |
board[best_col[random_swap]]=best_row[random_swap]; | |
} | |
bool validate_board(int board[SIZE]){ | |
// Make sure user enters valid input; otherwise returns false | |
for(int i=0; i<SIZE; i++){ | |
if(board[i]<0 || board[i]>7){ | |
return false; | |
} | |
} | |
return true; | |
} | |
void input_board(int board[SIZE]){ | |
// Prompts user to enter in a board as 8 integers | |
printf("Please enter a board: "); | |
for(int i=0; i<SIZE; i++){ | |
scanf("%d", &board[i]); | |
} | |
} | |
int main(int argc, char ** argv){ | |
int board[SIZE]; | |
// Continually ask user for a new board while they haven't entered valid | |
do{ | |
input_board(board); | |
} while(!validate_board(board)); | |
// Track the number of times through the loop | |
int iteration=0; | |
// While there still are conflicts | |
while(conflict_check(board) && iteration<1000){ | |
// Locally improve using stochastic hill-climbing algorithm | |
find_best_neighbor(board); | |
iteration++; | |
} | |
if(!conflict_check(board)){ | |
// Print out solution (Zeb, can you improve below here??) | |
printf("Solution found on %d iteration: \n", iteration); | |
for(int i=0; i<SIZE; i++){ | |
for(int j=0; j<SIZE; j++){ | |
if(j!=board[i]){ | |
printf("-"); | |
} | |
else{ | |
printf("Q"); | |
} | |
} | |
printf("\n"); | |
} | |
} | |
else{ | |
printf("Error: bad starting position\n"); | |
} | |
return 0; | |
} |