Форум программистов, компьютерный форум CyberForum.ru

проверка судоку - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.65
ahamoth
 Аватар для ahamoth
0 / 0 / 0
Регистрация: 26.11.2010
Сообщений: 111
06.04.2011, 00:12     проверка судоку #1
Помогите пожалуйста написать программу , которая проверяет правильность решения судоку.
Мне нужно ,чтобы в двумерном массиве в каждой строке не было повторяющихся элементов, в каждом столбе, и в секторе .
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.04.2011, 00:12     проверка судоку
Посмотрите здесь:

решение судоку C++
C++ Решение Судоку
почти судоку) C++
C++ Судоку
Судоку C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kazak
 Аватар для kazak
3029 / 2350 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
06.04.2011, 01:59     проверка судоку #2
А в чем проблема? Складываешь все числа в строке, столбце, секторе, и, если сумма равна 45, то все в порядке. Циклы в помощь.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
06.04.2011, 02:58     проверка судоку #3
kazak, вот неправильно заполненное поле которое удовлетворяет этому условию:
Код
1 2 3 | 4 5 5 | 8 8 9
4 5 5 | 8 8 9 | 1 2 3
8 8 9 | 1 2 3 | 4 5 5
------+-------+------
2 3 1 | 5 5 4 | 8 9 8
5 5 4 | 8 9 8 | 2 3 1
8 9 8 | 2 3 1 | 5 5 4
------+-------+------
3 1 2 | 5 4 5 | 9 8 8
5 4 5 | 9 8 8 | 3 1 2
9 8 8 | 3 1 2 | 5 4 5
Добавлено через 46 минут
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
tab[9][9] = {{...},{...}...}; // таблица как-нибудь заполняется
int fail = 0;  // вначале полагаем, что в таблице все четко
int i;
for (i = 0; i < 9 && !fail; ++i) {
  int p[9] = {}; // 0 числа нет, 1 число есть
  int j;
  for (j = 0; j < 9 && !fail; ++j) {
     if (p[tab[i][j] - 1] == 0)
         p[tab[i][j] - 1] = 1;
     else
         fail = 1;  // два одинаковых числа в строке
  }
}
for (i = 0; i < 9 && !fail; ++i) {
  int p[9] = {};
  int j;
  for (j = 0; j < 9 && !fail; ++j) {
     if (p[tab[j][i] - 1] == 0)
         p[tab[j][i] - 1] = 1;
     else
         fail = 1;  // два одинаковых числа в столбце
  }
}
if (!fail) printf("все заполнено правильно\n");
else printf("заполнено не правильно или еще не заполнено\n");
тут массив p нужен чтобы определить встречалось ли уже число в строке/столбце или нет. А секторы сами собой проверятся в результате этого алгоритма.
kazak
 Аватар для kazak
3029 / 2350 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
06.04.2011, 08:00     проверка судоку #4
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int mas[9][9];
int check;
/*
...
*/
for (int i = 0; i < 9; i++)
{
   check = 0;
   for (int j = 0; j < 9; j++)
      check ^= 1 << mas[i][j];
   if (check != 0x3fe)
      printf("Строка %d неправильная\n", i);
}
/*аналогично для столбцов*/
ahamoth
 Аватар для ahamoth
0 / 0 / 0
Регистрация: 26.11.2010
Сообщений: 111
06.04.2011, 15:08  [ТС]     проверка судоку #5
Aye Aye, а как сделать в твоем коде проверку на наличие 0 в судокку?

Добавлено через 26 минут
да и кстати ,вот пример судоку который твоим алгоритмом неправильно решается
123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
08.04.2011, 03:05     проверка судоку #6
ahamoth, да да ... к моему алгоритму надо еще добавить:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (i = 0; i < 9 && !fail; i+=3) {
  int j;
  for (j = 0; j < 9 && !fail; j+=3) {
     int p[9] = {};
     int ik;
     for (ik = i; ik < i+3 && !fail; ++ik) {
        int jk;
        for (jk = j; jk < j+3 && !fail; ++jk) {
           if (p[tab[ik][jk] - 1] == 0)
               p[tab[ik][jk] - 1] = 1;
           else
                 fail = 1;  // два одинаковых числа в квадрате - секторе
        }
     }
  }
}
Суть: проверяем каждый квадратик 3х3 и переходим к следующему квадратику
не доглядел сначала, извини.

Цитата Сообщение от ahamoth Посмотреть сообщение
Aye Aye, а как сделать в твоем коде проверку на наличие 0 в судокку?
но так же не бывает! А вообще надо просто убрать -1 в во всех местах доступа к элементам массива p,
p[tab[i][j] - 1] -> p[tab[i][j]]
p[tab[j][i] - 1] -> p[tab[j][i]]
p[tab[ik][jk] - 1] -> p[tab[ik][jk]]
Yandex
Объявления
08.04.2011, 03:05     проверка судоку
Ответ Создать тему
Опции темы

Текущее время: 04:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru