Finding all 92 solutions to the 8x8 N-Queens problem.
This is my C source for the 84+CE , although it might be an old version that I've since altered. It expects the size of the chess board (1 to 10) in the variable 'N' and returns a list of 2 integers in the list variable L1, the first of which is the number of solutions found and the second is the number of "nodes" tested. It doesn't update the display every time a solution is found, only once every 16 solutions, in order to avoid slowing things down too much.
Code:
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <tice.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fileioc.h>
char *bfr;
void nrow(unsigned int row, unsigned int *solution, unsigned int size, unsigned int *nbSolutions, unsigned int *nbNodes);
void printBfrAt(uint8_t line, uint8_t col);
void showProgress(int sol, int nodes, int skip);
void main(void) {
real_t *realVariable;
unsigned int boardSize;
unsigned int nbSolutions = 0;
unsigned int nbNodes = 0;
unsigned int *solution;
list_t *resultList;
bfr = (char *)malloc(32);
// Recall the value of 'N' (size of the chess board)
if (!ti_RclVar(TI_REAL_TYPE, ti_N, &realVariable)) {
boardSize = (unsigned int)abs(os_RealToInt24(realVariable));
if ((boardSize <= 10) && boardSize) {
os_ClrHome();
solution = (unsigned int *)calloc(boardSize, sizeof(int));
showProgress(0,0,0);
nrow(0, solution, boardSize, &nbSolutions, &nbNodes);
free(solution);
showProgress(nbSolutions,nbNodes,0);
// Store the results in the list L1
resultList = ti_MallocList(2);
resultList->items[0] = os_Int24ToReal(nbSolutions);
resultList->items[1] = os_Int24ToReal(nbNodes);
ti_SetVar(TI_REAL_LIST_TYPE, ti_L1, resultList);
free(resultList);
}
}
free(bfr);
}
void nrow(unsigned int row, unsigned int *solution, unsigned int size, unsigned int *nbSolutions, unsigned int *nbNodes) {
unsigned int col;
unsigned int testRow;
unsigned int safe;
for (col=0; col<size; col++)
{
(*nbNodes)++;
safe = 1;
for (testRow=0; testRow<row; testRow++)
{
if ((col == solution[testRow]) || (abs(col - solution[testRow])==(row-testRow)))
{
safe = 0;
break;
}
}
if (safe)
{
if (row==(size-1))
{
++(*nbSolutions);
showProgress(*nbSolutions, *nbNodes, 1);
}
else
{
solution[row] = col;
nrow(row+1,solution,size,nbSolutions,nbNodes);
}
}
}
}
void printBfrAt(uint8_t line, uint8_t col) {
os_SetCursorPos(line, col);
os_PutStrFull(bfr);
}
void showProgress(int sol, int nodes, int skip) {
if (skip && (sol & 0x0F)) return;
sprintf(bfr, "Solutions: %u", sol);
printBfrAt(0,0);
sprintf(bfr, "Nodes: %u", nodes);
printBfrAt(1,0);
}