KNIGHT.c

[Rx13]

I've been fooling with this all day. I need some advice solving what I believe is a logic error.I'm trying to find someone who can tell me why this code only works for a 7X7 chessboard or smaller. If I make the size to be 8X8 it never completes the process. If it's no trouble, I hope someone can help lead me to a solution. Thanks!

#include <stdio.h>
#include <stdlib.h>
#define N 8
int board[N][N];

void print_board()
    {
      int i, j;
      for (i=0; i<N; ++i)
        {
        for (j=0; j<N; ++j)
          printf("%5d", board[i][j]);
        printf("\n\n");
        }
    }
int Range(int row, int col)
{
  if (row>=0 && row<N && col>=0 && col<N)
    return 1;
  return 0;
}

int need_visit(int row, int col)
{
  return (Range(row,col) && board[row][col]==0);
}
//move[8][2] is the possible move destinations
void next_move(int row, int col, int move[8][2], int *n)
{
  *n = 0;
  if (need_visit(row-2,col-1)) { move[*n][0]=row-2; move[(*n)++][1]=col-1; }
  if (need_visit(row-2,col+1)) { move[*n][0]=row-2; move[(*n)++][1]=col+1; }
  if (need_visit(row-1,col-2)) { move[*n][0]=row-1; move[(*n)++][1]=col-2; }
  if (need_visit(row-1,col+2)) { move[*n][0]=row-1; move[(*n)++][1]=col+2; }
  if (need_visit(row+1,col-2)) { move[*n][0]=row+1; move[(*n)++][1]=col-2; }
  if (need_visit(row+1,col+2)) { move[*n][0]=row+1; move[(*n)++][1]=col+2; }
  if (need_visit(row+2,col-1)) { move[*n][0]=row+2; move[(*n)++][1]=col-1; }
  if (need_visit(row+2,col+1)) { move[*n][0]=row+2; move[(*n)++][1]=col+1; }
}
int continue(int row, int col)
{                                                                                                                           
  int move[8][2], move_num;                                                                                                 
  if(temp==N*N)                                                                                                             
  return 1;                                                                                                                 
  next_move(row, col, move, &move_num);                                                                                     
  while(move_num--)                                                                                                         
    {                                                                                                                       
      int move_row = move[move_num][0];                                                                                     
      int move_col = move[move_num][1];                                                                                     
      board[move_row][move_col] = ++temp;                                                                                   
      if (continue(move_row,move_col))                                                                                      
        return 1;                                                                                                           
      board[move_row][move_col] = 0;                                                                                        
      --temp;                                                                                                               
    }                                                                                                                       
  return 0;                                                                                                                 
}


int main()
{
  int StartRow,StartCol, temp;
  print_board();
  printf( "please enter the starting row  ");
  scanf( "%d", &StartRow );
  printf( "\n" );
  printf( "please enter the starting col  " );
  scanf( "%d", &StartCol );
  board[StartRow][StartCol]=1;
  temp = 1;
  print_board();
}
return 0;

[Draco]

from what it looks like all you should have to do is define N to be at least one bigger than the board size you want

[major_blagger]

Is that the actual code you're using?

[Rx13]

yes, I will use the code. I am making modifications still, however. why?

[major_blagger]

Originally posted by Rx13

#include <stdio.h>
#include <stdlib.h>
#define N 8
int board[N][N];

void print_board()
{
   int i, j;
   for (i=0; i<N; ++i)
   {
      for (j=0; j<N; ++j)
      printf("%5d", board[i][j]);
      printf("\n\n");
   }
}

/* snip */

int main()
{
  int StartRow,StartCol, temp;
  print_board();
  printf( "please enter the starting row  ");
  scanf( "%d", &StartRow );
  printf( "\n" );
  printf( "please enter the starting col  " );
  scanf( "%d", &StartCol );
  board[StartRow][StartCol]=1;
  temp = 1;
  print_board();
}
return 0;

This code prints the board, asks the row/column, prints the board with that row and column labelled 1 (zero based row/column)
None of your other functions are called.
One of the functions is called 'continue' which is a reserved keyword. (Should this compile?)
There is a return statement that isn't in a block. (Should this compile?)

After doing the minimum work to get it to compile I got it to print an 8 by 8 board with no problem so, to me, it seems this isn't the actual code you're using.

[Rx13]

After compiling the code, i type a.out, run it, but it never returns a solution or a prompt. It's like it is working but it's not returning with solution not found or what have you. It compiles fine for me in Unix. But when I run it, it doesn't return anything. I don't know what's happening with it. If it works for you, fantastic, but not returning a solution in Unix for me.

I renamed the continue function earlier. It works now.

[major_blagger]

Originally posted by Rx13
After compiling the code, i type a.out, run it, but it never returns a solution or a prompt. It's like it is working but it's not returning with solution not found or what have you. It compiles fine for me in Unix. But when I run it, it doesn't return anything. I don't know what's happening with it. If it works for you, fantastic, but not returning a solution in Unix for me.

I renamed the continue function earlier. It works now.

It never asks you 'please enter starting row' or 'please enter starting col' ?
Does it print the board at all?

[Rx13]

It does ask me for the startRow and column, prints out my starting position but then it doesn't finish. It never returns to the command line, never displays the result or anything. It just idles.

[major_blagger]

Well, then you haven't posted your actual code. I suggest you make a call to continue() in your main().

Assuming the actual code does what you want it to, then it will probably take a very very very very very very long time to complete given the problem.

I'm also very suprised it completes for a 7x7 board. Can you please post your solution?

[c99]

Rx13

#define N 8

int board[N][N]

Arrays are zero indexed in C therefor defining N, 8, limits your
board from [0][0] to [7][7]. If you attempt to read from or write
to any memory location other than the specified range the result
will most certainly be undefined behavior.

Hope that helps.

[Rx13]

This is my code, as far as i've got : If it works, it takes a very long time!


[CODE]#include <stdio.h>
#include <stdlib.h>
#define N 9
int board[N][N];
int temp;
void printBoard()
{
int i, j;
for (i=0; i<N; ++i)
{
for (j=0; j<N; ++j)
printf("%5d", board[i][j]);
printf("\n\n");
}
}
int Range(int row, int col)
{
if (row>=0 && row<N && col>=0 && col<N)
return 1;
return 0;
}

int need_visit(int row, int col)
{
return (Range(row,col) && board[row][col]==0);
}

void next_move(int row, int col, int move[8][2], int *n)
{
*n = 0;
if (need_visit(row-2,col-1)) { move[*n][0]=row-2; move[(*n)++][1]=col-1; }
if (need_visit(row-2,col+1)) { move[*n][0]=row-2; move[(*n)++][1]=col+1; }
if (need_visit(row-1,col-2)) { move[*n][0]=row-1; move[(*n)++][1]=col-2; }
if (need_visit(row-1,col+2)) { move[*n][0]=row-1; move[(*n)++][1]=col+2; }
if (need_visit(row+1,col-2)) { move[*n][0]=row+1; move[(*n)++][1]=col-2; }
if (need_visit(row+1,col+2)) { move[*n][0]=row+1; move[(*n)++][1]=col+2; }
if (need_visit(row+2,col-1)) { move[*n][0]=row+2; move[(*n)++][1]=col-1; }
if (need_visit(row+2,col+1)) { move[*n][0]=row+2; move[(*n)++][1]=col+1; }
}

int continu(int row, int col)
{
int move[8][2], move_num;
if(temp==N*N)
return 1;
next_move(row, col, move, &move_num);
while(move_num--)
{
int move_row = move[move_num][0];
int move_col = move[move_num][1];
board[move_row][move_col] = ++temp;
if (continu(move_row,move_col))
return 1;
board[move_row][move_col] = 0;
--temp;
}
return 0;
}

int main()
{
int StartRow,StartCol, temp;
printBoard();
printf( "please enter the starting row ");
scanf( "%d", &StartRow );
printf( "\n" );
printf( "please enter the starting col " );
scanf( "%d", &StartCol );
board[StartRow][StartCol]=1;
temp = 1;
printBoard();
if (continu(StartRow, StartCol))
{
printf("solution was found");
printBoard();
}
else printf("no solution found");
return 0;
}

[code/]

[major_blagger]

Google Warnsdorff

[WaltP]

Originally posted by Rx13
[code/]

????

Maybe [/code] would work better.