Sudoku program

This is a discussion on Sudoku program within the C++ Programming forums, part of the General Programming Boards category; I'm trying to make a program that makes sudoku fields. If you don't know what that is, i'll explain. This ...

  1. #1
    Registered User
    Join Date
    Aug 2005
    Location
    HOLLAND
    Posts
    10

    Wink Sudoku program

    I'm trying to make a program that makes sudoku fields. If you don't know what that is, i'll explain. This is the first version, and it only checks if the number is possible for the rows or the columns. I don't understand why it doesn't work.

    Code:
    #include "SudokuField.h"
    #include <cstdlib>
    #include <iostream>
    
    bool SudokuField::fillfield()  {
    	char random;
    	for(int r = 0; r < 9; r++)
    		for(int k =0; k < 9; k++)
    			for(int i = 1; i < 10; i++)  {
    				random = rand() % 9 + 1;
    				if(checkpossible(r, k, random))  {
    					field[r][k] = random;
    					break;
    				};
    				if(i == 9)
    					return false;
    			};
    	return true;
    };
    
    bool SudokuField::checkpossible(numdata row, numdata column, numdata num)  {
    	for(int i = 0; i < 9; i++)
    		if(field[i][column] == static_cast<short>(num))
    			return false;
    	for(i = 0; i < 9; i++)
    		if(field[row][i] == static_cast<short>(num))
    			return false;
    
    	printfield();
    	return true;
    };
    
    void SudokuField::printfield()  {
    	std::cout << std::endl;
    	for(int r = 0; r < 9; r++)  {
    		for(int k = 0; k < 9; k++)  {
    			std::cout << static_cast<short>(field[r][k]);
    			if((k + 1) % 3 == 0)
    				std::cout << " ";
    		};
    		std::cout << std::endl;
    		if((r + 1) % 3 == 0)
    			std::cout << std::endl;
    	};
    };
    
    typedef short numdata;
    class SudokuField  {
    private:
    	numdata field [9][9];
    public:
    	SudokuField()  {
    		for(int i = 0; i <9; i++)
    			for(int j = 0; j < 9; j++)
    				field[i][j] = 0;
    	};
    	bool fillfield();
    	bool checkpossible(numdata row, numdata column, numdata num);
    	void printfield();
    };
    EDIT: whoops, <code> is now [ code ]
    Last edited by Feite; 11-25-2005 at 10:25 AM.

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    psst its [code][/code] not <code> </code>

  3. #3
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Ok, I got your program to work. There are basically 2 problems.
    1st you are generating random number to try to fill in the puzzle and you "give-up" after 10 tries have failed. The problem with this is that you are going to fail often, because within 10 tries some number won't even be tried while others may be repeatedly tried.

    Secondly, trying to fill in the puzzle randomly is difficlut even if you do try each digit at each position. It really needs some logic to make it efficient, however with that said. I have modify your code to randomly keep trying till it does hit upon a solution. Here it is

    Code:
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    #include <ctime>
    
    typedef short numdata;
    class SudokuField  
    {
    private:
    	numdata field [9][9];
    public:
    	SudokuField()  
    	{
    		for(int i = 0; i <9; i++)
    			for(int j = 0; j < 9; j++)
    				field[i][j] = 0;
    	};
    	bool fillfield();
    	bool checkpossible(numdata row, numdata column, numdata num);
    	void printfield();
    	void clear()
    	{
    		for(int i = 0; i <9; i++)
    			for(int j = 0; j < 9; j++)
    				field[i][j] = 0;
    
    	}
    };
    
    bool SudokuField::fillfield()  
    {
    	for(int r = 0; r < 9; r++)
    		for(int k =0; k < 9; k++)
    		{
    			numdata random[] = {1,2,3,4,5,6,7,8,9};
    			std::random_shuffle(random,random+9);
    			for(int i = 0; i < 9; i++)  
    			{
    				
    				if(checkpossible(r, k, random[i]))  
    				{
    					field[r][k] = random[i];
    					break;
    				}
    				if(i == 8)		
    					return false;
    			}
    		}
    	return true;
    };
    
    bool SudokuField::checkpossible(numdata row, numdata column, numdata num)  
    {
    	for(int i = 0; i < 9; i++)
    		if(field[i][column] == num)
    			return false;
    	for(int i = 0; i < 9; i++)
    		if(field[row][i] == num)
    			return false;
    
    	int xsect = 3*(column/3);
    	int ysect = 3*(row/3);
    
    	for (int i = xsect;i< xsect+3;i++)
    		for (int j = ysect; j < ysect+3; j++)
    			if (field[j][i]==num)
    				return false;
    
    
    	return true;
    };
    
    void SudokuField::printfield()  
    {
    	std::cout << std::endl;
    	for(int r = 0; r < 9; r++)  
    	{
    		for(int k = 0; k < 9; k++)  
    		{
    			std::cout << static_cast<short>(field[r][k]);
    			if((k + 1) % 3 == 0)
    				std::cout << " ";
    		};
    		std::cout << std::endl;
    		if((r + 1) % 3 == 0)
    			std::cout << std::endl;
    	};
    };
    
    int main()
    {
    	srand((unsigned)time(0));
    	SudokuField s;
    
    	while(!s.fillfield())
    		s.clear();
    
    	s.printfield();
    }
    ok, modified program to do check mentioned below. Now it's really ineeficient and I'm not even sure if it can generate a solution in a reasonable amount of time.

    edit2 - slight error, had my column and rows mixed up.
    Now it fully works and generates puzzle fairly quickly.
    Last edited by Darryl; 11-25-2005 at 01:36 PM.

  4. #4
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    There's another problem with your method. Besides not duplicating a number in a row or column, you should also check that a number is not duplicated in each of the 9 3x3 grids

    239
    913
    741

    here the 9, 3 and 1 is duplicated in this section though not in same row or column.

    edit: Modified code above to solve this
    Last edited by Darryl; 11-25-2005 at 01:32 PM.

  5. #5
    Registered User
    Join Date
    Aug 2005
    Location
    HOLLAND
    Posts
    10
    Thanks! I understand what i was doing wrong. Next problem: making a puzzle out of it . But I try to solve that myself.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 02-21-2008, 09:39 AM
  2. sudoku program
    By ElemenT.usha in forum C Programming
    Replies: 1
    Last Post: 02-12-2008, 11:51 AM
  3. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  4. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21